Quantum vs. Classical Computing: Exploring Forrelation Problem
undefined
Forrelation: A Problem that Optimally
Separates Quantum from Classical
Computing
Quantum vs. classical
1 query quantumly
How many queries
classically?
Total vs. partial functions
Total functions
f(x
1
, ..., x
N
)
:
R = O(Q
2.5
)
[previous talk];
D = O(Q
4
)
[yesterday];
Partial functions
f(x
1
, ..., x
N
)
:
Much bigger gaps possible.
Period finding
x
1
, x
2
, ..., x
N
- periodic
i
x
i
Find period
r
[Shor, 1994]:
1
query quantumly
Period-finding
Quantum algorithm works if
N
r
2
.
T
classical queries – can test
T
2
possible periods.
i
x
i
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 =
F
ourier C
ORRELATION
Forrelation
Input:
(x
1
, ..., x
N
, y
1
, ..., y
N
)
{-1, 1}2N
.
Are vectors
highly correlated?
highly correlated?
F
F
N
N
– Fourier transform over
– Fourier transform over
Z
Z
N
N
.
.
More precisely...
Is the inner product
3/5
or
1/100
?
Quantum algorithm
1.
Generate a superposition of
(
1
query).
2.
Apply
F
N
to 2
nd
state.
3.
Test if states equal (
SWAP
test).
Classical lower bound
Theorem
Any classical algorithm
for
FORRELATION
uses
queries.
REAL FORRELATION
Distinguish between
random (
x
i
’s,
y
i
’s - Gaussian);
random,
.
Real-valued vectors
Lower bound
Claim
REAL FORRELATION requires
queries.
Intuition
: if
, each variable –
Gaussian, correlations between
x
i
’s and
y
j
’s - weak.
o(
N/log N)
values
x
i
and
y
j
uncorrelated random variables.
Reduction
Proof idea
: Replace
x
i
sgn(x
i
)
to
achieve
x
i
{-1, 1}.
T
query algorithm
for
FORRELATION
T
query algorithm for
REAL
FORRELATION
Simulating 1 query quantum
algorithms
Simulation
Theorem
Any
1
query quantum
algorithm can be simulated
probabilistically with
O(
N)
queries.
Analyzing
query
algorithms
Q
Q
Q
U
T
…
U
1
1,1
1,1
|1
|1
,1
,1
+
+
1,2
1,2
|
|
1,
1,
2
2
+
+
…
…
+
+
N, M
N, M
|N
|N
, M
, M
i,j
i,j
is actually
is actually
i,j
i,j
(x
(x
1
1
, ..., x
, ..., x
N
N
)
)
Polynomials method
Lemma
[Beals et al., 1998] After
k
queries,
the amplitudes
are polynomials in
x
1
, ..., x
N
of degree
k
.
Measurement:
Polynomial of degree
2k
Our task
Pr[
A
outputs
1
] =
p(x
1
, ..., x
N
)
,
deg p =2
.
0
p(x
1
, ..., x
N
)
1
.
Task: estimate
p
(x
1
, ..., x
N
)
with
precision
.
Solution: random sampling
.
Pre-processing
Problem
: large error if sampling omits
x
i
with large influence in
p(x
1
, ..., x
N
)
.
Solution
: replace influential
x
i
’s by
several variables with smaller
influence.
Sampling 1
Good if we s
ample
ample
N
N
of
of
N
N
2
2
terms
terms
independently.
independently.
Estimator:
Requires sampling
N variables x
i
!
Sampling 2
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
5
x
6
x
7
x
4
x
3
x
2
x
1
N variables
N
N
N = N
terms
Extension to
k
queries
Theorem
k
query quantum algorithms
can be simulated probabilistically with
O(N
1-1/2k
)
queries.
Proof:
Algorithm
polynomial of degree
2k
;
Random sampling.
Question:
Is this optimal?
k
-fold forrelation
Forrelation
: given black box functions
f(x)
and
g(y)
, estimate
k
-fold forrelation
: given
f
1
(x), ..., f
k
(x)
,
estimate
Results
Theorem
k
-fold forrelation can be
solved with
k/2
quantum queries.
Conjecture
k
-fold forrelation requires
(N
1-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
(N
1-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 -
classical
queries.
Any problem that requires
O(log N)
queries
quantumly,
(N
c
), c>1/2
classically?
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.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
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?
