2013

Complex instruction set computing architecture for performing accurate quantum $Z$ rotations with less magic

Landahl, Andrew J., Cesare, Chris

Understand

We present quantum protocols for executing arbitrarily accurate $\pi/2^k$ rotations of a qubit about its $Z$ axis.

Reduced instruction set computing (\textsc{risc}) architectures typically restrict the instruction set to stabilizer operations and a single non-stabilizer operation, such as preparation of a "magic" state from which $T = Z(\pi/4)$ gates can be teleported.
Although the overhead required to distill high-fidelity copies of this magic state is high, the subsequent quantum compiling overhead to realize $Z$ rotations in a \textsc{risc} architecture can be much greater.
We develop a complex instruction set computing (\textsc{cisc}) architecture whose instruction set includes stabilizer operations and preparation of magic states from which $Z(\pi/2^k)$ gates can be teleported, for $2 \leq k \leq k_{\text{max}}$.

Built on

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes , vol. 16 of North-Holland mathematical library (North-Holland, New York, 1977), ISBN 0-444-85009-0
1977
Earlier work this paper cites.
G. Duclos-Cianci and K. M. Svore, A state distillation protocol to implement arbitrary single-qubit rotations (2012), arXiv:1201.1980
Original
1980
Earlier work this paper cites.
H. N. Ward, Weight polarization and divisibility , Discrete Math. 83
1990
Earlier work this paper cites.
P. W. Shor, Scheme for reducing decoherence in quantum computer memory , Phys. Rev. A 52
1995
Earlier work this paper cites.
R. Solovay, Lie groups and quantum circuits (2000), MSRI presentation at http://www.msri.org/publica-tions/ln/msri/2000/qcomputing/solovay/1/ . According to Ref. Dawson and Nielsen 2006 , the proof was announced by Solovay in 1995 on a virtual reading group e-mail discussion list
1995
Earlier work this paper cites.
A. Y. Kitaev, Quantum measurements and the abelian stabilizer problem (1995), arXiv:quant-ph/9511026
1995
Earlier work this paper cites.
P. W. Shor, Fault-tolerant quantum computation , in Proceedings of the 37th Annual Symposium on Foundations of Computer Science , edited by R. S. Sipple, IEEE (IEEE Press, Los Alamitos, CA, 14–16 Oct. 1996, Burlington, VT, USA, 1996), pp. 56–65, ISBN 0-8186-7594-2, doi:10.1137/S0097539795293172 , arXiv:quant-ph/9605011
1996
Earlier work this paper cites.
A. R. Calderbank and P. W. Shor, Good quantum error-correcting codes exist , Phys. Rev. A 54
1996
Earlier work this paper cites.
D. Aharonov and M. Ben-Or, Fault tolerant quantum computation with constant error rate (1999), See also condensed version Aharonov and Ben-Or 1997 ., arXiv:quant-ph/9906129
1997
Earlier work this paper cites.
A. M. Steane, Active stabilization, quantum computation, and quantum state synthesis , Phys. Rev. Lett. 78
1997
Earlier work this paper cites.
D. Gottesman, Stabilizer codes and quantum error correction , Ph.D. thesis, Caltech (1997), arXiv:quant-ph/9705052
1997
Earlier work this paper cites.
L. Zhang and I. Fuss, Quantum Reed-Muller codes (1997), arXiv:quant-ph/9703045
1997
Earlier work this paper cites.
E. Farhi and S. Gutmann, Analog analogue of a digital quantum computation , Phys. Rev. A 57
1998
Earlier work this paper cites.
E. Knill, R. Laflamme, and W. H. Zurek, Resilient quantum computation: Error models and thresholds , Proc. Roy. Soc. London A 454
1998
Earlier work this paper cites.
R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca, Quantum algorithms revisited , Proc. Roy. Soc. London A 454
1998
Earlier work this paper cites.
D. Aharonov and M. Ben-Or, Fault tolerant quantum computation with constant error , in Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing , edited by F. T. Leighton and P. Shor (ACM Press, New York, El Paso, TX, USA, 1997), pp. 176–188, ISBN 0-89791-888-6, See also extended version Aharonov and Ben-Or 1999 ., doi:10.1145/258533.258579 , arXiv:quant-ph/9611025
1999
Earlier work this paper cites.
D. Gottesman, The Heisenberg representation of quantum computers , in Group22: Proceedings of the XXII International Colloquium on Group Theoretical Methods in Physics , edited by S. P. Corney, R. Delbourgo, and P. D. Jarvis (International Press, Cambridge, MA, 13–17 Jul. 1998, Hobart, Australia, 1999), pp. 32–43, arXiv:quant-ph/9807006
1999
Earlier work this paper cites.
M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, Cambridge, 2000), ISBN 0-521-63235-8 (Hardback), 0-521-63503-9 (Paperback)
2000
Earlier work this paper cites.
A. M. Childs, E. Farhi, and J. Preskill, Robustness of adiabatic quantum computation , Phys. Rev. A 65
2001
Earlier work this paper cites.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (MIT Press and McGraw-Hill, 2001), ISBN 0-262-03293-7
Original
2001
Earlier work this paper cites.
E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Topological quantum memory , J. Math. Phys. 43
2002
Earlier work this paper cites.
A. W. Harrow, B. Recht, and I. L. Chuang, Efficient discrete approximations of quantum gates , J. Math. Phys. 43
2002
Earlier work this paper cites.
A. Yu. Kitaev, A. Shen, and M. N. Vyalyi, Classical and Quantum Computation , vol. 47 of Graduate Studies in Mathematics (American Mathematical Society, Providence, RI, 2002), ISBN 0-821-82161-X, Translated from the Russian edition by Lester J. Senechal
2002
Earlier work this paper cites.

