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
A. Barenco et al.: “ Elementary gates for quantum computation ,” Physical Review A 52 , 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).
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.
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. Reversible Computers at Ghent 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.