Quantum vs. Classical Computing: Exploring Forrelation Problem
Delve into the world of quantum and classical computing with the Forrelation problem that optimally separates the two realms. From Fourier correlations to quantum algorithms and classical lower bounds, explore the intricacies of distinguishing between quantum and classical computation through various tasks and algorithms.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing SCOTT AARONSON (MIT), SCOTT AARONSON (MIT), ANDRIS AMBAINIS (UNIV. OF LATVIA) ANDRIS AMBAINIS (UNIV. OF LATVIA)
Quantum vs. classical 1 query quantumly How many queries classically?
Total vs. partial functions Total functions f(x1, ..., xN): R = O(Q2.5) [previous talk]; D = O(Q4) [yesterday]; Partial functions f(x1, ..., xN): Much bigger gaps possible.
Period finding x1, x2, ..., xN - periodic i xi Find period r [Shor, 1994]: 1 query quantumly
Period-finding i xi Quantum algorithm works if N r2. T classical queries can test T2 possible periods. queries classically
Our result 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
Forrelation Input: (x1, ..., xN, y1, ..., yN) {-1, 1}2N. Are vectors highly correlated? FN Fourier transform over ZN.
More precisely... Is the inner product 3/5 or 1/100?
Quantum algorithm 1. Generate a superposition of 2. Apply FN to 2nd state. 3. Test if states equal (SWAP test). (1 query).
Classical lower bound Theorem Any classical algorithm for FORRELATION uses queries.
REAL FORRELATION Real-valued vectors Distinguish between random (xi s, yi s - Gaussian); random, .
Lower bound Claim REAL FORRELATION requires queries. Intuition: if Gaussian, correlations between xi s and yj s - weak. o( N/log N) values xi and yj uncorrelated random variables. , each variable
Reduction T query algorithm for FORRELATION T query algorithm for REAL FORRELATION Proof idea: Replace xi sgn(xi) to achieve xi {-1, 1}.
Simulating 1 query quantum algorithms
Simulation Theorem Any 1 query quantum algorithm can be simulated probabilistically with O( N) queries.
Analyzing query algorithms U1 Q UT Q Q 1,1|1,1 + 1,2|1, 2 + + N, M|N, M i,j is actually i,j(x1, ..., xN)
Polynomials method Lemma [Beals et al., 1998] After k queries, the amplitudes are polynomials in x1, ..., xN of degree k. Measurement: 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: large error if sampling omits xi with large influence in p(x1, ..., xN). Solution: replace influential xi s by several variables with smaller influence.
Sampling 1 Requires sampling N variables xi! Estimator: Good if we sample N of N2 terms 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 k-fold forrelation: given f1(x), ..., fk(x), estimate
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 FORRELATION - the biggest gap between quantum from probabilistic. Provides a precise meaning for QFT is hard to simulate classically . Can we find an application for it?
Open problem 2 Does k-fold FORRELATION require (N1-1/2k) queries classically? Plausible but looks quite difficult matematically.
Open problem 3 Best quantum-classical gaps: 1 quantum query - ( N/log N) classical queries; 2 quantum queries - ( N/log N) classical; ... log N quantum queries - queries. classical Any problem that requires O(log N) queries quantumly, (Nc), c>1/2 classically?
