Transcript Slide 1

Quantum Computing
MAS 725
Hartmut Klauck
NTU
9.4.2012
Today

Lower bounds in the black box model
 polynomial method
 adversary method
The black box model



Input x1,…,xn with query access
We want to compute some function f(x1,…,xn)
Examples:
 Deutsch‘s problem: x1,x2 are the values g(0) and
g(1) for a function g, we want to know if g is
balanced
) Compute parity of x1,x2
 Grover: Find i mit xi=1, consider f=OR
The black box model


We measure the number of queries an algorithm
does in the worst case, cost of an algorithm
 Not time, space etc.
The query complexity of a function f is the minimal
cost of an algorithm computing f
Types of algorithms



Deterministic algorithms: classical, no error, the
complexity is denoted D(f)
Randomized algorithms: allow error probability
1/3, over the randomness of the algorithm,
complexity R(f)
Quantum algorithms:
 We count the number of quantum queries.
 With error 1/3: Q(f)
 Withour error: QE(f)
Examples



We know some bounds already:
 QE(XOR2)=1, but R(XOR2)=2
 QE(XORn)· d n/2e
 Q(OR)=O(n1/2)
 R(OR)=(n)
 Q(OR)=(n1/2)
How can we show quantum lower bounds in general?
How much better can quantum algorithms be compared to
randomized algorithms?
Examples




We showed the lower bound for OR with an
adversary argument
Are there other more general techniques?
For certain problems (Simon, Period Finding) we
have seen exponential speedups
What is the largest speedup for a total Boolean
function?
What is the hardest function?



Consider ID: ID(x)=x
How many queries are needed to compute ID?
R(ID)=n
 We get no information on a position we do not
query
 Formally: apply the Yao principle: fix random
string, then a deterministic algo with n-1 queries
must have error 1/2.
Q(ID)·

1/2
n/2+O(n )
Ansatz:
 We use the sign oracle (-1)xi |ii
 Formula for Hadamard transform:





Another Hadamard maps back to |xi
So suffices to generate this superposition
Doing this exactly needs n queries
Number of queries corresponds to |y|
Use only y with|y|· n/2+O(n1/2)
Algorithm




Generate uniform superposition over all y with
|y|· n/2+O(n1/2)
On |yi query all bits xi with yi=1
Apply Hadamard
Success probability?
 99% of all strings have Hamming weight at most
n/2+O(n1/2)
 Hence resulting superposition is close to the
desired one and we will have small error
 For example error 5% with n/2+n1/2 queries
Conclusion


n/2· Q(ID)· n/2+n1/2
...if we can show Q(XOR)¸ n/2
The polynomial method



A quantum black box algorithm is a sequence of
unitaries and query unitaries
We construct a low degree polynomial from such an
algorithm that represents the computed function
Then we analyze the minimum degree for such
polynomials
The polynomial method


We claim that the amplitudes of the final state of a T query algorithm
can be written as polynomials of degree T
Proof by induction:
 T=0: amplitudes do not depend on the input, i.e. are constants
 T! T+1: i(x) is given by a degree T polynomial
 Next we apply a unitary that does not depend on x
 The new ®i(x) is a linear combination of degree T polynomials,
degree unchanged
 The query transformation: state |ii|ai|ki maps to |ii|a© xii|ki
 The new iak(x) is xi¢ i, a©1, k + (1-xi)¢ i, a, k
 Degree is no more than T+1
The polynomial method




The acceptance probability on input x is the sum of
squred amplitudes
Hence can be written as a polynomial of degree 2T
We may replace xik by xi
The result is multilinear
Conclusion



Given a quantum algorithm with T queries that
computed f exactly we get a multilinear polynomial
of degree 2T that satisfies p(x)=f(x) for all x.
If the quantum algorithm has error 1/, then there is
a polynomial with p(x)2[0,1/3] for f(x)=0 and
p(x)2[2/3,1] for f(x)=1
Now we have to consider the degree of polynomials
representing Boolean functions
Exact quantum algorithms

For every total Boolean function f there is a unique
multilinear polynomial that represents f exactly
deg(f) denotes the degree of this polynomial
QE(f)¸ deg(f)/2
Example: XOR, the polynomial is

Degree is n, and QE(XOR) =n/2



Multilinear polynomials

Claim: For every Boolean function there is a unique multilinear
polynomial, which represents f exactly, i.e. f(x)= p(x) for all
Boolean x. Proof:
 Assume f(x)=p(x)=q(x) for alle Boolean x, yet pq
 Then p-q is a multilinear polynomial for g(x)=0, and p-q is
not the zero polynomial
 Take a minimum degree monomial m in p-q with nonzero
coefficient a0.
 Let z be the string string, that contains all xi in m as ones,
and contains no other ones
 m(z)=1, and p(z)=a, contradiction
Another example

Polynomial for OR:

Also has degree n

Hence QE(OR)¸ n/2

But actually QE(OR)=n
QE(OR)







We consider the amplitudes of the final state of an optimal
algorithm for OR (no error), as polynomials of degree T
Basis states |0yi are rejecting.
B is the set of those
For i in B we have pi(x)=0 when x is not 0n
There is a j in B with pj(0n) 0
Consider the real part q(x) on
1-pj(x)/pj(0n)
Then: deg (q) · T = QE(OR) and q(0n)=0 and q(x)=1 for other x,
hence deg(q)¸ deg(OR) = n
Some facts about polynomials




