# Presentation: 051165

## The Limits of Quantum Computers(or: What We Can’t Do With Computers We Don’t Have)

**The Limits of Quantum Computers****(or: What We Can’t Do With Computers We Don’t Have)**

- Scott Aaronson (MIT)

**NP-complete**

## So then why can’t we just ignore quantum computing, and get back to real work?

## Because the universe isn’t classical

**

- Fancier version: **Extended Church-Turing Thesis**

## Shor’s factoring algorithm presents us with a choice

-  the Extended Church-Turing Thesis is false,
-  textbook quantum mechanics is false, or
-  there’s an efficient classical factoring algorithm.

- All three seem like crackpot speculations.
- At least one of them is true!

**Either**

## One-Slide Summary

- Quantum computing is not a panacea—and that makes it **more** interesting rather than less!
- On our current understanding, quantum computers could break RSA, simulate quantum dynamics, and do other important things, but  **not** solve “generic” search problems exponentially faster than classical computers
- 3. In this talk, I’ll tell you about some of what’s known about the capabilities and limits of quantum computers

## Quantum Computing

**Quantum Computing**

- The goal of quantum computing is to exploit this exponentiality in our description of the world

**Idea:** Get paths leading to wrong answers to “interfere destructively” and cancel each other out

## Shor’s Result

- Quantum computers can factor integers in polynomial time
- 	(thereby break RSA, thereby swipe 	your credit card number...)

- To prove this, Shor had to exploit a special property of the factoring problem	(namely its reducibility to *period-finding*)

- Ideas extend to computing discrete logarithms, solving Pell’s equation, breaking elliptic curve cryptography...

## Note: This square-root speedup is achievable, via “Grover’s algorithm”

- So the question remains: *can quantum computers solve NP-complete problems in polynomial time?*

**Bennett et al. 1997:** “Quantum magic” won’t be enough

- Suppose we throw away the problem structure, and just consider an abstract space of 2n possible solutions
- Then even a quantum computer will need ~2n/2 steps to find a correct solution

**Note:** This square-root speedup is achievable, via “Grover’s algorithm”

## Hi

- Hi

- Hamiltonian with easily-prepared ground state

- Hf

- Ground state encodes solution to NP-complete problem

- But it suffers from provable limitations of its own...
- [van Dam, Mosca, Vazirani 2001]: Eigenvalue gap can be exponentially small

## Another example of a “quantum black-box problem”: find a collision in a list of numbers

- 28  12  18  76  96  82  94  99  21  78  88  93  39  44  64  32  99  70  18  94  66  92  64  95  46  53  16  35  42  72  31  66  75  33  93  32  47  17  70  37  78  79  36  63  40  69  92  71  28  85  41  80  10  73  63  95  57  43  84  67  57  31  62  39  65  74  24  90  26  83  60  91  27  96  35  20  26  52  88  89  38  97  54  30  62  79  71  84  50  38  49  20  47  24  54  48  98  23  41  16  40  75  82  13  58  56  81  34  14  61  52  21  44  22  34  14  51  74  76  83  37  90  58  13  10  25  29  11  56  68  12  61  51  23  77  68  72  43  69  46  87  97  45  59  73  30  19  81  86  49  60  85  80  50  11  59  65  67  89  29  86  48  22  15  17  55  36  27  42  55  77  19  45  15  53  98  91  87  25  33

## What Could We Do With A Fast Quantum Algorithm For the Collision Problem?

**Solve Graph Isomorphism**by finding a collision in

****

- [A. 2002]: Any quantum algorithm needs at least ~N1/5 queries to find a collision in a list of size N
- [Shi, Kutin, Ambainis, Midrijanis]: Improved to ~N1/3 (which is optimal)

## What makes the problem so hard?

- Basically, that a quantum computer can **almost** find a collision after one query to f!

- Or: if only we could see the whole trajectory of a “hidden variable” coursing through the quantum system![A., *Phys. Rev. A* 2005]

- “If only we could now measure twice!”

- Previous techniques weren’t sensitive to the fact that quantum mechanics doesn’t allow these things

## Cartoon Version of Proof

- T-query quantum algorithm that finds collisions in 2-to-1 functions

- T-query quantum algorithm that distinguishes 1-to-1 from 2-to-1 functions

- Let p(f) = probability algorithm says f is 2-to-1

- Let q(k) = average of p(f) over all k-to-1 functions f

*[Beals et al. 1998]** p(f) is a multilinear polynomial, of degree at most 2T, in Boolean indicator variables ****(f(x),y)*

*Suppose it exists by way of contradiction...*

*Crucial facts:**q(k) **** [0,1] for all k=1,2,3,...**q(1) **** 1/3**q(2) **** 2/3*

## That’s why

**The magic step:** q(k) itself is a univariate polynomial in k, of degree at most 2T

- Why?

## q(k)

- 0

- 1

- 1

- 2

- 3

- .   .   .   .   .

- k

- .   .   .   .   .

- N2/5

- Bounded in [0,1] at integer points

## 5

- We want to find a **local minimum** of f, evaluating f as few times as possible

**5**

**4**

**4**

**3**

**2**

- [Aldous 1983] Randomized algorithm making 2n/2n queries[A., STOC’04] Quantum algorithm making 2n/3n1/6 queries

- [Aldous 1983] Any randomized alg needs 2n/2-o(n) queries[A., STOC’04] Any quantum alg needs 2n/4/n queries

- My lower-bound proof uses **Ambainis’s quantum adversary method**, which upper-bounds how much the entanglement between algorithm and oracle can increase via a single query

## Quantum Generosity ... Giving back because we careTM

**Surprising part:** “Quantum-inspired” argument also yields a better classical lower bound: 2n/2/n2
- Also yields the first randomized *or* quantum lower bounds for local search on constant-dimensional grid graphs

## “OK, so I accept that quantum computers have these limitations.  Is there any physical means to solve (say) NP-complete problems in polynomial time?”

## Famous proposal for how to solve NP-complete problems: Dip two glass plates with pegs between them into soapy water.  Let the soap bubbles form a “minimum Steiner tree” connecting the pegs

**Other proposals with obvious scaling problems:** protein folding, DNA computing, optical computing...

## “Relativity Computing”

**“****Relativity Computing”**

- DONE

**Variant: Black hole computing**

**Problem: Energy needed to accelerate to relativistic speed**

## Abrams & Lloyd 1998: If the Schrödinger equation were nonlinear, one could exploit that fact to solve NP-complete problems in polynomial time

- No solutions

- 1 solution to NP-complete problem

- One way to interpret this result: as additional evidence that the Schrödinger equation is linear...

## “Zeno Computing”

**Problem:** “Quantum foaminess”

**“****Zeno Computing”**

- Below the Planck scale, our picture of space and time breaks down in not-yet-understood ways...

## Scientific American, March 2008

***Scientific American*****, March 2008**

**www.scottaaronson.com**