Similar

D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, Adiabatic quantum computation is equivalent to standard quantum computation , in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science , edited by D. Azada, IEEE (IEEE Press, Los Alamitos, CA, Oct. 17–19, Rome, IT, 2004), pp. 42–51, ISBN 0-7695-2228-9, doi:10.1109/FOCS.2004.8 , arXiv:quant-ph/0405098
2004
Cited alongside, same era.
C. S. Ahn, Extending quantum error correction: new continuous measurement protocols and improved fault-tolerant overhead , Ph.D. thesis, Caltech (2004)
2004
Cited alongside, same era.
E. Knill, Fault-tolerant postselected quantum computation: Schemes (2004), arXiv:quant-ph/0402171
2004
Cited alongside, same era.
B. W. Reichardt, The quantum adiabatic optimization algorithm and local minima , in Proceedings of the Thirty-Sixth Annual ACM Symposium on the Theory of Computing , edited by L. L. Larmore and M. X. Goemans (ACM Press, New York, 13–15 Jun. 2004, Chicago, IL, USA, 2004), pp. 502–510, ISBN 1-58113-852-0, doi:10.1145/1007352.1007428
2004
Cited alongside, same era.
M. S. Sarandy and D. A. Lidar, Adiabatic quantum computation in open systems , Phys. Rev. Lett. 95
2005
Cited alongside, same era.
J. Roland and N. J. Cerf, Noise resistance of adiabatic quantum computation using random matrix theory , Phys. Rev. A 71
2005
Cited alongside, same era.
S. Bravyi and A. Kitaev, Universal quantum computation with ideal Clifford gates and noisy ancillas , Phys. Rev. A 71
2005
Cited alongside, same era.
M. F. Sacchi, Optimal discrimination of quantum operations , Phys. Rev. A 71
2005
Cited alongside, same era.
A. G. Fowler, Towards larg-scale quantum computation , Ph.D. thesis, University of Melbourne (2005), arXiv:quant-ph/0506126
2005
Cited alongside, same era.
A. Gilchrist, N. K. Langford, and M. A. Nielsen, Distance measures to compare real and ideal quantum processes , Phys. Rev. A 71
2005
Cited alongside, same era.
B. W. Reichardt, Quantum universality from magic states distillation applied to CSS codes , Quant. Inf. Proc. 4
2005
Cited alongside, same era.
P. Sarvepalli and A. Klappenecker, Nonbinary quantum Reed-Muller codes , IEEE (IEEE Press, 4–9 Sep. 2005, Adelaide, Australia, 2005), pp. 1023–1027, doi:10.1109/ISIT.2005.1523494 , arXiv:quant-ph/0502001
2005
Cited alongside, same era.

