Canadian Summer School on Quantum Information (CSSQI) (10th : 2010)

Simulating quantum computers with probabilistic methods Van den Nest, Maarten Jul 24, 2010

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
59370-van_den_Nest_van_2010.pdf [ 371.05kB ]
59370-WS Jul 24 Van Den Nest.mp4 [ 140.14MB ]
Metadata
JSON: 59370-1.0103166.json
JSON-LD: 59370-1.0103166-ld.json
RDF/XML (Pretty): 59370-1.0103166-rdf.xml
RDF/JSON: 59370-1.0103166-rdf.json
Turtle: 59370-1.0103166-turtle.txt
N-Triples: 59370-1.0103166-rdf-ntriples.txt
Original Record: 59370-1.0103166-source.json
Full Text
59370-1.0103166-fulltext.txt
Citation
59370-1.0103166.ris

Full Text

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)  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.59370.1-0103166/manifest

Comment

Related Items