# The Complexity of Sampling Histories Scott Aaronson, UC Berkeley August 5, 2003.

## Presentation on theme: "The Complexity of Sampling Histories Scott Aaronson, UC Berkeley August 5, 2003."— Presentation transcript:

The Complexity of Sampling Histories Scott Aaronson, UC Berkeley http://www.cs.berkeley.edu/~aaronson August 5, 2003

Words You Should Stop Me If I Use polysize oracle relativizing zero-knowledge #P-complete nonuniform Words Ill Stop You If You Use holonomy gauge SU(2) intertwinor kinematical Lagrangian Words To Be Careful With loop string

Outline Why you should stay up at night worrying about quantum mechanics Dynamical quantum theories Solving Graph Isomorphism by sampling histories Search in N 1/3 queries (but not fewer)

What we experience Quantum mechanics

Assumption Time Quantum state of the universe You

A Puzzle Let|O R = you seeing a red dot |O B = you seeing a blue dot What is the probability that you see the dot change color?

The Goal Quantum state Probability distribution Unitary matrix Stochastic matrix

Why Look for This? Quantum theory says nothing about multiple-time or transition probabilities Then what is a prediction, or the output of a computation, or the utility of a decision? Reply: But we have no direct knowledge of the past anyway, just records

Bohms Theory Gives a deterministic evolution rule for particle positions and momenta Mathematicianly approach: Study the set of all discrete dynamical rules, without presupposing one of them is true But doesnt make sense for discrete observables:

Our Results We give evidence that by examining a history, one could solve problems that are intractable even for a quantum computer - Graph Isomorphism and Approximate Shortest Lattice Vector in polynomial time - Unordered search in N 1/3 steps instead of N 1/2 We define dynamical theories for obtaining classical histories, and investigate what axioms they can satisfy We obtain the first model of computation slightly more powerful than quantum computing

Dynamical Theory Must marginalize to single-time probabilities of quantum mechanics: diagonal entries of and U U -1 Fix an N-dimensional Hilbert space (N finite) and orthogonal basis Given an N N unitary U and state acted on, returns a stochastic matrix

Axiom: Symmetry D is invariant under relabeling of basis states:

Axiom: Indifference If U acts onand is the identity on H 2, then S should also be the identity on H 2 Can formalize without tensor products: partition U into minimal blocks of nonzero entries Not the same as commutativity:

Theorem: No dynamical theory satisfies both indifference and commutativity Proof: Suppose A and B share an EPR pair U A applies /8 rotation to first qubit, U B applies - /8 to second qubit. Consider probability p of being at |00 initially and |10 at the end If U A applied first:If U B applied first:

Axiom: Robustness Small (1/poly(N)) change to or U Small (1/poly(N)) change to joint probabilities matrix, S·diag( ) Arguably thats needed for any physical theory or model of computation

Example 1: Product Dynamics Symmetric, robust, commutative, but not indifferent Take probabilities at any two times to be independent of each other

Example 2: Dieks Dynamics Symmetric, indifferent, but not commutative or robust Partition U into minimal blocks, then apply product dynamics separately to each

Theorem: Suppose Then there is a weight-1 flow through the network where flow through an edge cant exceed the edges capacity

Proof Idea: By the Max-Flow-Min-Cut Theorem (Ford-Fulkerson 1956), it suffices to show that any set of edges separating s from t (a cut) has total capacity at least 1. Let A,B be right, left edges respectively not in cut C. Then the capacity of C is so we need to show Fix U and consider maximum of right-hand side. Equals the max eigenvalue of a positive semidefinite matrix, which we can analyze using some linear algebra…

Example 3: Flow Dynamics Using the previous theorem, we construct a dynamical theory that satisfies the symmetry, indifference, and robustness axioms Not obvious a priori that any such theory exists

