limits

100 %
0 %
Information about limits
Entertainment

Published on November 28, 2007

Author: Herminia

Source: authorstream.com

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

Add a comment

Related presentations

Related pages

Limit (mathematics) - Wikipedia, the free encyclopedia

In mathematics, a limit is the value that a function or sequence "approaches" as the input or index approaches some value. [1] Limits are essential to ...
Read more

Limit – Wikipedia

Limit (von franz. limite und lat. limes: "Grenzweg, Grenze, Grenzwall") steht für. das im Hochleistungssport und/oder Extremsport maximal Erreichbare ...
Read more

Limit of a function - Wikipedia, the free encyclopedia

In mathematics, the limit of a function is a fundamental concept in calculus and analysis concerning the behavior of that function near a particular input.
Read more

Limit (Roman) – Wikipedia

Limit ist ein Roman des deutschen Schriftstellers Frank Schätzing, der Anfang Oktober 2009 im Verlag Kiepenheuer & Witsch erschien. Zentrales Thema des ...
Read more

Limits (An Introduction) - Math is Fun - Maths Resources

Limits (An Introduction) Approaching ... Sometimes we can't work something out directly ... but we can see what it should be as we get closer and closer!
Read more

limit – Wiktionary

... The government limits the amount of food. Die Regierung schränkt die Nahrungsmenge ein. [2] I have been asked to limit my speech to ten minutes maximum.
Read more

dict.cc | Limit | Wörterbuch Englisch-Deutsch

Übersetzung für Limit im Englisch-Deutsch-Wörterbuch dict.cc.
Read more

Limits Spiel | Limits kaufen - Brettspiele, Kartenspiele ...

Limits das Spiel hier für 2,99EUR günstig bestellen. Zuletzt aktualisiert am 04.02.2016. Nur hier mit Spielregeln auf Video.
Read more

Limit | Define Limit at Dictionary.com

noun 1. the final, utmost, or furthest boundary or point as to extent, amount, continuance, procedure, etc.: the limit of his experience; the limit of ...
Read more

Limitis - Internet-Lösungen aus Südtirol

Zuverlässige Internet-Dienste aus Südtirol: Webhosting, E-Mail, WLAN-Hotspots, Backup-Lösungen und Server-Housing. Überzeugen Sie sich selbst!
Read more