Quantum circuits with mixed states

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Quantum circuits with mixed states

Full text

Pdf (1.32 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 20 - 30

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Dorit Aharonov	Institutes of Physics and Computer Science, The Hebrew University, Jerusalem, Israel
Alexei Kitaev	L.D.Landau Institute for Theoretical Physics, Moscow, Russia
Noam Nisan	Institute of Computer Science, The Hebrew University, Jerusalem, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 53, Citation Count: 23

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/276698.276708 What is a DOI?

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	D. Aharonov , M. Ben-Or, Fault-tolerant quantum computation with constant error, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.176-188, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258579]
	2	Charles H. Bennett , Ethan Bernstein , Gilles Brassard , Umesh Vazirani, Strengths and Weaknesses of Quantum Computing, SIAM Journal on Computing, v.26 n.5, p.1510-1523, Oct. 1997 [doi>10.1137/S0097539796300933]
	3	Ethan Bernstein , Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, v.26 n.5, p.1411-1473, Oct. 1997 [doi>10.1137/S0097539796300921]
	4	D. Deutsch. Quantum theory, the church-turlng prin. ciple and the universal quantum computer. In Proc. Roy. Soc. Lond, Vol. A400, 1935.
	5	R. Feymnan. Simulating physics with computers. In International Journal of Theoretical Physics, Vol. 21, No. 6/7, pages 467-488, 1982.
	6	L. Grover. Quantum mechanics helps in searching for a needle in a haystack, quant-ph}9605043, phys. rev. lett. 79, 325-328.
	7	I<. HeUwig and K. i<raus. Communications in mathcmatical physics, 16 142 (1970) , m.d. chi, linear algebra and its app~cations 10 286 (1975), k. kraus, states, effects and operations: Foundamental notions of quantum theory(springer-verlag, berlin, 1983), b. sdmreacher, sending entanglement through noisy quantum channels quant-ph/9604023, volume 16, 142 (1970).
	8	J.J.Saqurai. Modern Quantum Mechanics, rcviocd cdi. tion. Addison Wesley, 1994.
	9	A. Kitaev. Quantum error correction with imperfect gates, manuscript, 1997.
	10	E. KniU, R. Lafiamme, and W.H. Zurek. Resillant quantum computation. Science, 279, pp 342, 1998.
	11	P. W. Shor, Fault-tolerant quantum computation, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.56, October 14-16, 1996
	12	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]
	13	Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing, v.26 n.5, p.1474-1483, Oct. 1997 [doi>10.1137/S0097539796298637]
	14	A. Yao. Quantum circuit complexity. In 8$th An. nual Symposium on Foundations of Computer Scicnec, pages 352-361, 1993.

CITED BY 23

	Dorit Aharonov , Amnon Ta-Shma , Umesh V. Vazirani , Andrew C. Yao, Quantum bit escrow, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.705-714, May 21-23, 2000, Portland, Oregon, United States
	Alexei Kitaev , John Watrous, Parallelization, amplification, and exponential time simulation of quantum interactive proof systems, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.608-617, May 21-23, 2000, Portland, Oregon, United States
	Andris Ambainis, A new protocol and lower bounds for quantum coin flipping, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.134-142, July 2001, Hersonissos, Greece
	Andris Ambainis , Ashwin Nayak , Amnon Ta-Shma , Umesh Vazirani, Dense quantum coding and quantum finite automata, Journal of the ACM (JACM), v.49 n.4, p.496-511, July 2002
	Hartmut Klauck, On quantum and probabilistic communication: Las Vegas and one-way protocols, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.644-651, May 21-23, 2000, Portland, Oregon, United States
	Andris Ambainis, A new protocol and lower bounds for quantum coin flipping, Journal of Computer and System Sciences, v.68 n.2, p.398-416, March 2004
	Wim van Dam , Frédéic Magniez , Michele Mosca , Miklos Santha, Self-testing of universal and fault-tolerant sets of quantum gates, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.688-696, May 21-23, 2000, Portland, Oregon, United States
	Hartmut Klauck , Ashwin Nayak , Amnon Ta-Shma , David Zuckerman, Interaction in quantum communication and the complexity of set disjointness, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.124-133, July 2001, Hersonissos, Greece
	Hartmut Klauck, Quantum time-space tradeoffs for sorting, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Hirotada Kobayashi , Keiji Matsumoto, Quantum multi-prover interactive proof systems with limited prior entanglement, Journal of Computer and System Sciences, v.66 n.3, p.429-450, May 2003
	John Watrous, On the complexity of simulating space-bounded quantum computations, Computational Complexity, v.12 n.1/2, p.48-84, July 2004
	Andris Ambainis , John Watrous, Two-way finite automata with quantum and classical states, Theoretical Computer Science, v.287 n.1, p.299-311, 25 September 2002
	Yaoyun Shi, Tensor norms and the classical communication complexity of nonlocal quantum measurement, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Martin Sauerhoff , Detlef Sieling, Quantum branching programs and space-bounded nonuniform quantum complexity, Theoretical Computer Science, v.334 n.1-3, p.177-225, 11 April 2005
	John Watrous, PSPACE has constant-round quantum interactive proof systems, Theoretical Computer Science, v.292 n.3, p.575-588, 31 January 2003
	John Watrous, Zero-knowledge against quantum attacks, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	François Le Gall, Exponential separation of quantum and classical online space complexity, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Paolo Zuliani, Quantum Programming With Mixed States, Electronic Notes in Theoretical Computer Science (ENTCS), 170, p.185-199, March, 2007
	Dorit Aharonov , Andris Ambainis , Julia Kempe , Umesh Vazirani, Quantum walks on graphs, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.50-59, July 2001, Hersonissos, Greece
	Juliana Vizzotto , Thorsten Altenkirch , Amr Sabry, Structuring quantum effects: superoperators as arrows, Mathematical Structures in Computer Science, v.16 n.3, p.453-468, June 2006
	Pranab Sen , S. Venkatesh, Lower bounds for predecessor searching in the cell probe model, Journal of Computer and System Sciences, v.74 n.3, p.364-385, May, 2008
	Rūsiņš Freivalds , Māris Ozols , Laura Mančinska, Improved constructions of mixed state quantum automata, Theoretical Computer Science, v.410 n.20, p.1923-1931, May, 2009
	Ilze Dzelme-Brzia, Mathematical logic and quantum finite state automata, Theoretical Computer Science, v.410 n.20, p.1952-1959, May, 2009