Model of Computation Oracle chooses a symmetric robust indifferent theory D adversarially, then returns a sample from D Polynomial-time classical computation, with one query to a history oracle Oracle takes as input descriptions of quantum circuits U 1,…,U T Any dynamical theory D induces a distribution D over classical histories for At least as powerful as standard quantum computing

The Graph Isomorphism Problem Decide whether two graphs G and H are isomorphic The best known algorithm takes about time n = number of vertices But we dont think Graph Isomorphism is NP-complete Intuitively, its only as hard as counting collisions in Could be easier than finding a needle in a haystack!

The Collision Problem Given a list of N numbers x 1,…,x N, youre promised that either every number occurs once, or every number occurs twice. Decide which. Best classical algorithm makes ~ queries (birthday paradox) Brassard, Høyer, Tapp 1997 gave a quantum algorithm that makes ~N 1/3 queries Is there a faster quantum algorithmsay, log N queries? If so, wed get a polynomial-time quantum algorithm for Graph Isomorphism! 3 6 1 5 4 2 vs. 6 2 2 5 6 5

The Collision Problem (cont) Aaronson 2002: Any quantum algorithm needs at least ~N 1/5 queries Improved by Shi to ~N 1/3 queries Previously, couldnt even rule out constant number of queries! Proofs use multivariate polynomials Implications: No dumb quantum algorithm for Graph Isomorphism Oracle separation between the complexity classes BQP (Bounded-Error Quantum Polynomial-Time) and DQP (Dynamical Quantum Polynomial-Time)

P Polynomial Time BQP Quantum Polynomial Time DQP My New Class NP Satisfiability, Traveling Salesman, etc. Factoring Graph Isomorphism Approximate Shortest Vector Conjectured World Map

Solving the Collision Problem by Sampling Histories GOAL: When we inspect the classical history, see both |i and |j with high probability Suppose every number occurs twice. Then Measurement of 2 nd register Two bitwise Fourier transforms

Solving the Collision Problem by Sampling Histories (cont) Theorem: Under any dynamical theory satisfying the symmetry and indifference axioms, the first Fourier transform makes the hidden variable forget whether it was at |i or |j. So after the second Fourier transform, it goes to |i half the time and |j half the time; thus with ½ probability we see both |i and |j in the history Proof Idea: Use symmetry axiom, together with automorphisms of Indifference axiom needed to trace out second register

Finding a Marked Item in N 1/3 Queries N 1/3 iterations of Grovers quantum search algorithm Probability of observing the marked item after T iterations is ~T 2 /N Hidden variable

N 1/3 Search Algorithm Is Optimal Bennett, Bernstein, Brassard, Vazirani 1996: If a quantum computer searches a list of N items for a single randomly-placed marked item, the probability of observing the marked item after T steps is at most So probability of observing it in a history of the first T steps is at most

Summary: If your whole life flashed before you in an instant, and if youd prepared for this by putting your brain in certain superpositions, then (under reasonable axioms) you could solve Graph Isomorphism in polynomial time Contrast: Nonlinear quantum mechanics would put Satisfiability and even harder problems in polynomial time (Abrams and Lloyd 1998) But probably still not Satisfiability

Postulate: NP-complete problems cant be efficiently solved in physical reality The postulate does not imply your whole life couldnt flash before you in an instant Justification for the postulate: Maybe Im wrong, but then Id be too busy solving NP- complete problems to care that I was wrong (1) Quantum states evolve linearly (2) We cant make unlimited-precision measurements (3) The self-sampling anthropic principle (Bostrom 2000) is false (4) Constraints on quantum gravity? What does the postulate imply? (under plausible complexity assumptions)

Download ppt "The Complexity of Sampling Histories Scott Aaronson, UC Berkeley August 5, 2003."

Similar presentations
{"extraction_info": {"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8664808869361877, "perplexity": 2188.0184003256863}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2018-34/segments/1534221211935.42/warc/CC-MAIN-20180817084620-20180817104620-00269.warc.gz"}