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

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

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

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

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

Maarten Van den Nest Max Planck institute for quantum optics Garching, Germany Vancouver, July 2010 Simulating quantum computers with probabilistic methods 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  Example: consider the following class of elementary quantum circuits:  Let’s try to simulate this quantum circuit classically  -- but what do we really mean by ‘simulation’? Classical simulation of QC 0 Uf H 0 ⋮ H H H H , ( ) out x x f 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 with high accuracy [say, up to m bits in poly(n, m) time] out outZψ ψ ( )2 ( 1)n f xout out x Zψ ψ −= −∑ 0 Uf H 0 ⋮ H H H H , ( ) out x x f 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 with high accuracy [say, up to m bits in poly(n, m) time]  Need to compute                       i.e. #P-complete  -- so this is an un- simulatable circuit? out outZψ ψ ( )2 ( 1)n f xout out x Zψ ψ −= −∑ 0 Uf H 0 ⋮ H H H H { }| : ( ) 0 |x f x = What’s the problem?  Consider again                               followed by Z measurement. Q: How does this quantum computation allow to compute              ? • Outcome in each run: • Repeat circuit + measurement N = poly(n) times, record outcome in each run and output • Then c approximates                        with some accuracy • Best achievable accuracy  = 1/poly(n) due to Chernoff-Hoeffding bound [with exponentially small probability of failure] A: approximate                   with at most polynomial accuracy    = 1/poly(n), i.e. up to O(log n) bits 0 0n n outU ψ→ ≡ iz 1: i i c N z−= ∑ out outZψ ψ ε out outZψ ψ { }1, 1iz ∈ − out outZψ ψ Weak simulation  Classical-simulation-definition-Nr. 2: WEAK SIMULATION The computation                              can be simulated classically if there exists a classical algorithm that approximates with 1/poly(n) accuracy in poly-time [with exponentially small failure probability]  Just generate N = poly(n) random bit strings xk and output 0 0n n outU ψ→ ≡ out outZψ ψ ( )2 ( 1)n f xout out x Zψ ψ −= −∑ 0 Uf H 0 ⋮ H H H H ( )1: ( 1) kf x k c N = −∑ Strong versus weak simulation The strong approach    =   overdoing it a bit… The strong approach    =   overdoing it a bit… Strong versus weak simulation 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          can be computed in poly-time (b) It is possible to sample in poly-time from ψ x ψ 2 Prob( )x x ψ= CT states  DEFINITION An n-qubit state       is computationally tractable (CT) if (a) Given x, the coefficient          can be computed in poly-time (b) It is possible to sample in poly-time from  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, . . . ψ x ψ 2 Prob( )x x ψ= 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 x x xx xϕ ψ ϕδ εψ= +∑ ∑ ( )xδ = 1     If 0     otherwise x xϕ ψ≥ 1 ( )( )x xε δ= − 2 ( ) x xx x ψ δ ϕ ϕ    =      ∑ +    [similar for         ]( )xε sample 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              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          is also CT. ψ Oψ ψ ψ U ψ 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)             is efficiently computable sparse (ECS), then the circuit can be simulated efficiently [in the weak sense!] ψ ψ †U OU 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  +              is ECS, then use CT theorem]  Highlights distinction between entanglement and interference in quantum computation † 1U Z U 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,             is ECS  CT-Theorem identifies common element in these classes †U ZU 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 FOURIER 0 ⋮ CLIFFORDLU SPARSE 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 FOURIER 0 ⋮ CLIFFORDLU SPARSE 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:                                                     = product state Z/∆ = =  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 UfH 0 H⋮ Simon’s algorithm 0 UfH 0 H⋮ 0 out u u a uψ ψ = ∑ i ∼ Simon’s algorithm 0 UfH 0 H⋮ 0 out u u a uψ ψ = ∑ i ∼ 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. 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!  0PERMUTATION U1 H 0 H PERMUTATION U2  Doing the last round of classical computation coherently, Simon’s circuit can be  cast in the following form, followed by a single Z measurement Simon’s algorithm N oracle(s) Classical postprocessing  Doing the last round of classical computation coherently, Simon’s circuit can be  cast in the following form, followed by a single Z measurement  After U1, the system is in a CT state  Thus, if                   is ECS then entire computation is simulatable – but when does this happen? Simon’s algorithm 0 PERMUTATION U1 H 0 H PERMUTATION U2 † 2 2HU ZU H Simon’s algorithm  PROPERTY: Let g denote the function computed by U2.  Then the (x, y) element of equals  the x+y Fourier coefficient of g, i.e.  If g has poly(n) non-zero Fourier coefficients then                    is sparse  Nontrivial: If g has poly(n) nonzero Fourier coefficients then is  well-approximated by an operator that is efficiently computable sparse [proof uses Kushilevitz-Mansour ’93 result on learning sparse Boolean functions] † 2 2HU ZU H ( ) ( )1 ˆ( 1) ( ) 2 Tg u u x y m u g x y+ +− = +∑ † 2 2HU ZU H † 2 2HU ZU H 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}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            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:
https://iiif.library.ubc.ca/presentation/dsp.59370.1-0103166/manifest

Comment

Related Items