References A

Books, Surveys, and Popular Science

  1. A. Eckert, P. Hayden, H. Inamori, “ Basic Concepts In Quantum Computation,” Lecture Notes, 2000. (37 p.)

  2. J. H. Reif, “Quantum Information Processing: Compression, Coding, and Related Computations”, (Online preprint in postscript, Jan. 1999. (abstractps)

  3. E. Rieffel and W. Polak, “ An Introduction to Quantum Computing for Non-physicists,” ACM Computing Surveys 32(2), 300-335 (2000).

  4. D. Aharonov, “Quantum Computation,” Annual Reviews of Computational Physics , ed. Dietrich Stauffer, World Scientific, vol VI, 1998.

  5. J. Preskill: “Quantum Computing: Pro and Con,” Proc. Roy. Soc. Lond. A 454, 469-486 (1998).

  6. J. Mullins: “The Topsy Turvy World of Quantum Computing,” IEEE Spectrum , Feb. 2001.

  7. M. Tegmark and J. Wheeler: “100 Years of the Quantum,” Scientific American , Feb. 2001 (p.68-75). (abstractps)

  8. NSF, “Quantum Information Science”, Report of NSF Workshop, Arlington, VA, Oct. 1999 (38 p.)

  9. Th. Beth and M. R. Rotteler, “Quantum Algorithms: Applicable Algebra and Quantum Physics,” Springer Tracts in Modern Physics173, 2001, pp. 96-50. (pdf).

  10. “Two-bit heros,” The Economist, Janurary 13th, 1996, pp. 78-79. (pdf)

Quantum Algorithms

  1. P. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithm on a quantum computer,” SIAM Journal of Computing 26(5), 1484-1509 (1997).

  2. Y. Manin, “Classical computing, quantum computing, and Shor’s factoring algorithm,” quant-ph/9903008.

  3. A. Eckert and R. Jozsa: “Quantum Computation and Shor’s Factoring Algorithm,” Rev. Mod. Phys. 68(3), 733-753 (1996).

  4. L. Hales and S. Hallgren, “An Improved Quantum Fourier Transform Algorithm and Applications,” Proc. ACM Symposium on Foundations of Computer Science, Nov. 2000. (.ps)

  5. S. Hallgren et. al: “Normal Subgroup Reconstruction and Quantum Computation Using Group Representations,” Proc. ACM Symposium on Theory of Computing, 2000. (

  6. R. Josza, “ Quantum factoring, discrete logarithms and the hidden subgroup problem,”IEEE Computing in Science and Engineering, 2001.

  7. M. Grigni et. al, “Quantum mechanical algorithms for the nonabelian hidden subgroup problem,” Proc. ACM Symposium on Theory of Computing 33, 2001. (

  8. L. K. Grover: “From Schrodinger’s Equation to the Quantum Search Algorithm”, Winter Inst. on Foundations of Quantum Theory, Calcutta, Jan 2000

  9. L. K. Grover: “Searching with quantum computers,” Dr. Dobbs, April 2001.

Generic Quantum Logic Circuits


    1. A. Barenco et al.: “Elementary gates for quantum computation,” Physical Review A52, 3457 (1995).

    2. D. P. DiVincenzo, “Two-bit gates are universal for quantum computation,” Physical Review A 15, 1015 (1995).

    3. A. Barenco, D. Deutsch and A. Ekert, “Conditional quantum dynamics and logic gates,” Physical Review Letters 74, 4083 (1995).

    4. Yaoyun Shi, “Both Toffoli and Controlled-NOT need little help to do universal quantum computation,” quant-ph/0205115.

    5. Dorit Aharonov, “ A Simple Proof that Toffoli and Hadamard are Quantum Universal,” quant-ph/0301040

    6. P. O. Boykin, T. Mor, M. Pulver, V. Roychowdhury, F. Vatan, “On Universal and Fault-Tolerant Quantum Computing”, quant-ph/9906054.

    7. A. W. Harrow, B. Recht, I. L. Chuang “ Efficient Discrete Approximations of Quantum Gates”, quant-ph/0111031.

    8. W. van Dam, M. Mosca, U. Vazirani, “How Powerful is Adiabatic Quantum Computation?” quant-ph/0206003.

    9. D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, O. Regev Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation quant-ph/0405098.

    10. B. C. Travaglione, M. A. Nielsen, H. M. Wiseman, A. Ambainis, “ROM-based computation: quantum versus classical,” Quantum Information and Computation 2, no. 4 (2002)

Two Qubits

    1. B. Kraus and J.I. Cirac, “Optimal creation of entanglement using a two-qubit gate,”Physical Review A 63, 062309 (2000).

    2. K. Hammerer, G. Vidal, and J. I. Cirac, “Characterization of non-local gates,” Physical Review A 66, 062321 (2002).

    3. G. Song and A. Klappenecker “Optimal realizations of controlled unitary gates,” quant-ph/0207157.

    4. J. Zhang, J. Vala, K. B. Whaley, Sh. Sastry, “A geometric theory of non-local two-qubit operations,” Physical Review A 67, 042313 (2003).

    5. J. Zhang, J.Vala, Sh. Sastry, K. B. Whaley “Exact two-qubit universal quantum circuit,” Physical Review Letters 91, 027903 (2003).

    6. G. Vidal and C. M. Dawson, “A universal quantum circuit for two-qubit transformations with three CNOT gates,” Physical Review A 69, 010301 (2004)

    7. F. Vatan, C. Williams, “Optimal quantum circuits for general two-qubit gates,”Physical Review A 69, 032315 (2004).

    8. J. Zhang, J. Vala, Sh. Sastry, K. B. Whaley, “Minimum construction of two-qubit quantum operations,” Physical Review Letters 93, 020502 (2004).

Three Qubits

    1. J. A. Smolin, “Five two-bit quantum gates are sufficient to implement the quantum Fredkin gate”, Physical Review A 5(4), 2855 (1996). (.pdf)

    2. D. P. DiVincenzo and John Smolin, “Results on two-bit gate design for quantum computers,” cond-mat/9409111.

    3. J. J. Vartiainen, A. O. Niskanen, M. Nakahara, M. M. Salomaa, “Acceleration of quantum algorithms using three-qubit gates,” quant-ph/0310165.

    4. F. Vatan, C. Williams, “ Realization of a General Three-Qubit Quantum Gate,” quant-ph/0401178.

    5. G. Song and A. Klappenecker, “ The simplified Toffoli gate implementation by Margolus is optimal,” quant-ph/0312225

    6. D. Maslov, G. W. Dueck “ Improved Quantum Cost for n-bit Toffoli Gates ,” quant-ph/0403053.

    7. V. V. Shende and I. L. Markov “ On the CNOT-cost of TOFFOLI Gates ,” Quantum Information and Computation, vol. 9, no. 5-6, pp. 461-486, May 2009

N Qubits

    1. E. Knill, “Approximation by Quantum Circuits,” LANL report LAUR-95-2225.

    2. G. Cybenko: “Reducing Quantum Computations to Elementary Unitary Operations”, Comp. in Sci. and Engin., March/April 2001, pp. 27-32. (abstract.pdf)

    3. N. Khaneja, R. Brockett, and S.J. Glaser, “Time Optimal Control in Spin Systems,” Phys. Rev A, 63, 032308 (2001).

    4. N. Khaneja and St. Glaser, “Cartan Decomposition of SU(2^n), Constructive Controllability of Spin systems and Universal Quantum Computing,” quant-ph/0010100

    5. S. S. Bullock, “Note on the Khaneja Glaser Decomposition,” quant-ph/0403141.

    6. A. V. Aho, K. M. Svore “ Compiling Quantum Circuits using the Palindrome Transform,” quant-ph/0311008.

    7. J. J. Vartiainen, M. Mottonen, and. M. Salomaa “Efficient Decomposition of Quantum Gates,” Physical Review Letters 92, 177902 (2004).

    8. M. Mottonen, J. J. Vartiainen, V. Bergholm, M. M. Salomaa, “Universal quantum computation,” quant-ph/0404089.

Circuit Blocks (Arithmetic ops, Fourier Transform, etc)

    1. D. Maslov and G. Dueck, “ Improved Quantum Cost for n-bit Toffoli Gates,” IEE Electronics Letters, vol. 39, issue 25, Dec. 2003, pp. 1790-1791. quant-ph/0403053.

    2. Th. G. Draper, S. A. Kutin, E. M. Rains, K. M. Svore “ A logarithmic-depth quantum carry-lookahead adder,” quant-ph/0404162.

    3. V. Vedral, A. Barenko and A. Eckert, “Quantum Networks for Elementary Arithmetic Operations,” quant-ph/9511018.

    4. R. Cleve and J. Watrous. “Fast parallel circuits for the quantum Fourier transform” (.ps), FOCS, pages 526-536, 2000.

    5. St. Beauregard, “Circuit for Shor’s algorithm using 2n+3 qubits,” Quantum Information and Computation 3(2), 175 (2003).

    6. A. G. Fowler, S. J. Devitt, L. C. L. Hollenberg, “ Implementation of Shor’s Algorithm on a Linear Nearest Neighbour Qubit Array,” quant-ph/0402196.
    7. D. Maslov, G. W. Dueck, “ Improved Quantum Cost for n-bit Toffoli Gates”, quant-ph/0403053.
    8. T. Hogg, C. Mochon, W. Polak, E. Rieffel “ Tools for Quantum Algorithms”, Int.J.Mod.Phys. C10 (1999) 1347-1362, quant-ph/9811073.
    9. V. V. Shende and I. L. Markov “ On the CNOT-cost of TOFFOLI Gates ,” Quantum Information and Computation, vol. 9, no. 5-6, pp. 461-486, May 2009


  1. C. P. Williams and A. G. Gray, “Automated design of quantum circuits,” QCQC 98, Lecture Notes on Compu. Sci., v. 1509, pp. 113-125, Springer-Verlag, 1999. (pdf)

  2. T.Yabuki and H.Iba, “Genetic Algorithms for quantum circuit design: Evolving a simpler teleportation circuit,” 2000 Genetic and Evolutionary Computation Conf., Las Vegas, NV, pp. 425-430, 2000. (pdf)

Architectures and Physical Implementations

  1. M. Steffen et al.: “Toward Quantum Computation: a Five-qubit Quantum Processor,”IEEE Micro, March-April 2001, pp. 24-34. (abstractpdf)

  2. L. M. K. Vandersypen et al., “NMR quantum computing: realizing Shor’s algorithm,”Nature 20/27, December 2001.

  3. D. Kielpinski, C. Monroe and D. J. Wineland, “ Architecture for a large-scale ion-trap quantum computer,” Nature 417, 709 (2002). (.ps)

  4. Philip Ball, “Silicon quantum computer,” Nature News Service.

  5. S. Bettelli, L. Serafini, T. Calarco, “Toward an architecture for quantum programming,” European Physics Journal D 25(2), 181 (2003).

  6. Yu. A. Pashkin, T. Yamamoto, O. Astafiev, Y. Nakamura, D. V. Averin and J. S. Tsai, “Quantum Oscillations In Two Coupled Charge Qubits,” Nature 421, 823 (2003).

  7. L. M. K. Vandersypen, I. L. Chuang, “ NMR Techniques for Quantum Control and Computation,” quant-ph/0404064.

Noise and Error Correction

  1. D. Aharonov, M. Ben-Or, “Fault-Tolerant Quantum Computation With Constant Error Rate,” quant-ph/9906129.

  2. D. Gottesman, “The Heisenberg Representation of Quantum Computers,” LAUR-98-2848.

  3. W. van Dam, F. Magniez, M. Mosca, Miklos Santha, “Self-Testing of Universal and Fault-Tolerant Sets of Quantum Gates,” Proc. ACM Symposium on Theory of Computing 32, 2000, pp. 688-696.

  4. N. Shenvi, K. R. Brown, K. B. Whaley, “Effects of Noisy Oracle on Search Algorithm Complexity,” quant-ph/0304138.

  5. A. Barenco, T. A. Brun, R. Schack, and T. Spiller, “Effects of noise on quantum error correction algorithms,” Modern Physics Letters A 13, 2503-2512 (1998).


  1. D. Gottesman, “The Heisenberg Representation of Quantum Computers,” LAUR-98-2848.

  2. S. Aaronson and D. Gottesman, “Improved Simulation of Stabilizer Circuits Representation of Quantum Computers”, quant-ph/0406196

  3. R. Josza and N. Linden, “On the Role of Entanglement in Quantum Computational Speed-up”, quant-ph/0201143.

  4. G. Vidal, Efficient classical simulation of slightly entangled quantum computations , Phys. Rev. Lett. 91, 147902 (2003), quant-ph/0301063

  5. G. Vidal, Efficient simulation of one-dimensional quantum many-body systems , quant-ph/0310089

  6. Quantum Computer Architecture Simulator (ARQ) from Chuang’s group at MIT.

  7. Quantum Computer Emulator from de Raedt’s group.

Classical Computation

  1. G. Hachtel and F. Somenzi, “Logic Synthesis and Verification Algorithms”, 3 ed., 2000

  2. O. Coudert: “Doing Two-Level Logic Minimization 100 Times Faster.” Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, 1995, pp.112–121. (

  3. D. Jankovic, R. S. Stankovic and R. Drechsler: “Decision Diagram Method for Calculation of Pruned Walsh Transform”, IEEE Transactions on Computers, Vol. 50, No. 2, February 2001. (abstractpdf)

  4. V. Kravets: “Constructive Multi-Level Synthesis by Way of Functional Properties.” (abstractpdf)

  5. A. Mishchenko: “Implicit Representation of Discrete Objects”, Proc. of 3d Oregon Symposium on Logic, Design,and Learning (LDL ’00), May 22 2000, Porland, Oregon. (abstractpdf)

  6. A. Mishchenko: “An Introduction to Zero-suppressed Binary Decision Diagrams,” 2001. (pdf)

  7. M. Thornton and V. S. S. Nair, “Behavioral Synthesis of Combinational Logic Using Spectral Based Heuristics,” ACM Transactions on Design Automation of Electronic Systems 4(2), 219-230 (1999). (abstractpdf)

  8. T. Toffoli, “Reversible Computing,” Tech. Memo MIT/LCS/TM-151, MIT Lab for Comp. Sci, 1980. (36 p.) (pdf)

  9. M. Perkowski et al., “A General Decomposition For Reversible Logic,” Reed-Muller workshop, Aug. 2001. (18 p., pdf 1 pdf 2)

  10. K. Iwama, Y. Kambayashi, S. Yamashita, “Transformation Rules For Designing CNOT-based Quantum Circuits,” Design Autom. Conf. (DAC) 2002, pp. 419-425. (pdf)

  11. Jae-Seung Lee, “A Practical Method of Constructing Quantum Combinational Logic Circuits,” quant-ph/9911053.

  12. Reversible Computers at Ghent

Matrix Decomposition Techniques

  1. V. Pan: “Nearly Optimal Computations With Structured Matrices,” Proc. ACM-SIAM Symposium on Discrete Algorithms 11, San Francisco, CA (2000). (abstractpdf)

  2. S. Egner et. al: “Decomposing a Permutation into a Conjugated Tensor Product,” International Symposium on Symbolic and Algebraic Computation, 1997. (

  3. C. C. Paige and M. Wei, “History and Generality of the CS Decomposition,” Linear Algebra and Appl. 208/209, 303-326 (1994). (ps)

Visualization and Graphics

  1. B. Eastin, S. T. Flammia, “Q-circuit Tutorial,” quant-ph/0406003.