- 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.
- 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?
- 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.
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.
Posts
5 comments:
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.)
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.
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.
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.
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.
Post a Comment