Books, Surveys, and Popular Science
-
A. Eckert, P. Hayden, H. Inamori, “ Basic Concepts In Quantum Computation,” Lecture Notes, 2000. (37 p.)
-
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)
-
E. Rieffel and W. Polak, “ An Introduction to Quantum Computing for Non-physicists,” ACM Computing Surveys 32(2), 300-335 (2000).
-
D. Aharonov, “Quantum Computation,” Annual Reviews of Computational Physics , ed. Dietrich Stauffer, World Scientific, vol VI, 1998.
-
J. Preskill: “Quantum Computing: Pro and Con,” Proc. Roy. Soc. Lond. A 454, 469-486 (1998).
-
J. Mullins: “The Topsy Turvy World of Quantum Computing,” IEEE Spectrum , Feb. 2001.
-
M. Tegmark and J. Wheeler: “100 Years of the Quantum,” Scientific American , Feb. 2001 (p.68-75). (abstract, ps)
-
NSF, “Quantum Information Science”, Report of NSF Workshop, Arlington, VA, Oct. 1999 (38 p.)
-
Th. Beth and M. R. Rotteler, “Quantum Algorithms: Applicable Algebra and Quantum Physics,” Springer Tracts in Modern Physics, 173, 2001, pp. 96-50. (pdf).
-
“Two-bit heros,” The Economist, Janurary 13th, 1996, pp. 78-79. (pdf)
Quantum Algorithms
-
P. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithm on a quantum computer,” SIAM Journal of Computing , 26(5), 1484-1509 (1997).
-
Y. Manin, “Classical computing, quantum computing, and Shor’s factoring algorithm,” quant-ph/9903008.
-
A. Eckert and R. Jozsa: “Quantum Computation and Shor’s Factoring Algorithm,” Rev. Mod. Phys. 68(3), 733-753 (1996).
-
L. Hales and S. Hallgren, “An Improved Quantum Fourier Transform Algorithm and Applications,” Proc. ACM Symposium on Foundations of Computer Science, Nov. 2000. (.ps)
-
S. Hallgren et. al: “Normal Subgroup Reconstruction and Quantum Computation Using Group Representations,” Proc. ACM Symposium on Theory of Computing, 2000. (abstract, .ps)
-
R. Josza, “ Quantum factoring, discrete logarithms and the hidden subgroup problem,”IEEE Computing in Science and Engineering, 2001.
-
M. Grigni et. al, “Quantum mechanical algorithms for the nonabelian hidden subgroup problem,” Proc. ACM Symposium on Theory of Computing 33, 2001. (abstract, .ps)
-
L. K. Grover: “From Schrodinger’s Equation to the Quantum Search Algorithm”, Winter Inst. on Foundations of Quantum Theory, Calcutta, Jan 2000
-
L. K. Grover: “Searching with quantum computers,” Dr. Dobbs, April 2001.
Generic Quantum Logic Circuits
Universality
-
-
A. Barenco et al.: “Elementary gates for quantum computation,” Physical Review A52, 3457 (1995).
-
D. P. DiVincenzo, “Two-bit gates are universal for quantum computation,” Physical Review A 15, 1015 (1995).
-
A. Barenco, D. Deutsch and A. Ekert, “Conditional quantum dynamics and logic gates,” Physical Review Letters 74, 4083 (1995).
-
Yaoyun Shi, “Both Toffoli and Controlled-NOT need little help to do universal quantum computation,” quant-ph/0205115.
-
Dorit Aharonov, “ A Simple Proof that Toffoli and Hadamard are Quantum Universal,” quant-ph/0301040
-
P. O. Boykin, T. Mor, M. Pulver, V. Roychowdhury, F. Vatan, “On Universal and Fault-Tolerant Quantum Computing”, quant-ph/9906054.
-
A. W. Harrow, B. Recht, I. L. Chuang “ Efficient Discrete Approximations of Quantum Gates”, quant-ph/0111031.
-
W. van Dam, M. Mosca, U. Vazirani, “How Powerful is Adiabatic Quantum Computation?” quant-ph/0206003.
-
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.
-
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
-
-
B. Kraus and J.I. Cirac, “Optimal creation of entanglement using a two-qubit gate,”Physical Review A 63, 062309 (2000).
-
K. Hammerer, G. Vidal, and J. I. Cirac, “Characterization of non-local gates,” Physical Review A 66, 062321 (2002).
-
G. Song and A. Klappenecker “Optimal realizations of controlled unitary gates,” quant-ph/0207157.
-
J. Zhang, J. Vala, K. B. Whaley, Sh. Sastry, “A geometric theory of non-local two-qubit operations,” Physical Review A 67, 042313 (2003).
-
J. Zhang, J.Vala, Sh. Sastry, K. B. Whaley “Exact two-qubit universal quantum circuit,” Physical Review Letters 91, 027903 (2003).
-
G. Vidal and C. M. Dawson, “A universal quantum circuit for two-qubit transformations with three CNOT gates,” Physical Review A 69, 010301 (2004)
-
F. Vatan, C. Williams, “Optimal quantum circuits for general two-qubit gates,”Physical Review A 69, 032315 (2004).
-
J. Zhang, J. Vala, Sh. Sastry, K. B. Whaley, “Minimum construction of two-qubit quantum operations,” Physical Review Letters 93, 020502 (2004).
-
Three Qubits
-
-
J. A. Smolin, “Five two-bit quantum gates are sufficient to implement the quantum Fredkin gate”, Physical Review A 5(4), 2855 (1996). (.pdf)
-
D. P. DiVincenzo and John Smolin, “Results on two-bit gate design for quantum computers,” cond-mat/9409111.
-
J. J. Vartiainen, A. O. Niskanen, M. Nakahara, M. M. Salomaa, “Acceleration of quantum algorithms using three-qubit gates,” quant-ph/0310165.
-
F. Vatan, C. Williams, “ Realization of a General Three-Qubit Quantum Gate,” quant-ph/0401178.
-
G. Song and A. Klappenecker, “ The simplified Toffoli gate implementation by Margolus is optimal,” quant-ph/0312225
-
D. Maslov, G. W. Dueck “ Improved Quantum Cost for n-bit Toffoli Gates ,” quant-ph/0403053.
-
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
-
-
E. Knill, “Approximation by Quantum Circuits,” LANL report LAUR-95-2225.
-
G. Cybenko: “Reducing Quantum Computations to Elementary Unitary Operations”, Comp. in Sci. and Engin., March/April 2001, pp. 27-32. (abstract, .pdf)
-
N. Khaneja, R. Brockett, and S.J. Glaser, “Time Optimal Control in Spin Systems,” Phys. Rev A, 63, 032308 (2001).
-
N. Khaneja and St. Glaser, “Cartan Decomposition of SU(2^n), Constructive Controllability of Spin systems and Universal Quantum Computing,” quant-ph/0010100
-
S. S. Bullock, “Note on the Khaneja Glaser Decomposition,” quant-ph/0403141.
-
A. V. Aho, K. M. Svore “ Compiling Quantum Circuits using the Palindrome Transform,” quant-ph/0311008.
-
J. J. Vartiainen, M. Mottonen, and. M. Salomaa “Efficient Decomposition of Quantum Gates,” Physical Review Letters 92, 177902 (2004).
-
M. Mottonen, J. J. Vartiainen, V. Bergholm, M. M. Salomaa, “Universal quantum computation,” quant-ph/0404089.
-
Circuit Blocks (Arithmetic ops, Fourier Transform, etc)
-
-
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.
-
Th. G. Draper, S. A. Kutin, E. M. Rains, K. M. Svore “ A logarithmic-depth quantum carry-lookahead adder,” quant-ph/0404162.
-
V. Vedral, A. Barenko and A. Eckert, “Quantum Networks for Elementary Arithmetic Operations,” quant-ph/9511018.
-
R. Cleve and J. Watrous. “Fast parallel circuits for the quantum Fourier transform” (.ps), FOCS, pages 526-536, 2000.
-
St. Beauregard, “Circuit for Shor’s algorithm using 2n+3 qubits,” Quantum Information and Computation 3(2), 175 (2003).
- 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.
- D. Maslov, G. W. Dueck, “ Improved Quantum Cost for n-bit Toffoli Gates”, quant-ph/0403053.
- T. Hogg, C. Mochon, W. Polak, E. Rieffel “ Tools for Quantum Algorithms”, Int.J.Mod.Phys. C10 (1999) 1347-1362, quant-ph/9811073.
-
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
-
Other
-
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)
-
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
-
M. Steffen et al.: “Toward Quantum Computation: a Five-qubit Quantum Processor,”IEEE Micro, March-April 2001, pp. 24-34. (abstract, pdf)
-
L. M. K. Vandersypen et al., “NMR quantum computing: realizing Shor’s algorithm,”Nature 20/27, December 2001.
-
D. Kielpinski, C. Monroe and D. J. Wineland, “ Architecture for a large-scale ion-trap quantum computer,” Nature 417, 709 (2002). (.ps)
-
Philip Ball, “Silicon quantum computer,” Nature News Service.
-
S. Bettelli, L. Serafini, T. Calarco, “Toward an architecture for quantum programming,” European Physics Journal D 25(2), 181 (2003).
-
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).
-
L. M. K. Vandersypen, I. L. Chuang, “ NMR Techniques for Quantum Control and Computation,” quant-ph/0404064.
Noise and Error Correction
-
D. Aharonov, M. Ben-Or, “Fault-Tolerant Quantum Computation With Constant Error Rate,” quant-ph/9906129.
-
D. Gottesman, “The Heisenberg Representation of Quantum Computers,” LAUR-98-2848.
-
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.
-
N. Shenvi, K. R. Brown, K. B. Whaley, “Effects of Noisy Oracle on Search Algorithm Complexity,” quant-ph/0304138.
-
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
-
D. Gottesman, “The Heisenberg Representation of Quantum Computers,” LAUR-98-2848.
-
S. Aaronson and D. Gottesman, “Improved Simulation of Stabilizer Circuits Representation of Quantum Computers”, quant-ph/0406196
-
R. Josza and N. Linden, “On the Role of Entanglement in Quantum Computational Speed-up”, quant-ph/0201143.
-
G. Vidal, Efficient classical simulation of slightly entangled quantum computations , Phys. Rev. Lett. 91, 147902 (2003), quant-ph/0301063
-
G. Vidal, Efficient simulation of one-dimensional quantum many-body systems , quant-ph/0310089
-
Quantum Computer Architecture Simulator (ARQ) from Chuang’s group at MIT.
-
Quantum Computer Emulator from de Raedt’s group.
Classical Computation
-
G. Hachtel and F. Somenzi, “Logic Synthesis and Verification Algorithms”, 3 ed., 2000
-
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)
-
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)
-
V. Kravets: “Constructive Multi-Level Synthesis by Way of Functional Properties.” (abstract, pdf)
-
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)
-
A. Mishchenko: “An Introduction to Zero-suppressed Binary Decision Diagrams,” 2001. (pdf)
-
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)
-
T. Toffoli, “Reversible Computing,” Tech. Memo MIT/LCS/TM-151, MIT Lab for Comp. Sci, 1980. (36 p.) (pdf)
-
M. Perkowski et al., “A General Decomposition For Reversible Logic,” Reed-Muller workshop, Aug. 2001. (18 p., pdf 1 pdf 2)
-
K. Iwama, Y. Kambayashi, S. Yamashita, “Transformation Rules For Designing CNOT-based Quantum Circuits,” Design Autom. Conf. (DAC) 2002, pp. 419-425. (pdf)
-
Jae-Seung Lee, “A Practical Method of Constructing Quantum Combinational Logic Circuits,” quant-ph/9911053.
Matrix Decomposition Techniques
-
V. Pan: “Nearly Optimal Computations With Structured Matrices,” Proc. ACM-SIAM Symposium on Discrete Algorithms 11, San Francisco, CA (2000). (abstract, pdf)
-
S. Egner et. al: “Decomposing a Permutation into a Conjugated Tensor Product,” International Symposium on Symbolic and Algebraic Computation, 1997. (abstract, .ps)
-
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
-
B. Eastin, S. T. Flammia, “Q-circuit Tutorial,” quant-ph/0406003.