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., Laflamme, R., & Mosca, M. (2007). An introduction to quantum computing. Oxford University Press.
  • Rieffel, 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 Toffoli 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 efficiently 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 Clifford 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 Clifford+ T approximation of z-rotations. arXiv preprint arXiv:1403.2975.
  • Kliuchnikov, V. (2013). Synthesis of unitaries with Clifford+ T circuits. arXiv preprint arXiv:1306.3200.
  • Jones, N. C., Whitfield, 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 amplification 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

Procedures for quantum optimization

  • Durr, C., & Høyer, P. (1996). A quantum algorithm for finding 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 Semidefinite Programming. In Annual Symposium on Foundations of Computer Science (FOCS 2017).