Open Collections

A framework for approximating qubit unitaries

Banff International Research Station for Mathematical Innovation and Discovery

We present an algorithm for efficiently approximating of qubit unitaries over gate sets derived from totally definite quaternion algebras. It achieves ε-approximations using circuits of length O(log(1/ε)), which is asymptotically optimal. The algorithm achieves the same quality of approximation as previously-known algorithms for Clifford+T [arXiv:1212.6253], V-basis [arXiv:1303.1411] and Clifford+π/12 [arXiv:1409.3552], running on average in time polynomial in O(log(1/ε)) (conditional on a number-theoretic conjecture). Ours is the first such algorithm that works for a wide range of gate sets and provides insight into what should constitute a "good" gate set for a fault-tolerant quantum computer. Joint work with Alex Bocharov, Martin Roetteler, Jon Yard: http://arxiv.org/abs/1510.03888

Mathematics; Quantum theory; Information and communication, circuits; Theoretical computer science

video/mp4

Author affiliation: Microsoft Research

2016-10-18

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/59480

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/