25 September 2006

unglorious problems in quantum information

Along the lines of Scott's 10 annoying problems in quantum information (now happily only 8), I have a handful related to universal gate families.
  1. Let V be an imprimitive gate in U(d2), meaning that it cannot be written as a product of two gates in U(d). We know that V and V-1, together with U(d) x U(d) (i.e. all local gates), can exactly generate all of U(d2) [quant-ph/0108062]. But if we don't have access to V-1 then we only know how to approximate all of U(d2). Without the subgroup structure, general tools like quant-ph/0209113 can't be used. This is clearly an absurd situation, but show me the simple proof that V and U(d)xU(d) are exactly universal (which remarkably, I could actually make use of in a proof) and I'll agree that I'm being dumb.
  2. Does the Solovay-Kitaev theorem still hold if we aren't given inverses? Obviously, yes, but can we prove it? Even without giving an efficient construction of the approximating sequence?
  3. Some univeral gate families (e.g. (1 +- 2 i \sigma_j)/sqrt(5) where j ranges over x,y,z) have the property that a sequence of length O(log 1/eps) can approximate any gate to within accuracy eps. This matches the Omega(log 1/eps) bound from counting epsilon-balls. Does the O(log 1/eps) upper bound hold for all universal gate families? Solovay-Kitaev only guarantees O(log^(3+o(1)) 1/eps) sequence length, but it probably makes the sequences longer than it has to by requiring that everything be poly-time.
This last one is actually something that real mathematicians have considered, but not solved. But the first two I'm almost too embarassed to ask them! I mean, come on, people: we can pull this together.

A different sort of unglorious problem is the kind that someone else has solved, but couldn't be bothered to write up. Watch this space later for Shor's construction of higher-accuracy embezzling states and Kitaev's O(t) quantum communication simulation of e^{-itZZ}. Or more realistically you could corner me or Debbie at a conference some time and ask for an explanation.


Dave Bacon said...

1 is true for d=2, right?

a) Canonically decompose V=exp(i ( a XX + b YY + c ZZ)), by appropriate pre and post local unitaries
b) Conjugate V by XI to generate (XI)V(XI)=exp(i ( a XX - b YY - c ZZ))
c) Similarly construct exp(i ( -a XX + b YY - c ZZ)) and exp(i ( -a XX - b YY + c ZZ)) by appropriate conjugations
d) Use all three of these to together to generate exp(-i(a XX+b YY + c ZZ)) which is V^{-1}

(Probably an easier way to get this, but oh well.)

aram harrow said...

Good point. Actually this construction was the best we found in quant-ph/0207072, and it's no more than 5 times the optimal number of uses of V.

So it's only the d>2 case that's open.

mick said...

I worked on the first problem all day yesterday with no success. It is really unbelievable that this problem is open.

I thought I had almost solved it using some techniques from a Hamiltonian simulation paper that I wrote with Dave, but then I realised that I can't multiply by -1 properly.

Chris said...

Good point. Actually this construction was the best we found in quant-ph/0207072, and it's no more than 5 times the optimal number of uses of V.

When I wrote up my thesis I found a slightly better way to do it, and the construction is now optimal.

aram harrow said...

I solved problem #1 and will post the (not terribly exciting) solution on the arxiv in probably a few months. Email me if you want me to send it to you before then.