It’s time for the second installment of the Weakly Abstract and I can already tell that this is going to be a hell of a job to get through every week. The last week saw some fantastic papers hit the quant-ph arXiv, here’s the Weakly Abstract shortlist:
- Stephen Jordan and Edward Farhi, Perturbative Gadgets at Arbitrary Orders.
- Julia Kempe, Oded Regev, Falk Unger, and Ronald de Wolf, Upper Bounds on the Noise Threshold for Fault-tolerant Quantum Computing.
- Ronald de Wolf, A note on quantum algorithms and the minimal degree of $\eps$-error polynomials for symmetric functions.
The world however is a harsh and cruel place so there can only be one Weakly Abstract per week, and because nepotism is such a powerful force (and also because this paper got the most scites on SciRate this week) I’ve chosen "Random Quantum Circuits are Approximate 2-designs" by Richard Low and Aram Harrow:
Random Quantum Circuits are Approximate 2-designs
Authors: Aram Harrow, Richard Low
Given a universal gate set on two qubits, it is well known that applying random gates from the set to random pairs of qubits will eventually yield an approximately Haar-distributed unitary. However, this requires exponential time. We show that random circuits of only polynomial length will approximate the first and second moments of the Haar distribution, thus forming approximate 1- and 2-designs. Previous constructions required longer circuits and worked only for specific gate sets. As a corollary of our main result, we also improve previous bounds on the convergence rate of random walks on the Clifford group.
This paper is Richard (Rich) Low’s arXiv debut which is a massive achievement seeing as he has the misfortune of sharing an office with me. Now, because of this I get to try something that I’ve never really done before, I’m going to do an interview with Rich about the paper…
mick: Hi Rich.
mick: Your paper is really long. Let’s say, hypothetically, that I couldn’t be assed reading the whole thing, and possibly couldn’t even be bothered to read my way through the abstract. What would you say is the take home message of your paper?
Rich: The title. Presumably you’ve read that.
mick: OK then, what is a quantum 2-design?
Rich: A state 2-design is an ensemble of states that looks uniformly random when you are only given two copies of the state.
mick: What is a unitary 2-design?
Rich: It’s an ensemble of unitaries that looks uniformly random given two copies of a unitary from the ensemble.
mick: OK, so what did you do again?
Rich: We showed that random circuits constructed from a 2-qubit universal gate set give approximate unitary 2-designs efficiently.
mick: So that really took 36 pages? I guess that at least this paper is shorter than Toby’s paper last week. So should we end this now and just drink our beer?