BQP and the Polynomial Hierarchy

BQP and the Polynomial Hierarchy

Quantum Supremacy Scott Aaronson (MITUT Austin) Strachey Lecture, Oxford University May 24, 2016 What this talk is about | Quantum Supremacy: A term thats come into vogue in the past few years for quantum computing experimentshopefully doable in the near future that aim merely to overthrow the Extended Church-Turing Thesis with as much certainty as possible, not to do anything of practical use The Extended Church-Turing Thesis (ECT) Everything feasibly

computable in the physical world is feasibly computable by a (probabilistic) Turing machine Shors Theorem (1994): QUANTUM SIMULATION has no efficient classical algorithm, unless FACTORING Quantum Mechanics in One Slide: Probability Theory with Minus Signs Probability Theory: Quantum Mechanics: s11 s1n p1 q1 s s p q nn n

n1 n u11 u1n 1 1 u u nn n n1 n pi 0, n p i

1 i 1 Linear transformations that conserve 1-norm of probability vectors: Stochastic matrices i C, n 2 i 1

i 1 Linear transformations that conserve 2-norm of amplitude vectors: Unitary matrices What is quantum computing? In the 1980s, Feynman, Deutsch, and others noticed that quantum systems with n particles seemed to take ~2n time to simulateand had the idea of building a quantum computer to overcome that problem Not just a matter of trying all answers in parallel! Exponentially many possible measurement x outcomes, but you n x 1,, 2

only see one, probabilistically! Any hope for a speedup rides on the magic of interference between positive and negative contributions to an amplitude x BQP (Bounded-Error Quantum Polynomial-Time): The class of problems solvable efficiently by a quantum computer,

defined by Bernstein and Vazirani in Interesting 1993 Shor 1994: Factoring integers is in BQP NP-complete P #P NP BQP Factoring P So quantum computers refute the ECT what more proof could anyone want? Building a scalable quantum computer is hard! After 20+ years, no fundamental obstacle has been found

but cant we just refute the skeptics today? Can we meet the experimentalists halfway, and show computational hardness for quantum systems closer to what theyre actually working with? FACTORING might have a fast classical algorithm! At any rate, its an extremely special problem Wouldnt it be great to show that if, quantum computers can be simulated classically, then (say) P=NP? Motivates Quantum Supremacy a.k.a., physicists learning to think like applied cryptographers! Define a clear mathematical task that you can perform with quantum hardware of the near future

Think hard about how your worst enemy would perform that task (or appear to) using classical resources only Closest historical analogue in physics: the Bell inequality Publish benchmark challenges for classical skeptics Isolate the cleanest possible hardness assumption that implies what you want Leave a safety margin! The Sampling Approach A.-Arkhipov 2011, Bremner-Jozsa-Shepherd 2011 Consider sampling problems, where given an input x, were

asked to output a sample (exactly or approximately) from a probability distribution Dx over n-bit strings Compared to problems with a single valid output (like FACTORING), sampling problems can be (1) Easier to solve with near-future quantum devices, and (2) Easier to argue are hard for classical computers! (We merely give up on: practical applications, fast classical way to verify the result) BosonSampling (A.-Arkhipov 2011) A rudimentary type of quantum computing, involving only non-interacting photons Classical counterpart: Galtons Board Replacing the balls by photons leads to famously counterintuitive phenomena, like the Hong-Ou-Mandel dip Whats going on? In general, we consider a

network of beamsplitters, with n input modes (locations) and m>>n output modes n identical photons enter, one per input mode Assume for simplicity they all leave in different m modesthere are possibilities n The beamsplitter network defines a column-orthonormal 2 mn matrix AC , such that Pr outcome S Per AS n

where Per X xi , i S n i 1 nn submatrix of A corresponding to S is the matrix permanent (like the determinant, but without minus signs!) So Can We Use Photons to Calculate Permanentsa #P-Complete Problem? That sounds way too good to be true Explanation: If X is a submatrix of a unitary matrix, then |Per(X)|2 will typically be exponentially small. So to get a reasonable estimate of |Per(X)|2 for a given X, wed generally need to repeat the optical experiment

exponentially many times! So Then, Why Is BosonSampling Classically Hard? Sketch: Suppose there were a poly-time classical algorithm to sample the same distribution as the experiment. Then the probabilitiesi.e., |Per(X)|2 for XCnncould be estimated using approximate counting (in BPPNP). So P#P would equal BPPNP, collapsing the polynomial hierarchy to the third level! Arguing that even a noisy BosonSampling device samples a classically-hard distribution is much more complicated Our Main Result: Suppose theres a poly-time classical algorithm to sample a distribution even 1/poly(n)-close to the BosonSampling one in variation distance. Then theres also a BPPNP algorithm to estimate |Per(X)|2, with high probability over a matrix XCnn of i.i.d. N(0,1) Gaussians Our Main Conjecture: The above is already #P-hard. (If so, then even a noisy simulation would collapse PH) Verification

