Report

When Exactly Do Quantum Computers Provide A Speedup? Scott Aaronson (MIT) Papers & slides at www.scottaaronson.com Genesis of This Talk “We all hear about the experimental progress toward building quantum computers … but in the meantime, what about the applications? It’s been 20 years since Peter Shor discovered his famous factoring algorithm. Where are all the amazing new applications we were promised?” Who promised you more quantum algorithms? Not me! The Parallelism Fallacy What’s the source of the popular belief that countless more quantum algorithms should exist? To me, it seems tied to the idea that a quantum computer could just “try every possible answer in parallel” But that’s not how quantum computing works! You need to choreograph an interference pattern, where the unwanted paths cancel The miracle, I’d say, is that this trick yields a speedup for any classical problems, not that it doesn’t work for more of them Underappreciated challenge of quantum algorithms research: beating 60 years of classical algorithms research An Inconvenient Truth A problem has to be special even to be a plausible candidate for an exponential quantum speedup 3SAT NP-hard NP-complete NP BQP (Quantum P) P P≠BQP, NPBQP: Plausible conjectures, which we have no hope of proving given the current state of complexity theory Rest of the Talk I. Survey of the main families of quantum algorithms that have been discovered (and their limitations) II. Results in the black-box model, which aim toward a general theory of when quantum speedups are possible III. Lemons into lemonade: implications for physics of the limitations of quantum computers Quantum Simulation “What a QC does in its sleep” The “original” application of QCs! My personal view: still the most important one Major applications (high-Tc superconductivity, protein folding, nanofabrication, photovoltaics…) High confidence in possibility of a quantum speedup Can plausibly realize even before universal QCs are available Shor-like Algorithms “The magic of the Interesting Fourier transform” In BQP: Pretty much anything you can think of that reduces to finding hidden structure in abelian groups Factoring, discrete log, elliptic curve problems, Pell’s equation, unit groups, class groups, Simon’s problem… Breaks almost all public-key cryptosystems used today But theoretical public-key systems exist that are unaffected Can we go further? Hidden Subgroup Problem Generalizes Shor to nonabelian groups. Captures e.g. Graph Isomorphism Alas, nonabelian HSP has been the Afghanistan of quantum algorithms! Grover-like Algorithms Quadratic speedup for any problem involving searching an unordered list, provided the list elements can be queried in superposition Implies subquadratic speedups for many other basic problems Bennett et al. 1997: For black-box searching, the squareroot speedup of Grover’s algorithm is the best possible Quantum Walk Algorithms Childs et al. 2003: Quantum walks can achieve provable exponential speedups over classical walks, but for extremely “fine-tuned” graphs THE GLUED TREES Quantum Adiabatic Algorithm (Farhi et al. 2000) Hi Hamiltonian with easilyprepared ground state Hf Ground state encodes solution to NP-complete problem Problem: “Eigenvalue gap” can be exponentially small Landscapeology Adiabatic algorithm can find global minimum exponentially faster than simulated annealing (though maybe other classical algorithms do better) Simulated annealing can find global minimum exponentially faster than adiabatic algorithm (!) Simulated annealing and adiabatic algorithm both need exponential time to find global minimum Quantum Machine Learning Algorithms ‘Exponential quantum speedups’ for solving linear systems, support vector machines, Google PageRank, computing Betti numbers, EM scattering problems… THE FINE PRINT: 1. Don’t get solution vector explicitly, but only as vector of amplitudes. Need to measure to learn anything! 2. Dependence on condition number could kill exponential speedup 3. Need a way of loading huge amounts of data into quantum state (which, again, could kill exponential speedup) 4. Not ruled out that there are fast randomized algorithms for the same problems BosonSampling Suppose we just want a quantum system for which there’s good evidence that it’s hard to simulate classically—we don’t care what it’s useful for A.-Arkhipov 2011, Bremner-Jozsa-Shepherd 2011: In that case, we can plausibly improve both the hardware We showed: if a fast, classical requirements and the evidence for classicalExperimental hardness, exact of algorithm demonstrations with 3-4 compared to simulation Shor’s factoring BosonSampling is possible, photons achieved (by Ourhierarchy proposal: then the polynomial groups in Oxford, Identical single Brisbane, Rome, Vienna) collapses to the third level. photons sent through network of interferometers, For more: My complex quantum systems seminar tomorrow then measured at output modes “But you just listed a bunch of examples where you know a quantum speedup, and other examples where you don’t! What you guys need is a theory, which would tell you from first principles when quantum speedups are possible.” The Quantum Black-Box Model The setting for much of what we know about the power of quantum algorithms i X=x1…xN xi X “Query complexity” of f: The minimum number of queries used by any i,a,w i, athat , w outputs if(X), , a high xi , w algorithm ,a, w iwith probability, every a=“answer X of interest to us (i=“queryfor register,” register,” w=“workspace”) An algorithm can make query transformations, which map as well as arbitrary unitary transformations that don’t depend on X (we won’t worry about their computational cost). Its goal is to learn some property f(X) (for example: is X 1-to-1?) Total Boolean Functions f : 0,1 0,1 N D(f): Deterministic query complexity of F R(f): Randomized query complexity Q(f): Quantum query complexity Example: DORN RORN N , QORN ~ N Theorem (Beals et al. 1998): For all Boolean functions f, D f O Q f 6 How to reconcile with the exponential speedup of Shor’s algorithm? Totality of f. Longstanding Open Problem: Is there any Boolean function with a quantum quantum/classical gap better than quadratic? Almost-Total Functions? Conjecture (A.-Ambainis 2011): Let Q be any quantum algorithm that makes T queries to an input X{0,1}N. Then there’s a classical randomized that makes poly(T,1/,1/) queries to X, and that approximates Pr[Q accepts X] to within on a ≥1- fraction of X’s Theorem (A.-Ambainis): This would follow from an extremely natural conjecture in discrete Fourier analysis (“every bounded low-degree polynomial p:{0,1}N[0,1] has a highly influential variable”) The Collision Problem Given a 2-to-1 function f:{1,…,N}{1,…,N}, find a collision (i.e., two inputs x,y such that f(x)=f(y)) 10 4 1 8 7 9 11 5 6 4 2 10 3 2 7 9 11 5 1 6 3 8 Variant: Promised that f is either 2-to-1 or 1-to-1, decide which Models the breaking of collision-resistant hash functions—a central problem in cryptanalysis “More structured than Grover search, but less structured than Shor’s period-finding problem” Birthday Paradox: Classically, ~N queries are necessary and sufficient to find a collision with high probability Brassard-Høyer-Tapp 1997: Quantumly, ~N1/3 queries suffice Grover on N2/3 f(x) values N1/3 f(x) values queried classically A. 2002: First quantum lower bound for the collision problem (~N1/5 queries are needed; no exponential speedup possible) Shi 2002: Improved lower bound of ~N1/3. Brassard-HøyerTapp’s algorithm is the best possible Symmetric Problems A.-Ambainis 2011: Massive generalization of collision lower bound. If f is any function whatsoever that’s symmetric under permuting the inputs and outputs, and has sufficiently many outputs (like collision, element distinctness, etc.), then R f O Q f polylogQ f 7 New Result (Ben-David 2014): If f:SN{0,1} is any Boolean function of permutations, then D(f)=O(Q(f)12) Upshot: Need a “structured” promise if you want an exponential quantum speedup What’s the largest possible quantum speedup? “Forrelation”: Given two Boolean functions f,g:{0,1}n{-1,1}, estimate how correlated g is with the Fourier transform of f: 1 2 3n / 2 f x 1 x y x , y0 ,1n gy 1/ 3? 2 / 3? A.-Ambainis 2014: This problem is solvable using only 1 quantum query, but requires at least ~2n/2/n queries classically Furthermore, this separation is essentially the largest possible! Any N-bit problem that’s solvable with k quantum queries, is also solvable with ~N1-1/2k classical queries For details: My CS theory seminar on Friday Can we turn the lemon of QCs’ limitations into the lemonade of physical insight? Proposal: Adopt as a principle (conjecture?) that there’s no efficient way to solve NP-complete problems in the physical world, then investigate the implications for other issues Example Implications: - No closed timelike curves (A.-Watrous 2009) - No postselected final state (probably rules out Horowitz-Maldacena) - Something like the holographic entropy bound should hold - Metastable states must be unavoidable in spin glasses, protein folding, etc. - Many spectral gaps must decrease exponentially with number of particles “Explanation” for the linearity of the Schrödinger equation Abrams & Lloyd 1998: If quantum mechanics were nonlinear, one could generically exploit that to solve NP-complete problems in polynomial time 1 solution to NP-complete problem No solutions A complexity-theoretic argument against hidden variables? A. 2004: In theories like Bohmian mechanics, in order to sample the entire trajectory of the hidden variable, you’d need the ability to solve the collision problem— something I showed is generically hard even for a quantum computer 1 N x y N x f x x 1 Measure 2nd register 2 f x The Firewall Paradox (AMPS 2012): Refinement of Hawking’s information paradox that challenges black hole complementarity If the black hole interior is “built” out of the same qubits coming out as Hawking radiation, then why can’t we do something to those Hawking qubits, then dive into the black hole, and see that we’ve completely destroyed the spacetime geometry in the interior? Entanglement among Hawking photons detected! Harlow-Hayden 2013: Striking argument that doing the AMPS experiment would require solving a problem that’s exponentially hard even for a quantum computer A. 2014: Strengthened the Harlow-Hayden argument, to showmade that aa dent general ability to perform “So, long before you’ve in the problem, the black AMPSevaporated experimentanyway, would imply the ability to to hole hasthe already and there’s nowhere invert any cryptographic one-way function jump to see a firewall!” MODEL SITUATION: RBH Is the geometry x,0ofRspacetime 0 B f x protected x,1 Rby1 an g x H B 1 2narmor x0,of 1n computational complexity? 1 R: “Old” Hawking photons B: Hawking photon just now coming out H: Degrees of freedom still in black hole H f,g: Two functions for which we want to know whether their ranges are equal or disjoint If we could detect entanglement between R and B for any |RBH, then we could solve a close cousin of the collision problem! Summary Exponential quantum speedups depend on structure For example, abelian group structure, glued-trees structure, forrelational structure… Sometimes we can even find such structure in real, non-blackbox problems of practical interest (e.g., factoring) The black-box model lets us develop a rich theory of what kinds of structure do or don’t suffice for exponential speedups Understanding the limitations of quantum computers has given us new insights about seemingly-remote issues in physics Single most important application of QC (in my opinion): Disproving the people who said QC was impossible!