arXiv Analytics

Sign in

arXiv:1904.01124 [quant-ph]AbstractReferencesReviewsResources

Lower bounds on the non-Clifford resources for quantum computations

Michael Beverland, Earl Campbell, Mark Howard, Vadym Kliuchnikov

Published 2019-04-01Version 1

We establish lower-bounds on the number of resource states, also known as magic states, needed to perform various quantum computing tasks, treating stabilizer operations as free. Our bounds apply to adaptive computations using measurements and an arbitrary number of stabilizer ancillas. We consider (1) resource state conversion, (2) single-qubit unitary synthesis, and (3) computational tasks. To prove our resource conversion bounds we introduce two new monotones, the stabilizer nullity and the dyadic monotone, and make use of the already-known stabilizer extent. We consider conversions that borrow resource states, known as catalyst states, and return them at the end of the algorithm. We show that catalysis is necessary for many conversions and introduce new catalytic conversions, some of which are close to optimal. By finding a canonical form for post-selected stabilizer computations, we show that approximating a single-qubit unitary to within diamond-norm precision $\varepsilon$ requires at least $1/7\cdot\log_2(1/\varepsilon) - 4/3$ $T$-states on average. This is the first lower bound that applies to synthesis protocols using fall-back, mixing techniques, and where the number of ancillas used can depend on $\varepsilon$. Up to multiplicative factors, we optimally lower bound the number of $T$ or $CCZ$ states needed to implement the ubiquitous modular adder and multiply-controlled-$Z$ operations. When the probability of Pauli measurement outcomes is 1/2, some of our bounds become tight to within a small additive constant.

Related articles: Most relevant | Search more
arXiv:quant-ph/0102030 (Published 2001-02-05, updated 2004-06-14)
Geometric Phases and Quantum Computations
arXiv:quant-ph/0207102 (Published 2002-07-18)
On Geometric Realization of Quantum Computations in Externally Driven 4-Level System
arXiv:quant-ph/9602021 (Published 1996-02-29)
Polarization in Quantum Computations