Then

N. Isailovic, M. Whitney, Y. Patel, and J. Kubiatowicz, Running a quantum circuit at the speed of data , IEEE (IEEE Press, Los Alamitos, 21–25 Jun., 2008, Beijing, China, 2008), p. 177, doi:10.1109/ISCA.2008.5 , arXiv:0804.4725
Original
2008
Later among the works it cites.
A. G. Fowler, A. M. Stephens, and P. Groszkowski, High-threshold universal quantum computation on the surface code , Phys. Rev. A 80
Original
2009
Later among the works it cites.
B. Eastin and E. Knill, Restrictions on transversal encoded quantum gate sets , Phys. Rev. Lett. 102
Original
2009
Later among the works it cites.
F. M. Spedalieri and V. P. Roychowdhury, Latency in local, two-dimensional, fault-tolerant quantum computing , Quant. Inf. Comp. 9
Original
2009
Later among the works it cites.
J. Watrous, Semidefinite programs for completely bounded norms (2009), arXiv:0901.4709
Original
2009
Later among the works it cites.
I. de Vega, M. C. Bañuls, and A. Pérez, Effects of dissipation on an adiabatic quantum search algorithm , New J. Phys. 12
Original
2010
Later among the works it cites.
A. J. Landahl, J. T. Anderson, and P. R. Rice, Fault-tolerant quantum computing with color codes (2011), arXiv:1108.5738
Original
2011
Later among the works it cites.
A. Fowler, Constructing arbitrary Steane code single logical qubit fault-tolerant gates , Quant. Inf. Comp. 11
2011
Later among the works it cites.
G. A. Paz-Silva, A. T. Rezakhani, J. M. Dominy, and D. A. Lidar, Zeno effect for quantum computation and control , Phys. Rev. Lett. 108
Original
2012
Later among the works it cites.
K. C. Young and M. Sarovar, Equivalence and limitations of error suppression techniques for adiabatic quantum computing (2012), arXiv:1208.6371
Original
2012
Later among the works it cites.
S. Bravyi and J. Haah, Magic state distillation with low overhead (2012), arXiv:1209.2426
Original
2012
Later among the works it cites.
N. C. Jones, J. D. Whitfield, P. L. McMahon, M.-H. Yung, R. Van Meter, A. Aspuru-Guzik, and Y. Yamamoto, Simulating chemistry efficiently on fault-tolerant quantum computers (2012), arXiv:1204.0567
Original
2012
Later among the works it cites.
P. Selinger, Efficient Clifford+T approximation of single-qubit operators (2012), arXiv:1212.6253
Original
2012
Later among the works it cites.
J. T. Anderson, On the power of reusable magic states (2012), arXiv:1205.0289
Original
2012
Later among the works it cites.
P. T. Trung, R. Van Meter, and C. Horsman, Optimising the Solovay-Kitaev algorithm (2012), arXiv:1209.4139
Original
2012
Later among the works it cites.
R. B. McDonald and H. G. Katzgraber, Genetic braid optimization: A heuristic approach to compute quasiparticle braids (2012), arXiv:1211.7359
Original
2012
Later among the works it cites.
M. Amy, D. Maslov, M. Mosca, and M. Roetteler, A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits (2012), arXiv:1206.0758
Original
2012
Later among the works it cites.
A. Bocharov and K. Svore, A depth-optimal canonical form for single-qubit quantum circuits (2012), arXiv:1206.3223
Original
2012
Later among the works it cites.
T. Jochym-O’Connor, Y. Yu, B. Helou, and R. Laflamme, The robustness of magic state distillation against errors in Clifford gates (2012), arXiv:1205.6715
Original
2012
Later among the works it cites.
A. M. Meier, B. Eastin, and E. Knill, Magic-state distillation with the four-qubit code (2012), arXiv:1204.4221
Original
2012
Later among the works it cites.
A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Surface codes: Towards practical large-scale quantum computation , Phys. Rev. A 86
Original
2012
Later among the works it cites.
E. T. Campbell, H. Anwar, and D. E. Browne, Magic state distillation in all prime dimensions using quantum Reed-Muller codes (2012), arXiv:1205.3104
Original
2012
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…