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.