References

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 http://www.cs.duke.edu/reif/paper/qsurvey.ps), Jan. 1999. (abstract, ps)

  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). (abstract, ps)

  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 Physics, 173, 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. (abstract, .ps)

  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. (abstract, .ps)

  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

    Universality

  1. A. Barenco et al.: ``Elementary gates for quantum computation,'' Physical Review A 52, 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)

    11. Two Qubits

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

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

  13. G. Song and A. Klappenecker ``Optimal realizations of controlled unitary gates,'' quant-ph/0207157.

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

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

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

  17. F. Vatan, C. Williams, ``Optimal quantum circuits for general two-qubit gates,'' Physical Review A 69, 032315 (2004).

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

    19. Three Qubits

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

  20. D. P. DiVincenzo and John Smolin, ``Results on two-bit gate design for quantum computers,'' cond-mat/9409111.

  21. J. J. Vartiainen, A. O. Niskanen, M. Nakahara, M. M. Salomaa, ``Acceleration of quantum algorithms using three-qubit gates,'' quant-ph/0310165.

  22. F. Vatan, C. Williams, `` Realization of a General Three-Qubit Quantum Gate,'' quant-ph/0401178.

  23. G. Song and A. Klappenecker, `` The simplified Toffoli gate implementation by Margolus is optimal,'' quant-ph/0312225

  24. D. Maslov, G. W. Dueck `` Improved Quantum Cost for n-bit Toffoli Gates ,'' quant-ph/0403053.

  25. 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

    26. N Qubits

  26. E. Knill, ``Approximation by Quantum Circuits,'' LANL report LAUR-95-2225.

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

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

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

  30. S. S. Bullock, ``Note on the Khaneja Glaser Decomposition,'' quant-ph/0403141.

  31. A. V. Aho, K. M. Svore `` Compiling Quantum Circuits using the Palindrome Transform,'' quant-ph/0311008.

  32. J. J. Vartiainen, M. Mottonen, and. M. Salomaa ``Efficient Decomposition of Quantum Gates,'' Physical Review Letters 92, 177902 (2004).

  33. M. Mottonen, J. J. Vartiainen, V. Bergholm, M. M. Salomaa, ``Universal quantum computation,'' quant-ph/0404089.

    34. Circuit Blocks (Arithmetic ops, Fourier Transform, etc)

  34. 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.

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

  36. V. Vedral, A. Barenko and A. Eckert, ``Quantum Networks for Elementary Arithmetic Operations,'' quant-ph/9511018.

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

  38. St. Beauregard, ``Circuit for Shor's algorithm using 2n+3 qubits,'' Quantum Information and Computation 3(2), 175 (2003).

  39. 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.

  40. D. Maslov, G. W. Dueck, `` Improved Quantum Cost for n-bit Toffoli Gates'', quant-ph/0403053.

  41. T. Hogg, C. Mochon, W. Polak, E. Rieffel `` Tools for Quantum Algorithms'', Int.J.Mod.Phys. C10 (1999) 1347-1362, quant-ph/9811073.

  42. 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

    43. Other

  43. 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)

  44. 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. (abstract, pdf)

  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).

Simulation

  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. (abstract, .ps)

  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. (abstract, pdf)

  4. V. Kravets: "Constructive Multi-Level Synthesis by Way of Functional Properties." (abstract, pdf)

  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. (abstract, pdf)

  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). (abstract, pdf)

  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). (abstract, pdf)

  2. S. Egner et. al: ``Decomposing a Permutation into a Conjugated Tensor Product,'' International Symposium on Symbolic and Algebraic Computation, 1997. (abstract, .ps)

  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.