Exploring Quantum vs Classical Algorithms: Bridging the Gaps
Delve into the research on the largest possible gaps between quantum and classical algorithms by Andris Ambainis and collaborators. Discover insights into models of computation, query algorithms, Grover's search, and more, highlighting the distinctions and advancements in quantum computing over classical methods.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
The largest possible gaps between quantum and classical algorithms Andris Ambainis University of Latvia Joint work with: Scott Aaronson, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs
Quantum vs. classical k quantum steps How many steps classically?
Models of Computation Deterministic Randomized | Quantum 2 / 39
Query algorithms Task: compute f(x1, ..., xN). Input variables xiaccessed via queries. i xi Complexity = number of queries.
Grovers search ... 0 1 0 x1x2 0 x3 xN Does there exist i:xi=1? Classically, N queries required. Quantum: O( N) [Grover, 1996].
Reasons to study query model Encompasses many quantum algorithms (Grover s search, quantum part of factoring, etc.). Provable quantum-vs-classical gaps.
Computation Models D:Deterministic (Decision Tree) x1 x2 x2 x3 x3 0 1 0 1 0 1 Complexity: on input: in total: path) tree) of the of the (length (depth Number of queries Worst input 2 or 3 3
Computation Models R: Randomized (Probability distribution on decision trees) x1 x2 x2 x3 x3 0 1 0 0 1 1 0 0 1 1 Complexity: on input: in total: Expected number of queries Worst input 8/3 2 or 8/3
Computation Models Quantum query model Q: Quantum (Quantum query algorithms) U1 UT U0 Q Q start U0, U1, , UT independent of x1, , xN. Q queries: |i (-1)xi|i .
Computation Models D deterministic (decision tree) R randomized R0 zero error; R1 one sided error; R2 bounded error; Q quantum QE exact; Q2 bounded error; Q2vs R2vs D?
Settings Partial functions: For some inputs (x1, ..., xN), the algorithm is allowed to output anything. Huge quantum speedups. Total functions: Prescribed anwer f(x1, ..., xN) for every (x1, ..., xN). Biggest quantum speedup: Grover.
Period finding x1, x2, ..., xN- periodic i xi Find period r 1 query quantumly 4N c queries classically
Our result [Aaronson, A] Task that requires 1 query quantumly, ( N/log N) classically. 1 query quantum algorithms can be simulated by O( N) query probabilistic algorithms.
FORRELATION = Fourier CORRELATION
High level idea Quantum Fourier transform hard to simulate classically. Task Input/output should be classical.
Forrelation Input: (x1, ..., xN, y1, ..., yN) {-1, 1}2N. Are vectors y x 1 1 y ... x ... 2 = 2 = F y N x x y N N highly correlated? FN Fourier transform over ZN.
More precisely ... Is the inner product 1 i , = F x y , x y i j i j N j at least 3/5 or at most 1/100?
Quantum algorithm 1. Generate a superposition of N x N 1 = i = i = , = i y i x i y i 1 (1 query). 2. Apply FNto 2ndstate. 3. Test if states equal (SWAP test).
Classical lower bound Theorem Any classical algorithm for FORRELATION uses log N N queries.
Simulating 1 query quantum algorithms
Simulation Theorem Any 1 query quantum algorithm can be simulated probabilistically with O( N) queries.
Overview | x1x2+4x2x4-x3x4+x3x5 Sampling
Analyzing query algorithms U1 Q UT Q Q 1,1|1,1 + 1,2|1, 2 + + N, M|N, M i,jis actually i,j(x1, ..., xN)
Polynomials method Lemma [Beals et al., 1998] After k queries, the amplitudes ( j i x ..., , ) , x 1 N are polynomials in x1, ..., xNof degree k. ( ) 2 , ..., x x Measurement: , 1 i j N Polynomial of degree 2k
Our task Pr[A outputs 1] = p(x1, ..., xN), deg p =2. 0 p(x1, ..., xN) 1. Task: estimate p(x1, ..., xN) with precision . Solution: random sampling.
Pre-processing Problem: some xi s in p(x1, ..., xN) may be more influential than others. ... influential xi several less influential xi
Sampling Requires sampling N variables xi! sampled a x x Estimator: , i j i j ( , ) i j Good if we sample N of N2terms independently.
Sampling 2 x1 x2 x3 x4 x5 x6 x7 N variables N N = N terms x5x6 x4 x3 x2 x1 x7 N
Extension to k queries Theorem k query quantum algorithms can be simulated probabilistically with O(N1-1/2k) queries. Proof: Algorithm polynomial of degree 2k; Random sampling. Question: Is this optimal?
Forrelation: given black box functions f(x) and g(y), estimate y x , ( ) ( ) F f x g y , x y k-fold forrelation: given f1(x), ..., fk(x), estimate k x x ,..., 1 ( ) ( ) ... ( ) f x F f x F f x 1 1 , 2 2 , x x x x k k 1 2 2 3
Results Theorem k-fold forrelation can be solved with k/2 quantum queries. Conjecture k-fold forrelation requires (N1-1/k) queries classically.
Open problem 1 Does k-fold FORRELATION require (N1-1/2k) queries classically? Plausible but looks quite difficult matematically.
Open problem 2 Best quantum-classical gaps: 1 quantum query - ( N/log N) classical queries; 2 quantum queries - ( N/log N) classical; ... log N quantum queries - queries. ( ) Nlog N classical Any problem that requires O(log N) queries quantumly, (Nc), c>1/2 classically?
Why total functions? Partial functions: huge quantum advantages ... achieved by ignoring the inputs where quantum algorithm does not provide a conclusive answer. What if the algorithm has to output a conclusive answer for every (x1, ..., xN)?
Quantum vs Classical The biggest known speedup: Grover s search on N elements (1996); Q2=O( N), R2=D=N. Our result*: Q2=O( 4?), D=N. * up to log N factors
Randomized vs Deterministic The biggest known gap: Binary AND-OR tree (Snir, 1996). R0=O(N0.7537...), D=N. Our result*: R0=O( N), D=N. * up to log N factors
Two notes 4th power gap between D and Q: D=N, Q2=O( Quantum-vs-randomized gap still quadratic (Grover). [Aaronson, Ben-David, Kothari, 2016]: Q2=O((?2)2/5). 4?).
Goal Communication vs. Partition number. f with following properties: D large; f=1 can be certified by values for a small number of variables. Certificates are unambiguous.
D versus 1-certificates Function of nm variables f=1 iff there exists unique all-1 column 1 1 1 1 1 1 1 1 0 0 n D=nm 0 0 0 0 0 m short 1-certificates BUT not unambiguous.
D versus 1-certificates Function of nm variables f=1 iff there exists unique all-1 column 1 1 1 1 1 1 1 1 0 0 n D=nm 0 0 0 0 0 m Should specify which 0 to choose from each column
Pointers 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 f=1 iff there is an all-1 column b, in b there is a unique r with non-zero pointer, following the pointers from r, we traverse exactly one zero in all other columns.
Pointers 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 D = nm and unambiguous short 1-certificates.
Features Highly elusive (flexible) Still traversable (if know where to start).
Binary Tree Instead of a list 0 0 0 0 1 0 0 0 we use a balanced binary tree 1 0 0 0 0 0 0 0 More elusive Random access
