Open Collections

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)