Obvious Difficulty: Supposing you do a BosonSampling experiment, how does a classical computer even verify the result? Could do so by calculating |Per(X)|2 for Xs corresponding to the output samples, and seeing whether theyre anomalously large But this entails calculating permanents, which takes ~2n time for n photons! Doesnt that defeat the purpose? Our Claim: Not necessarily. Sweet spot at n 30 or 40 photons The Experimental Situation Last summer, the group at Bristol reported BosonSampling with 6 photons (in a special case)confirming experimentally that 6photon amplitudes are indeed given by permanents of 66 complex matrices, just as quantum mechanics says But scaling up to more photons is hard, because it seems to require deterministic single-photon sources What might help: Scattershot BosonSampling (proposed

by the group here at Oxford, esp. Steve Kolthammer) But its worth considering whether BosonSampling-like ideas could be ported to other QC architectures, besides optics In a few years, were likely to have 40-50 high-quality qubits with controllable couplings, in superconducting or ion-trap architectures. (Way more exciting to me than 1000 lower-quality annealing qubits!) John Martinis, Google Still wont be enough for most QC applications. But should suffice for a quantum supremacy experiment! Our duty as theoretical computer scientists: Tell the experimenters what they can do with their existing or planned hardware, how to verify it, and what can be said about the hardness of simulating it classically The Random Quantum Circuit Proposal

(Ongoing joint work with Lijie Chen) Generate a quantum circuit C on n qubits in a nn lattice, with d layers of random nearest-neighbor gates Apply C to |0n and measure. Repeat t times, to obtain samples x1,,xT from {0,1}n Apply a statistical test to x1,,xT (taking classical exponential time, which is OK for n40) Publish C. Challenge skeptics to generate samples passing the test in a reasonable amount of time Verification of Outputs e x Simplest: Just check whether the histogram of probabilities of the observed xis matches the theoretical prediction (assuming probabilities are exponentially

distributed, as with a Haar-random state) xe x Theorem (Brandao-Harrow-Horodecki 2012): A random local circuit on nn qubits produces nearly Gaussian amplitudes (hence nearly exponentially-distributed probabilities) after d=O(n) depth (right answer should be d=O(n)) To be more concrete, lets do the following test Do an 0.6 fraction of the sampled xis have ln 2 p xi n ? 2 Our Strong Hardness Assumption Theres no polynomial-time classical algorithm A such that, given a uniformly-random quantum circuit C with n

qubits and m>>n gates, n Pr A C guesses whether 0 C 0 C n 2 ln 2 1 n 2 n 2 2 Note: There is a polynomial-time classical algorithm that guesses with probability 1 1 m 2 4 (just expand 0|nC|0n out as a sum of 4m terms, then

sample a few random terms) Theorem: Assume SHA. Then given as input a random quantum circuit C, with n qubits and m>>n gates, theres no polynomial-time classical algorithm that even passes our statistical test for C-sampling with high probability Proof Sketch: Given a circuit C, first hide which amplitude we care about by applying a random XOR-mask to the outputs, producing a C such that n n n 0 C' z 0 C0 Now let A be a poly-time classical algorithm that passes the

test for C with probability 0.99. Suppose A outputs samples x1,,xT. Then if xi =z for some i[T], guess that T], guess that ln 2 n n 2 0 C0 n 2 Violates SHA! Otherwise, guess that with probability 1 m 2 2 n 1 Time-Space Tradeoffs for Simulating Quantum Circuits Given a general quantum circuit with n qubits and m>>n two-qubit gates, how should we simulate it classically? Schrdinger way: Feynman way:

Store whole wavefunction Sum over paths O(2n) memory, O(m2n) time O(m+n) memory, O(4m) time n=40, m=1000: Feasible but requires TB of RAM n=40, m=1000: Infeasible but requires little RAM Best of both worlds? Theorem: Let C be a quantum circuit with n qubits and d layers of gates. Then we can compute each transition amplitude, x|C|y, in dO(n) time and poly(n,d) space.

C2 C1 Proof: Savitchs Theorem! Recursively divide C into two chunks, C1 and C2, with d/2 layers each. Then x|C | y x | C1 | z z | C2 | y z 0 ,1 n Evaluation T d 2 n T d T d 2O n log d time: 2 2

Comments Time/Space Tradeoff: Starting with the nave, ~2n-time and -memory Schrdinger simulation, every time you halve the available memory, multiply the running time by the circuit depth d and you can still simulate Is this dO(n) algorithm optimal? Open problem! Related to L vs. NL We dont get a polytime algorithm to guess x|C|y with greater than 4-m success probability (why not?) A Different Approach: Fourier Sampling / IQP Given a Boolean function n f : 0,1 1,1 Let Df be the distribution over {0,1}n defined by

2 Pr z f z f z 1 2n 1 xz f x Trivial Quantum Algorithm: x 0 ,1 n |0 H