If a Boolean f depends on n variables, we have
deg(f)¸ log n - loglog n
All symmetric, nonconstant f have degree n-o(n)
Hence QE(f)¸ (log n)/2 –o(log n)
And QE(f)¸ n/2-o(n) for symmetric nonconstant f
Approximating polynomials

Given a quantum algorithm with T queries that we
get a multilinear polynomial of degree 2T with
p(x)2[0,1/3] for f(x)=0 and p(x)2[2/3,1] for f(x)=1

adeg(f) denotes the minimal degree of such a
polynomial
Then: Q(f)¸ adeg(f)/2
Example OR on 2 bits: x1/3 + x2/3 + 1/3,
adeg(OR2)=1


Symmetrization



Let f denote a symmetric function, i.e, f is constant
on all x with |x|=k, i.e., we have function values
f0,…,fn
Symmetrization turns a multilinear polynomial for f
into a univariate polynomial of the same degree
p(k)2[0,1/3] for fk=0 and p(k)2[2/3,1] for fk=1
XOR


We get a polynomial such that
p(k)2[0,1/3] for even k and p(k)2[2/3,1] for odd k
k2{0,…,n}

Clearly p(k)-1/2 has n roots!
And degree n

Q(XOR)=n/2

Symmetrization



Let  be a permutation of [1,…,n], p polynomial in n var.
Set psym(x)=
Lemma: If p is a multilinear polynom of degree d, then there is
a univariate degree d polynomial with q(|x|) = psym(x) for all x
 Proof:
 Let Vj denote the sum of all products of j variables
 Then psym can be written as i=0...d bi Vi

Value of Vj on x is

The sum is
The approximation degree of
OR



But what about OR?
 We know already Q(OR)=n1/2
 But adeg(OR) could be smaller
Symmetrization:
 p(0)
2[0,1/3]
 p(1),…,p(n)2[2/3,1]
What is the minimal degree of such a polynomial?
A result from approximation
theory

Theorem: Let p be a polynomial with 0· p(x)· 1 for
all integers 0· x· n
such that |p’(x)|¸ c for some real 0· x· n
Then deg(p)¸ (cn/(c+1))1/2




But: p(0)<1/3 and p(1)>2/3
Hence p’(x)¸ 1/3 for some x2 [0,1]
adeg(OR)¸ (n/4)1/2
We recover the lower bound for search etc.
Some more facts





For a total Boolean function f we have
D(f)=O(adeg(f)6)
Hence also D(f)=O(Q(f)6)
This is clearly only true for total functions
The best speedup that is known (Grover) is only
quadratic
Polynomial method is very useful for functions with
a lot of symmetry, example Element Distinctness
The adversary method



This method actually characterizes Q(f) [in its
strongest form]
Leads to a characterization as a semidefinite
program
Original idea is to bound the progress achieved by
one query in distinguishing pairs of inputs
Certificate complexity




A certificate for x is a set of positions and values
that fixes the function value for all x that are
consistent with them
 Example: x1=1 fixes OR
 XOR has no certificate of length <n
C(f) is the max over all x of the min certificate for x
C(XOR)=n
C(OR)=n
 0n needs a certificate of size n
An observation


There are 1-certificates and 0-certificates
 xi=1 is 1-cert for OR
 x1=0,…, xn=0 is 0-cert for OR
For all f: 1-cert and 0-cert need to share at least one
variable
Certificate and adversary
C( f ) =
m in
px 2 f
0;1gn
m ax
x
X
px ( j )
j
such t hat
X
px ( j ) py ( j ) ¸ 1 if f ( x) 6
= f ( y)
j :x j 6
= yj
A dv( f ) =
m inn m ax
px 2 R
x
X
px ( j ) 2
j
such t hat
X
j :x j 6
= yj
px ( j ) py ( j ) ¸ 1 if f ( x) 6
= f ( y)
Adversary bound
A dv( f ) =
m inn m ax jjpx jj 2
px 2 R
x
such t hat
X
px ( j ) py ( j ) ¸ 1 if f ( x) 6
= f ( y)
j :x j 6
= yj



Example: OR on 0n
10n-1 …
0n-11
px :
(1…1) (1 0….) (01 0…) (0…01)
Rescale by
1/n1/2
n1/2
Adv(OR)· n1/2
Adversary bound

Need to show two things:
 Q(f)=(Adv(f))
 How to prove lower bounds on Adv(f)
How to prove lower bounds

Adversary bound as stated is a minimization
problem, so we take the dual
A dv( f ) =
m ax
¡ 2RD£ D
jj¡ jj
such t hat
¡ ( x; y) ¸ 0
¡ ( x; y) = 0 if f ( x) = f ( y)
8j jj¡ ±
X
x;y:x j 6
= yj
jxi hyj jj · 1
Generalized adversary bound
A dv § ( f ) =
m ax
¡ 2 R D £ nD
jj¡ jj
such t hat
¡ ( x; y) = 0 if f ( x) = f ( y)
8j jj¡ ±
X
jxi hyjjj · 1
x;y:x j 6
= yj

This bound is asymptotically equal to Q(f)