Open Collections

Simulating quantum computers with probabilistic methods  Maarten Van den Nest Max Planck institute for quantum optics Garching, Germany  Vancouver, July 2010  Motivation  Why study classical simulations? There is a lot we don’t know about the following problems: What are the essential ingredients responsible for quantum computational power? Are quantum computers truly exponentially more powerful than classical ones? Except quantum simulation, what would we actually do with a quantum computer if it were built?  Two complementary routes towards understanding such questions:  Quantum algorithms  Classical simulations  Why study classical simulations? There is a lot we don’t know about the following problems: What are the essential ingredients responsible for quantum computational power? Are quantum computers truly exponentially more powerful than classical ones? Except quantum simulation, what would we actually do with a quantum computer if it were built?  Two complementary routes towards understanding such questions:  Quantum algorithms  Classical simulations  Why probabilistic simulations? Quantum mechanics is probabilistic  Outline  I.  Fundamental concepts: what is classical simulation of QC?  II.  Main result: class of simulatable quantum computations  III.  Applications & examples  IV.  Quantum algorithms  I. Fundamental concepts  Classical simulation of QC Example: consider the following class of elementary quantum circuits:  0  H H  ⋮  H H  Uf  H 0  ψ out = ∑ x, f ( x) x  Let’s try to simulate this quantum circuit classically -- but what do we really mean by ‘simulation’?  Strong simulation Classical-simulation-definition-Nr. 1: STRONG SIMULATION A quantum computation can be simulated classically if there exists a poly-time classical algorithm that computes ψ out Z ψ out with high accuracy [say, up to m bits in poly(n, m) time] 0  H H  ⋮  H H  ψ out Z ψ out = 2− n ∑ (−1) f ( x ) Uf  x  H 0  ψ out = ∑ x, f ( x) x  Strong simulation Classical-simulation-definition-Nr. 1: STRONG SIMULATION A quantum computation can be simulated classically if there exists a poly-time classical algorithm that computes ψ out Z ψ out with high accuracy [say, up to m bits in poly(n, m) time] 0  H H  ⋮  H H  ψ out Z ψ out = 2− n ∑ (−1) f ( x ) Uf  x  H 0  Need to compute | { x : f ( x) = 0} | i.e. #P-complete -- so this is an unsimulatable circuit?  What’s the problem? Consider again 0 → U 0 ≡ ψ n  n  followed by Z measurement.  out  Q: How does this quantum computation allow to compute ψ out Z ψ out  ?  • Outcome in each run: zi ∈ {1, −1} • Repeat circuit + measurement N = poly(n) times, record outcome zi in each run and output c := N −1  ∑z  i  i  • Then c approximates ψ out Z ψ out  with some accuracy  • Best achievable accuracy = 1/poly(n) due to Chernoff-Hoeffding bound [with exponentially small probability of failure]  A: approximate ψ out Z ψ out i.e. up to O(log n) bits  with at most polynomial accuracy ε = 1/poly(n),  Weak simulation Classical-simulation-definition-Nr. 2: WEAK SIMULATION The computation 0 → U 0 ≡ ψ out can be simulated classically if there exists a classical algorithm that approximates ψ out Z ψ out with 1/poly(n) accuracy in poly-time [with exponentially small failure probability] n  0  n  H H  ⋮  H H  ψ out Z ψ out = 2− n ∑ (−1) f ( x ) Uf  x  H 0  Just generate N = poly(n) random bit strings xk and output c :=  1 N  ∑ (−1) k  f ( xk )  Strong versus weak simulation  The strong approach  = overdoing it a bit…  Strong versus weak simulation  The strong approach  = overdoing it a bit…  Our work Develop new weak classical simulation algorithms Results: • One main theorem • Several applications • Simulating quantum algorithms  II. Main Theorem  CT states DEFINITION An n-qubit state ψ  is computationally tractable (CT) if  (a) Given x, the coefficient x ψ can be computed in poly-time (b) It is possible to sample in poly-time from Prob( x) = x ψ  2  CT states DEFINITION An n-qubit state ψ  is computationally tractable (CT) if  (a) Given x, the coefficient x ψ  can be computed in poly-time  (b) It is possible to sample in poly-time from Prob( x) = x ψ  2  Examples: most of existing simulation results • Product states, MPS, TTN, stabilizer states, Weighted graph states • Standard basis inputs followed by matchgate circuits • Product inputs followed by Toffoli’s, QFT, log-depth n.n. circuits, . . .  Overlaps of CT states PROPERTY: If ψ and ϕ are two CT states, then there exist an efficient classical algorithm to approximate ϕ ψ with 1/poly(n) accuracy  Overlaps of CT states PROPERTY: If ψ and ϕ are two CT states, then there exist an efficient classical algorithm to approximate ϕ ψ with 1/poly(n) accuracy Hint of proof:  δ ( x) =  ϕψ  xϕ ≥ xψ  1  If  0  otherwise  ε ( x ) = 1 − δ ( x)  =  ∑ϕ  x xψ  =  ∑ϕ  x x ψ δ ( x) + ∑ ϕ x x ψ ε ( x)  =  ∑  ϕ x  sample  2   x ψ  δ ( x)   ϕ x    +  [similar for ε ( x ) ]  Eff. Computable + bounded  CT States Other properties: PROPERTY: If ψ is a CT state and O is a d-local operator with d = O(log n), then the expectation value ψ O ψ can be estimated efficiently with 1/poly accuracy. PROPERTY: If ψ is a CT state and U is a poly-size circuit of Toffoli and/or diagonal gates, then U ψ is also CT.  Sparse operations An n-qubit operation is efficiently computable sparse (ECS) if • Only poly(n) nonzero entries per row/column • Given n-bit string x, it is possible to list all nonzero entries in row x in poly-time; similar for columns Examples: • • • • •  Pauli products The standard Uf operator (where f is in P) A single d-qubit gate U⊗I with d = O(log n) Circuits of Toffoli + diagonal (+ adding a few non-toffoli’s) d-local Hamiltonians  Main Theorem  CT-THEOREM: Let ψ be an n-qubit state, let U denote a poly-size circuit and let O denote an observable. If (a) ψ  is CT, and  † (b) U OU is efficiently computable sparse (ECS),  then the circuit can be simulated efficiently [in the weak sense!]  III. Applications  App. 1: Sparse circuits THEOREM: Consider an n-qubit circuit U of m gates, each of which is ECS with sparseness s, acting on a product state and followed by Z measurement. If sm = poly(n) then this circuit can be simulated classically. †  [Proof: product state is CT + U Z1U is ECS, then use CT theorem]  Highlights distinction between entanglement and interference in quantum computation  App. 2: “Unification” Consider a product input followed by poly-size circuit U that is one of the following, followed by Z measurement. • • • •  Clifford circuit, possibly interspersed with few non-Cliffords Toffoli circuit -- i.e. “classical” computation Matchgate circuit Bounded-depth circuit  All of the above cases can be simulated classically -- with very different methods! Product state is trivially CT + in all above cases, U † ZU is ECS CT-Theorem identifies common element in these classes  App. 3: Composability Given two circuits U1 and U2 that can be simulated efficiently classically, when is the concatenated circuit U2U1 classically simulatable? Nontrivial question – cf. e.g Shor algorithm!  App. 3: Composability Given two circuits U1 and U2 that can be simulated efficiently classically, when is the concatenated circuit U2U1 classically simulatable? Nontrivial question – cf. e.g Shor algorithm! CT-Theorem leads to classical simulation of concatenated circuits of different types: 0  ⋮  0  LU  FOURIER  SPARSE  CLIFFORD  MATCHGATE  App. 3: Composability Given two circuits U1 and U2 that can be simulated efficiently classically, when is the concatenated circuit U2U1 classically simulatable? Nontrivial question – cf. e.g Shor algorithm! CT-Theorem leads to classical simulation of concatenated circuits of different types: 0  ⋮  0  LU  FOURIER  SPARSE  CLIFFORD  MATCHGATE  IV. Quantum algorithms  Example #1: Potts model q. algorithm  Potts model algorithm Z = partition function of classical spin system e.g. Ising, Potts, … I. Arad & Z. Landau ‘08: quantum algorithm to approximate Z/∆ with 1/poly accuracy, where ∆ is easy-to-compute normalization  α  VDN, Dür, Briegel ’07: Z/∆ = α ψ  = product state  ψ = stabilizer state  Both states are CT states And overlaps between CT states can be estimated with 1/poly accuracy classically in poly-time Hence, Potts model quantum algo can be simulated classically  Example #2: Simon’s algorithm  Simon’s algorithm SIMON’S PROBLEM: Consider oracle access to n-bit function f. It is promised that there exists a bit string a such that f(x) = f(y) if and only if x+y = a. Objective: find the string a. Classically O(2n/2) queries are required, quantum only O(n). The quantum circuit has very simple structure:  0  ⋮  0  H  Uf  H  Simon’s algorithm  ψ out ∼  0  ⋮  0  H  Uf  H  ∑  u i a =0  u ψu  Simon’s algorithm Final step: classical postprocessing Measure 1st register N=O(n) times, yielding N bit strings uk that are orthogonal to a. Then solving a simple system of linear equations yields a.  ψ out ∼  0  ⋮  0  H  Uf  H  ∑  u i a =0  u ψu  Simon’s algorithm Where does the power of Simon’s algorithm originate? Let’s try to simulate such Simon-type circuits and see how far we get Here we focus on the -- somewhat surprising! – role of the last round i.e. classical post-processing  Simon’s algorithm THEOREM: If the function computed in the classical post-processing has a sufficiently peaked Fourier spectrum, then the entire quantum computation is classically simulatable!  i.e. nontrivial interplay between FT and classical round is required to obtain exponential speed-up!  Conclusion  Weak simulation yields new insights in simulation of QC We’ve only scratched the surface… See MVDN, arXiv:0911.1624 Some advertising of new work: Matchgate computations and linear threshold gates (MVDN, arXiv:1005.1143)  Thank you very much!  Simon’s algorithm Doing the last round of classical computation coherently, Simon’s circuit can be cast in the following form, followed by a single Z measurement  0  H  PERMUTATION  U1  H  PERMUTATION  U2  0  N oracle(s)  Classical postprocessing  Simon’s algorithm Doing the last round of classical computation coherently, Simon’s circuit can be cast in the following form, followed by a single Z measurement  0  H  PERMUTATION  H  U1  PERMUTATION  U2  0  After U1, the system is in a CT state † Thus, if HU 2 ZU 2 H is ECS then entire computation is simulatable – but when does this happen?  Simon’s algorithm PROPERTY: Let g denote the function computed by U2. Then the (x, y) element of HU 2 † ZU 2 H equals the x+y Fourier coefficient of g, i.e.  1 2m  ∑  u  ( − 1)  g (u )+ uT ( x + y )  = gˆ ( x + y )  † If g has poly(n) non-zero Fourier coefficients then HU 2 ZU 2 H is sparse  † Nontrivial: If g has poly(n) nonzero Fourier coefficients then HU 2 ZU 2 H is well-approximated by an operator that is efficiently computable sparse  [proof uses Kushilevitz-Mansour ’93 result on learning sparse Boolean functions]  Strong versus weak simulation  This gives an example of a class of quantum computations where • From the point of view of strong simulation, these quantum circuits are impossible to simulate classically (unless P = #P) • From the point of view of weak simulation, they are trivial to simulate classically Note how elementary this class of quantum circuits is (coherent version of probabilistic classical computation)