For More Information
We have reviewed, in this brief introduction, how a quantum computer can be viewed as a device that stores information as a unit vector in an exponentially large vector space, and seen how quantum gates can be used to rotate the information in a way so as to perform a calculation. We have also discussed useful language for describing quantum operations such as quantum circuits and Dirac notation which allow complex quantum states and subroutines to be quickly understood by a developer.
While these tools are foundational for any developer of quantum software, they by no means span the depth or breadth of what is known about quantum computer programming and algorithm design. Since quantum computing remains a rapidly developing field, there is no one resource that has all of the information needed to learn how to best use these tools in order to solve problems. For this reason we have compiled a list of below that may interest the reader who wishes to learn more about the art and beauty of quantum computer programming. This section contains selected references to deep coverage of quantum computing topics.
Basic quantum computing
- Nielsen, M. A. & Chuang, I. L. (2010). Quantum Computation and Quantum Information. Quantum Computation and Quantum Information, UK: Cambridge University Press, 2010.
- Kitaev, A. Y., Shen, A., & Vyalyi, M. N. (2002). Classical and quantum computation (Vol. 47). Providence: American Mathematical Society.
- Kaye, P., Laﬂamme, R., & Mosca, M. (2007). An introduction to quantum computing. Oxford University Press.
- Rieﬀel, E. G., & Polak, W. H. (2011). Quantum computing: A gentle introduction. MIT Press.
Elementary techniques for building controlled gates
- Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., ... & Weinfurter, H. (1995). Elementary gates for quantum computation. Physical Review A, 52(5), 3457.
- Jones, C. (2013). Low-overhead constructions for the fault-tolerant Toﬀoli gate. Physical Review A, 87(2), 022328
Techniques for preparing quantum states
- Shende, V. V., Markov, I. L., & Bullock, S. S. (2004). Minimal universal two-qubit controlled-NOT-based circuits. Physical Review A, 69(6), 062321.
- Ozols, M., Roetteler, M., & Roland, J. (2013). Quantum rejection sampling. ACM Transactions on Computation Theory (TOCT), 5(3), 11.
- Grover, L., & Rudolph, T. (2002). Creating superpositions that correspond to eﬃciently integrable probability distributions. arXiv preprint quant-ph/0208112.
- Farhi, E., Goldstone, J., Gutmann, S., & Sipser, M. (2000). Quantum computation by adiabatic evolution. arXiv preprint quant-ph/0001106.
Approaches for synthesizing circuits out of H, T and CNOT gates
- Kliuchnikov, V., Maslov, D., & Mosca, M. (2013). Asymptotically optimal approximation of single qubit unitaries by Cliﬀord and T circuits using a constant number of ancillary qubits. Physical Review Letters, 110(19), 190502.
- Ross, N. J., & Selinger, P. (2014). Optimal ancilla-free Cliﬀord+ T approximation of z-rotations. arXiv preprint arXiv:1403.2975.
- Kliuchnikov, V. (2013). Synthesis of unitaries with Cliﬀord+ T circuits. arXiv preprint arXiv:1306.3200.
- Jones, N. C., Whitﬁeld, J. D., McMahon, P. L., Yung, M. H., Van Meter, R., Aspuru-Guzik, A., & Yamamoto, Y. (2012). Faster quantum chemistry simulation on fault-tolerant quantum computers. New Journal of Physics, 14(11), 115023.
Approaches for quantum arithmetic
- Takahashi, Y., & Kunihiro, N. (2005). A linear-size quantum circuit for addition with no ancillary qubits. Quantum Information & Computation, 5(6), 440-448.
- Draper, T. G. (2000). Addition on a quantum computer. arXiv preprint quant-ph/0008033.
- Soeken, M., Roetteler, M., Wiebe, N., & De Micheli, G. (2017, March). Design automation and design space exploration for quantum computers. In 2017 Design, Automation & Test in Europe Conference & Exhibition (DATE) (pp. 470-475). IEEE.
Methods for fast quantum sampling (amplitude amplification) and probability estimation
- Brassard, G., Hoyer, P., Mosca, M., & Tapp, A. (2002). Quantum amplitude ampliﬁcation and estimation. Contemporary Mathematics, 305, 53-74.
- Grover, L. K. (2005). Fixed-point quantum search. Physical Review Letters, 95(15), 150501.
- Berry, D. W., Childs, A. M., & Kothari, R. (2015, October). Hamiltonian simulation with nearly optimal dependence on all parameters. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on (pp. 792-809). IEEE.
Algorithms for quantum simulation
- Lloyd, S. (1996). Universal Quantum Simulators. Science (New York, NY), 273(5278), 1073.
- Berry, D. W., Childs, A. M., Cleve, R., Kothari, R., & Somma, R. D. (2015). Simulating Hamiltonian dynamics with a truncated Taylor series. Physical Review Letters, 114(9), 090502.
- Low, G. H., & Chuang, I. L. (2017). Optimal Hamiltonian simulation by quantum signal processing. Physical Review Letters, 118(1), 010501.
- Low, G. H., & Chuang, I. L. (2016). Hamiltonian simulation by qubitization. arXiv preprint:1610.06546.
- Reiher, M., Wiebe, N., Svore, K. M., Wecker, D., & Troyer, M. (2017). Elucidating reaction mechanisms on quantum computers. Proceedings of the National Academy of Sciences, 201619152.
- Wiebe, N., Berry, D. W., Høyer, P., & Sanders, B. C. (2011). Simulating quantum dynamics on a quantum computer. Journal of Physics A: Mathematical and Theoretical, 44(44), 445308.
- Peruzzo, A., McClean, J., Shadbolt, P., Yung, M. H., Zhou, X. Q., Love, P. J., ... & Obrien, J. L. (2014). A variational eigenvalue solver on a photonic quantum processor. Nature communications, 5.
Procedures for quantum optimization
- Durr, C., & Høyer, P. (1996). A quantum algorithm for ﬁnding the minimum. arXiv preprint quantph/9607014.
- Farhi, E., Goldstone, J., & Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028.
- Brandao, F. G., Svore, K. M. (2017). Quantum Speed-ups for Semideﬁnite Programming. In Annual Symposium on Foundations of Computer Science (FOCS 2017).