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)
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- Canadian Summer School on Quantum Information (CSSQI) (10th : 2010) /
- Simulating quantum computers with probabilistic methods
Open Collections
Canadian Summer School on Quantum Information (CSSQI) (10th : 2010)
Simulating quantum computers with probabilistic methods Van den Nest, Maarten Jul 24, 2010
Page Metadata
Item Metadata
Title | Simulating quantum computers with probabilistic methods |
Creator |
Van den Nest, Maarten |
Contributor | University of British Columbia. Department of Physics and Astronomy Workshop on Quantum Algorithms, Computational Models and Foundations of Quantum Mechanics Pacific Institute for the Mathematical Sciences |
Date Issued | 2010-07-24 |
Description | The study of quantum computations that can be simulated efficiently classically is of interest for numerous reasons. From a fundamental point of view, such an investigation sheds light on the intrinsic computational power harnessed in quantum mechanics as compared to classical physics. More practically, understanding which quantum computations do not offer any speed-up over classical computation provides insights in where (not) to look for novel quantum algorithmic primitives. In this talk we discuss novel classical simulation methods that are centered on probabilistic methods ('weak simulation'). We show how these techniques outperform existing methods that rely on the exact computation of measurement probabilities ('strong simulation'). Using weak simulation methods, several new classes of simulatable quantum circuits are generated. For example, we show that various concatenations of matchgate, Toffoli, Clifford, bounded-depth, Fourier transform an! d other circuits are classically simulatable. Finally, we focus on famous quantum algorithms and investigate the origin of their computational power, or their lack thereof. |
Subject |
Quantum computation classical simulation |
Genre |
Presentation |
Type |
Text Still Image Sound Moving Image |
Language | eng |
Date Available | 2016-11-22 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0103166 |
URI | http://hdl.handle.net/2429/30075 |
Affiliation |
Non UBC |
Peer Review Status | Unreviewed |
Scholarly Level | Postdoctoral |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
Aggregated Source Repository | DSpace |
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
Cite
Citation Scheme:
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>
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