Quantum Fan-out is Powerful

by Peter Høyer and Robert Špalek

Theory of Computing, Volume 1(5), pp. 81-103, 2005

Bibliography with links to cited articles

[1]   L. M. Adleman, J. DeMarrais, and M. A. Huang: Quantum computability. SIAM Journal on Computing, 26(5):1524–1540, 1997. [SICOMP:29363].

[2]   A. Barenco, C. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter: Elementary gates for quantum computation. Physical Review A, 52:3457–3467, 1995. [PRA:10.1103/PhysRevA.52.3457, arXiv:quant-ph/9503016].

[3]   R. Beigel: The polynomial method in circuit complexity. In Proc. of 8th IEEE Structure in Complexity Theory Conf., pp. 82–95, 1993. [1993.336538].

[4]   J. I. Cirac and P. Zoller: Quantum computations with cold trapped ions. Phys. Rev. Lett., 74:4091–4094, 1995. [PRL:10.1103/PhysRevLett.74.4091].

[5]   R. Cleve and J. Watrous: Fast parallel circuits for the quantum Fourier transform. In Proc. of 41st IEEE FOCS, pp. 526–536, 2000. [FOCS:10.1109/SFCS.2000.892140].

[6]   D. Coppersmith: An approximate Fourier transform useful in quantum factoring. IBM technical report RC19642, quant-ph/0201067, 1994. [arXiv:quant-ph/0201067].

[7]   M. Fang, S. Fenner, F. Green, S. Homer, and Y. Zhang: Quantum lower bounds for fanout. 2003. [arXiv:quant-ph/0312208].

[8]   S. A. Fenner: Implementing the fanout gate by a Hamiltonian. 2003. [arXiv:quant-ph/0309163].

[9]   N. Gershenfeld and I. Chuang: Bulk spin resonance quantum computation. Science, 275:350–356, 1997. [doi:10.1126/science.275.5298.350].

[10]   F. Green, S. Homer, C. Moore, and C. Pollett: Counting, fanout, and the complexity of quantum ACC. Quantum Information and Computation, 2(1):35–65, 2002. [arXiv:quant-ph/0106017].

[11]   L. Hales and S. Hallgren: Quantum Fourier sampling simplified. In Proc. of 31st ACM STOC, pp. 330–338, 1999. [STOC:301250.301336].

[12]   W. Hoeffding: Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc., 58:13–30, 1963.

[13]   R. A. Horn and C. R. Johnson: Matrix Analysis. Cambridge University Press, 1985.

[14]   P. Høyer and R. Špalek: Quantum circuits with unbounded fan-out. In Proc. of 20th STACS, pp. 234–246, 2003. LNCS 2607. [STACS:80j4ju67n25kcf06].

[15]   K. Mølmer and A. Sørensen: Multiparticle entanglement of hot trapped ions. Phys. Rev. Lett., 82:1835–1838, 1999. [PRL:10.1103/PhysRevLett.82.1835].

[16]   C. Moore: Quantum circuits: Fanout, parity, and counting. 1999. [arXiv:quant-ph/9903046].

[17]   C. Moore and M. Nilsson: Parallel quantum computation and quantum codes. SIAM Journal on Computing, 31(3):799–815, 2002. [SICOMP:35505, arXiv:quant-ph/9808027].

[18]   A. A. Razborov: Lower bounds for the size of circuits of bounded depth with basis {&,⊕}. Math. Notes Acad. Sci. USSR, 41(4):333–338, 1987.

[19]   P. W. Shor: Algorithms for quantum computation: discrete logarithms and factoring. In Proc. of 35th IEEE FOCS, pp. 124–134, 1994. [FOCS:10.1109/SFCS.1994.365700].

[20]   K.-Y. Siu, J. Bruck, T. Kailath, and T. Hofmeister: Depth efficient neural networks for division and related problems. IEEE Transactions on Information Theory, 39(3):946–956, 1993. [TIT:10.1109/18.256501].

[21]   R. Smolensky: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proc. of 19th ACM STOC, pp. 77–82, 1987. [STOC:28395.28404].

[22]   R. Špalek: Quantum circuits with unbounded fan-out. Master’s thesis, Faculty of Sciences, Vrije Universiteit, Amsterdam, 2002. Shorter version and improved results in quant-ph/0208043. [arXiv:quant-ph/0208043].

[23]   W. K. Wootters and W. H. Zurek: A single quantum cannot be cloned. Nature, 299:802–803, 1982. [doi:10.1038/299802a0].

[24]   A. C-C. Yao: Probabilistic computations: Toward a unified measure of complexity. In Proc. of 18th IEEE FOCS, pp. 222–227, 1977.