Quantum complexity theory. (English) Zbl 1310.68080
Proceedings of the 25th annual ACM symposium on theory of computing, STOC ’93. San Diego, CA, USA, May 16–18, 1993. New York, NY: Association for Computing Machinery (ACM) (ISBN 0-89791-591-7). 11-20 (1993).
For the entire collection see [Zbl 1285.68003].
MSC:
| 68Q12 | Quantum algorithms and complexity in the theory of computing |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
References:
| [1] | L.Babai and S.Moran. “Arthur- Merlin games: a randomized proof system, and a. hierarchy of complexit, y classes ” dourhal of Comp#tler and System Sciences, Vol. 36, 1988, pp. 254-276. 10.1016/0022-0000(88)90028-1 · Zbl 0652.03029 |
| [2] | C.Bennett. “Logical reversibility of comput, ation ” IBM J. Res. De’#,elop., Vol. 17. 1973, pp. 525-532. · Zbl 0267.68024 |
| [3] | A.Berthiaume a,nd G.Brassard. “The quantum challenge to structural complexit.y theory.” Proceedings of 7th IEEE CoT@rencc o7# Structure t# Complexzty Theory, 1992. |
| [4] | A.Berthia,ume and G.Bra.ssard. “Oracle quantum computing ” Proceed#gs of th# Physzcs of Computations, Dallas, 1992. |
| [5] | D.Deutsch. “’Qua.ntuna theory, the Church- Turing principle and the universa.1 quant, um comput.er” Proc. R. Soc. Lond., Vol. A400, 1985, pp. 97-117. · Zbl 0900.81019 |
| [6] | D.Deut.sch. “Quantum computa.tional networks.” Proc. R. Soc. Lond., Vol. A425. 1989, pp. 73-90. · Zbl 0691.68054 |
| [7] | D.Deutsch and R.Jozsa. “’Rapid solution of problems by quant, um computation ” Proc. R. Soc. Lond. Vol. A439. 1992, pp. 55.3-558. · Zbl 0792.68058 |
| [8] | R.Feynman. “Simula.t, ing physics with computers ” International Journal of Theoretical Phys.lcs, Vol. 21, nos. 6/7, 1982, pp. 467-488. |
| [9] | R.Jozsa. “Characterizing classes of functions comput, able by quantum pa.rallelism ” Proc. R. Soc. Lond. Vol. A435, 1991, pp. 563-574. · Zbl 0774.68087 |
| [10] | L.Valiant. Personal communication, 1992. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
