limits

Limits on Efficient Computation in the Physical World: 

Limits on Efficient Computation in the Physical World Dissertation Talk Scott Aaronson

The Computer Science Picture of Reality: 

The Computer Science Picture of Reality Quantum computing challenges this picture That’s why everyone should care about it, whether or not quantum factoring machines are ever built 

PLAN OF TALK: 

PLAN OF TALK Part I: Limitations of Quantum Computers A lower bound extravaganza Part II: Models and Reality Is the quantum computing model too powerful? Or not powerful enough?

What Quantum Mechanics Says: 

What Quantum Mechanics Says If an object can be in two states |0 or |1, then it can also be in a superposition |0 + |1 Here  and  are complex amplitudes satisfying ||2+||2=1

Slide6: 

To modify a state we can multiply vector of amplitudes by a unitary matrix—one that preserves

Slide7: 

We’re seeing interference of amplitudes—the source of “quantum weirdness”

Slide8: 

A quantum state of n “qubits” takes 2n complex numbers to describe: Quantum Computing The goal of quantum computing is to exploit this exponentiality in Nature.

Slide10: 

Background The gospel according to Shor Part I: Limitations of Quantum Computers A lower bound extravaganza Part II: Models and Reality Is the quantum computing model too powerful? Or not powerful enough?

The Quantum Black Box Model: 

The Quantum Black Box Model I do believe it Against an oracle. —Shakespeare, The Tempest

Slide12: 

We count only the number of queries to an oracle, not the number of computational steps Example: Given a function f:{0,1}n{0,1}, decide if there’s an x such that f(x)=1 Like solving an NP-complete problem by brute force Classically, ~2n queries to f needed Grover’s algorithm uses only ~2n/2 BBBV 1997: Grover is optimal Provides evidence that NP  BQP Without oracle results, we don’t understand anything All known quantum algorithms are oracle algorithms What about IP=PSPACE? Do I believe Against an oracle? The proof of the pudding is in the proving

Slide13: 

Algorithm’s state: x: location to query w: “workspace” qubits After a query transformation: Between two queries, we can apply an arbitrary unitary matrix that doesn’t depend on f Complexity = minimum number of queries needed to achieve for all oracles f

Problem: Find 2 numbers that are the same (each number appears twice): 

Problem: Find 2 numbers that are the same (each number appears twice) 28 12 18 76 96 82 94 99 21 78 88 93 39 44 64 32 99 70 18 94 82 92 64 95 46 53 16 35 42 72 31 40 75 71 93 32 47 11 70 37 78 79 36 63 40 69 92 71 28 85 41 80 10 52 63 88 57 43 84 67 57 31 98 39 65 74 24 90 26 83 60 91 27 96 35 20 26 52 95 65 66 97 54 30 62 79 33 84 50 38 49 20 47 24 54 48 98 23 41 16 66 75 38 13 58 56 86 34 73 61 73 21 44 62 34 14 51 74 76 83 37 90 58 13 10 25 29 25 56 68 12 11 51 23 77 68 72 43 69 46 87 97 45 59 14 30 19 81 81 49 60 85 80 50 61 59 89 67 89 29 86 48 22 15 17 55 36 27 42 55 77 19 45 15 53 22 91 87 17 33 By “birthday paradox”, a randomized algorithm must examine N of the N numbers Brassard, Høyer, Tapp: quantum algorithm (based on Grover) that makes N1/3 queries Is that optimal? Proving a lower bound better than constant was open for 5 years

Motivation for the Collision Problem: 

Motivation for the Collision Problem

Slide16: 

A., STOC’02: N1/5 lower bound on quantum query complexity of the collision problem Improved to N1/3 and generalized by Shi, Kutin, Ambainis, and Midrijanis

Proof Sketch (only one in the talk): 

Proof Sketch (only one in the talk) T-query quantum algorithm that finds collisions in 2-to-1 functions T-query algorithm that distinguishes 1-to-1 from 2-to-1 functions

Proof Sketch (only one in the talk): 

Proof Sketch (only one in the talk) q(g) 0 1 1 2 3 . . . . . g . . . . . N Large derivative Bounded in [0,1] A. A. Markov’s Inequality implies such a polynomial must have large degree

Direct Product Theorem for Quantum Search: 

Direct Product Theorem for Quantum Search A., CCC’04: With few (N) queries, the probability of finding all K marked items is 2-(K) Proof uses polynomial method Corollary 1: Exists oracle relative to which NP  BQP/qpoly (BQP/qpoly = BQP with polynomial-size “quantum advice”) Corollary 2: Fixes wrong result of Klauck on quantum time-space tradeoffs for sorting N items, K of them marked

Can quantum ideas help us prove classical lower bounds?: 

Can quantum ideas help us prove classical lower bounds? Quantum Generosity … Giving back because we careTM Examples: Kerenidis & de Wolf 2003, Aharonov & Regev 2004 Local Search: Given oracle access to f:{0,1}nZ, find a local minimum of f using as few queries as possible 5 4 4 3 2

