Parallelization, amplification, and exponential time simulation of quantum interactive proof systems

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	Dorit Aharonov , Alexei Kitaev , Noam Nisan, Quantum circuits with mixed states, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.20-30, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276708]
	2	F. Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization, 5(1):13-51, 1995.
	3	L Babai, Trading group theory for randomness, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.421-429, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22192]
	4	L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 1(1):3-40, 1991.
	5	A. Barenco. A universal two-bit gate for quantum computation. Proceedings of the Royal Society of London, 449:679-683, 1995.
	6	A. Barenco, C. H. Bennett, R. Cleve, D. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin, and H. Weinfurter. Elementary gates for quantum computation. Physical Review Letters A, 52:3457-3467, 1995.
	7	Ethan Bernstein , Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, v.26 n.5, p.1411-1473, Oct. 1997 [doi>10.1137/S0097539796300921]
	8	André Berthiaume, Quantum computation, Complexity theory retrospective II, Springer-Verlag New York, Inc., New York, NY, 1998
	9	J. Cai, A. Condon, and R. Lipton. On bounded round multi-prover interactive proof systems. In Proceedings of the Fifth Annual Conference on Structure in Complexity Theory, pages 45-54, 1990.
	10	D. Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London, A400:97-117, 1985.
	11	D. Deutsch. Quantum computational networks. Proceedings of the Royal Society of London, A425:73-90, 1989.
	12	D. DiVincenzo. Two-bit gates are universal for quantum computation. Physical Review A, 50:1015-1022, 1995.
	13	U. Feige. On the success probability of two provers in one-round proof systems. In Proceedings of the Sixth Annual Conference on Structure in Complexity Theory, pages 116-123, 1991.
	14	Uriel Feige , László Lovász, Two-prover one-round proof systems: their power and their problems (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.733-744, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129783]
	15	C. Fuchs and J. van de Graaf. Cryptographic distinguishability measures for quantum-mechanical states. IEEE Transactions on Information Theory, 45(4):1216-1227, 1999.
	16	Oded Goldreich, A taxonomy of proof systems, Complexity theory retrospective II, Springer-Verlag New York, Inc., New York, NY, 1998
	17	S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
	18	S. Goldwasser and M. Sipser. Private coins versus public coins in interactive proof systems. In S. Micali, editor, Randomness and Computation, volume 5 of Advances in Computing Research, pages 73-90. JAI Press, 1989.
	19	M. GrStschel, L. Lov~sz, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1, 1981.
	20	Roger A. Horn , Charles R. Johnson, Matrix analysis, Cambridge University Press, New York, NY, 1985
	21	L. Hughston, R. Jozsa, and W. Wootters. A complete classification of quantum ensembles having a given density matrix. Physics Letters A, 183:14-18, 1993.
	22	R. Jozsa. Fidelity for mixed quantum states. Journal of Modern Optics, 41(12):2315-2323, 1994.
	23	A. Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52(6):1191-1249, 1997.
	24	Dror Lapidot , Adi Shamir, Fully parallelized multi prover protocols for NEXP-time (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.13-18, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185342]
	25	Carsten Lund , Lance Fortnow , Howard Karloff, Algebraic methods for interactive proof systems, Journal of the ACM (JACM), v.39 n.4, p.859-868, Oct. 1992 [doi>10.1145/146585.146605]
	26	Adi Shamir, IP = PSPACE, Journal of the ACM (JACM), v.39 n.4, p.869-877, Oct. 1992 [doi>10.1145/146585.146609]
	27	P. W. Shor, Fault-tolerant quantum computation, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.56, October 14-16, 1996
	28	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]
	29	Lieven Vandenberghe , Stephen Boyd, Semidefinite programming, SIAM Review, v.38 n.1, p.49-95, Mar. 1996 [doi>10.1137/1038003]
	30	John Watrous, PSPACE Has Constant-Round Quantum Interactive Proof Systems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.112, October 17-18, 1999
	31	A. Yao. Quantum circuit complexity. In Proceedings of the 3jth Annual Symposium on Foundations of Computer Science, pages 352-361, 1993.