Problem: Sample exactly or approximately from Df |0 H |0 H H f H H Classical Hardness of Fourier Sampling? If f is a black box: Any classical algorithm to sample Df

within requires (2n/n) queries to f [T], guess that A.-Ambainis 2015] (2n) queries for sufficiently small [T], guess that A.-Chen 2016] Even a classical randomized algorithm with a PH oracle must make exponentially many queries to f [T], guess that A. 2010] If f is given by an explicit circuit: As usual, any classical algorithm to sample Df exactly would collapse PH A classical algorithm to sample Df within seems unlikely, but that requires a new hardness assumption [T], guess that BremnerMontanaro-Shepherd 2015] SHA is false, as it is for BosonSampling SCOTT & LIJIE A N EW KIND OF HARDNESS Our Proposal: Compare complexity classes, relative to black boxes that are constrained

to lie in the class P/poly (i.e., black boxes that we can actually instantiate using small circuits) Zhandry 2013: If pseudorandom functions exist, then theres an AP/ poly with PABQPA We show: Any such result must use some computational assumption Suppose we do FourierSampling with a pseudorandom function f. What can we say about the hardness of simulating the result classically? Theorem: No polynomial-time classical algorithm, which accesses a cryptographic pseudorandom function fP/poly only as a black box, can do anything that passes a standard statistical test for FourierSampling f

Proof Sketch: No such algorithm could pass a test for FourierSampling a truly random function. So if we run the test and it passes, we distinguished f from truly random! Conclusions In the near future, we might be able to perform random quantum circuit and Fourier sampling with ~40 qubits Central question: how do we verify that something classically hard was achieved? Theres no direct physical signature of quantum supremacy, because supremacy just means the nonexistence of a fast classical algorithm to do the same thing. This is what makes complexity theory unavoidable! Quantum computing theorists would be urgently called upon to think about this, even if there were nothing theoretically interesting to say. But there is! Open Problems (& Recent Progress) BosonSampling with constant fraction of lost photons

A.-Brod 2015: BosonSampling with constant number of lost photons is just as hard as perfect BosonSampling Show that a collapse of quantum and classical approximate sampling would collapse the polynomial hierarchy A.-Chen 2016: Any proof of this would need to be non-relativizing Give an efficient classical cryptographic scheme to verify the outputs of a BosonSampler or random quantum circuit sampler Shepherd & Bremner 2008: Proposal like this for Fourier Sampling

Recently Viewed Presentations

  • UWF Writing Lab Rules of Thumb for Possessives/Apostrophes

    UWF Writing Lab Rules of Thumb for Possessives/Apostrophes

    Writers use the apostrophe to substitute for the preposition of, by, with, or for: a doctor's appointment (appointment with the doctor) a week's notice (notice of one week) the children's toys (toys for the children) Presidents' Day (Day for [two]...
  • Bayesian Networks - Brunel University London

    Bayesian Networks - Brunel University London

    Data-Mining with Bayesian Networks on the Internet Section 1 - Bayesian Networks An Introduction Brief Summary of Expert Systems Causal Reasoning Probability Theory Bayesian Networks - Definition, inference Current issues in Bayesian Networks Other Approaches to Uncertainty Expert Systems 1...
  • 3D KMC Simulation in the Annealed Binary and

    3D KMC Simulation in the Annealed Binary and

    3D KMC Simulation in the Annealed Binary and Ternary Alloy Systems Xuan Zhang, Mengqi Huang Dept. of MatSE and Dept. of NPRE, UIUC May 11, 2010 Motivation Binary thin film alloy (Cu-Nb): large Nb precipitates ( > 40 nm) at...
  • Book Clubs -

    Book Clubs -

    Flush. The plot centers around Noah Underwood, a boy whose father enlists his help to catch a repeat environmental offender in the act. Noah Underwood's Dad failed to prove that the Coral Queen was dumping their waste in Thunder Beach.So...
  • Corporate Finance: Lecture Note Packet 1 The Objective and ...

    Corporate Finance: Lecture Note Packet 1 The Objective and ...

    Applied Corporate Finance Aswath Damodaran
  • Anti-Judaism and Anti-Semitism in the Middle Ages

    Anti-Judaism and Anti-Semitism in the Middle Ages

    In myrthe al nyght a bisy lyf they lede Til it was day… (314-319) Puns, Double Entendres, and Collapsing Distinctions in the Shipman's Tale II The end of the tale: For I wol paye yow wel and redily Fro day...
  • Research Questions and Subquestions

    Research Questions and Subquestions

    Research Questions and Subquestions Research Questions Over arching umbrella questions that address your topic. Include KEY TERMS that you can use to help you research your topic. Generally, research questions are questions you do not know the answer to. The...
  • Educating Our Children: The Critical Role of Parents

    Educating Our Children: The Critical Role of Parents

    Basic language and communication skills are formed during a child's first three years. Language experience before age 3 is an excellent predictor of reading ability in third grade. After 3 years of age, it is increasingly difficult to make up...