Can quantum ideas help us prove classical lower bounds?: 

Proof technique based on Ambainis’ quantum adversary method Can quantum ideas help us prove classical lower bounds? Technique also yields 2n/2/n2 randomized lower bound First lower bounds (randomized or quantum) for constant-dimensional grid graphs 0-inputs 1-inputs 0-inputs 1-inputs Each query only separates 0-inputs from 1-inputs by so much

More Fun With Ambainis’ Adversary Method: 

More Fun With Ambainis’ Adversary Method A. 2003: Bernstein-Vazirani “recursive Fourier sampling” algorithm is optimal—need to uncompute garbage presents a fundamental barrier A., CCC’03: For all total Boolean f:{0,1}n{0,1}, R0(f) = O(Q0(f) Q2(f)2 log n) where R0 = zero-error randomized query complexity of f, Q0 = zero-error quantum, Q2 = bounded-error quantum

Summary: 

Summary The Art of the Quantum Lower Bound Polynomials and adversaries—the dynamic duo Techniques even applied classically Quantum computing is not a panacea Many problems still intractable: NP, collision-finding, local search, total Boolean functions, … Even with quantum advice Quantum computing  exponential parallelism Popular articles get this wrong Because of linearity, one “parallel universe” can’t shout above the others

Slide24: 

Background The gospel according to Shor Part I: Limitations of Quantum Computers A lower bound extravaganza Part II: Models and Reality Is the quantum computing model too powerful? Or not powerful enough?

Slide25: 

Is quantum mechanics merely an approximation to a classical theory?

Slide26: 

A., 2002: Wolfram’s thread hypothesis can’t be reconciled with relativity of simultaneity Is quantum mechanics merely an approximation to a classical theory?

Slide27: 

Is quantum computing just obvious baloney? Leonid Levin: “We have never seen a physical law valid to over a dozen decimals” Oded Goldreich: Exponentially long vectors  exponential time to manipulate

Sure/Shor separators: 

My response: What criterion separates the quantum states that suffice for factoring from the states we’ve already seen? Sure/Shor separators DIVIDING LINE

Slide29: 

A., STOC’04 proposes a complexity classification of quantum states to help answer this question Main result: States arising in quantum error-correction take n(log n) additions and tensor products to express Proof applies Ran Raz’s breakthrough lower bound on multilinear formula size

Are quantum states really “exponential-sized objects”?: 

Are quantum states really “exponential-sized objects”? A., CCC’04: Given f:{0,1}n{0,1}m{0,1} (partial or total), D1(f) = O(m Q1(f) logQ1(f)) D1(f) = deterministic 1-way communication complexity Q1(f) = bounded-error quantum 1-way complexity (contrast with Bar-Yossef, Jayram, Kerenidis 2004) Corollary: BQP/qpoly  PP/poly

Slide31: 

Marked item Grover Search of a Physical Region “Quantum robot”

Slide32: 

Benioff 2001: Each of the N Grover iterations takes N time, just to move the robot across the grid. So no improvement over classical A., Ambainis, FOCS’03: Sadly, no lower bound… Using divide-and-conquer, can search d-dimensional cube in N log2N time for d=2, or N for d3 Corollary: O(N)-qubit disjointness protocol Grover Search of a Physical Region My motivation: What computational limitations are imposed by the speed of light being finite? Or the holographic principle (any region containing 1.41069 bits per meter2 of surface area collapses to a black hole)?

Foolproof Way to Solve NP Complete Problems Efficiently: 

Foolproof Way to Solve NP Complete Problems Efficiently Guess a random solution by measuring electron spins. If solution is wrong, kill yourself Let PostBQP (Postselected Bounded-Error Quantum Polynomial-Time) be class of problems solvable this way A., 2004: PostBQP = PP (believed that NP  PP) Corollary: Numerous “small” changes to quantum mechanics would let us solve PP-complete problems—nonunitary matrices, ||p for p2, … |0000 |0001 |0010 |0011 |0100 |0101 |0110 |0111 |1000 |1001 |1010 |1011 |1100 |1101 |1110 |1111 |1010

Slide35: 

What we experience Quantum mechanics

Slide36: 

Time Quantum state of the universe Stochastic Hidden-Variable Theories

Slide37: 

Let DQP (Dynamical Quantum Polynomial-Time) be the class of problems you could then solve efficiently (assuming transition probabilities satisfy two reasonable axioms—symmetry and locality) Also, you could search an N-item array in N1/3 steps instead of N1/2 But not fewer: NP  DQP relative to an oracle Suppose your whole life history flashed before you in an instant

Concluding Remarks: 

Concluding Remarks The Ogre of Intractability: Not even quantum computers escape Lower bound techniques “unreasonably effective” Challenge for quantum computing skeptics Give us a better picture of the world Computer science and fundamental physics: a match made in Hilbert space New perspective forces us to take QM seriously Insights into hidden variables, postselection, holographic entropy bound, … Computational input to quantum gravity? Intractability as a physical axiom?

THANK YOU: 

THANK YOU