Small depth quantum circuits

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Small depth quantum circuits

Full text

Pdf (774 KB)

Source

ACM SIGACT News archive
Volume 38 , Issue 2 (June 2007) table of contents

COLUMN: SIGACT news complexity theory column 55 table of contents

Pages: 35 - 50

Year of Publication: 2007

ISSN:0163-5700

Authors

Debajyoti Bera	Boston University
Frederic Green	Clark University
Steven Homer	Boston University

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 36, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1272729.1272739 What is a DOI?

ABSTRACT

Small depth quantum circuits have proved to be unexpectedly powerful in comparison to their classical counterparts. We survey some of the recent work on this and present some open problems.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Leonard M. Adleman , Jonathan DeMarrais , Ming-Deh A. Huang, Quantum Computability, SIAM Journal on Computing, v.26 n.5, p.1524-1540, Oct. 1997 [doi>10.1137/S0097539795293639]
	2	A. Barenco, C. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weifurter. "Elementary gates for quantum computation". Phys. Rev. A, 52:3457--3467, 1995.
	3	J. I. Cirac and P. Zoller. "Quantum computers with cold trapped ions". Phys. Rev. Lett., 74:4091--4094, 1995.
	4	R. Cleve , J. Watrous, Fast parallel circuits for the quantum Fourier transform, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.526, November 12-14, 2000
	5	V. Coffman, J. Kundu, and W. K. Wootters. "Distributed Entanglement". Phys. Rev. A, 61, 052306, 2000.
	6	D. Coppersmith. "An approximate Fourier transform useful in quantum factoring". IBM technical report RC19642, quant-ph/0201067, 1994.
	7	S. Fenner. "A physics-free introduction to the quantum computation model", Computational Complexity Column. Bulletin of EATCS, 79:69--85, 2003.
	8	M. Fang, S. Fenner, F. Green, S. Homer, and Y. Zhang. "Quantum lower bounds for fanout". Quantum Information and Computation, 6(1):046--057, 2006.
	9	S. Fenner, F. Green, S. Homer, and R. Pruim. "Quantum NP is hard for PH". Proceedings of 6th Italian Conference on theoretical Computer Science, World Scientific, Singapore, pages 241--252, 1998.
	10	L. Fortnow , J. Rogers, Complexity Limitations on Quantum Computation, Proceedings of the Thirteenth Annual IEEE Conference on Computational Complexity, p.202, June 15-18, 1998
	11	M. Furst, J. B. Saxe, and M. Sipser. "Parity, circuits, and the polynomial-time hierarchy". Math. Syst. Theory, 17:13--27, 1984.
	12	N. Gershenfeld and I. Chuang. "Bulk spin resonance quantum computation". Science, 275:350--356, 1997.
	13	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.
	14	P. Høyer and R. Špalek. "Quantum fan-out is powerful". Theory of Computing, 1:81--103, 2005.
	15	Cristopher Moore. "Quantum Circuits: Fanout, Parity, and Counting". In Los Alamos Preprint archives quant-ph/9903046, 1999.
	16	Cristopher Moore and Martin Nilsson. "Parallel Quantum Computation and Quantum Codes". In Los Alamos Preprint archives quant-ph/9808027, 1998.
	17	Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
	18	Noam Nisan, CREW PRAMs and decision trees, SIAM Journal on Computing, v.20 n.6, p.999-1007, Dec. 1991 [doi>10.1137/0220062]
	19	Harumichi Nishimura , Masanao Ozawa, Computational complexity of uniform quantum circuit families and quantum Turing machines, Theoretical Computer Science, v.276 n.1-2, p.147-181, April 6, 2002 [doi>10.1016/S0304-3975(01)00111-6]
	20	S. Parker and M. B. Plenio. "Efficient factorization with a single pure qubit and logN Mixed qubits". Physics Review Letters, 85(14):3049--3052, Oct 2000.
	21	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.
	22	Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
	23	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.
	24	R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.77-82, January 1987, New York, New York, United States [doi>10.1145/28395.28404]
	25	R. Špalek. "Quantum Circuits with Unbounded Fan-out". Master's Thesis, Faculty of Sciences, Vrije Universiteit, Amsterdam, 2002.
	26	Heribert Vollmer, Introduction to Circuit Complexity: A Uniform Approach, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
	27	A. C.-C. Yao. "Quantum circuit complexity". In Proceedings of the 34th IEEE Symposium on Foundations of Computer Science, pages 352--361, 1993.