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)
- 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 2010-07-24
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
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 Summer School on Quantum Information (10th : 2010 : Vancouver, B.C.) |
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 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/ |
AggregatedSourceRepository | 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}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
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