Ethan Bernstein
- BM88.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. Google Scholar
Digital Library
- Be73.C.Bennett. "Logical reversibility of comput, ation "" IBM J. Res. De'#,elop., Vol. 17. 1973, pp. 525-532.Google ScholarDigital Library
- BB92a.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.Google Scholar
- BB92b.A.Berthia,ume and G.Bra.ssard. "Oracle quantum computing '" Proceed#gs of th# Physzcs of Computations, Dallas, 1992.Google Scholar
- De85.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.Google ScholarCross Ref
- De89.D.Deut.sch. "Quantum computa.tional networks." Proc. R. Soc. Lond., Vol. A425. 1989, pp. 73-90.Google Scholar
- DJ91.D.Deutsch and R.Jozsa. "'Rapid solution of problems by quant, um computation '" Proc. R. Soc. Lond. Vol. A439. 1992, pp. 55.3-558.Google Scholar
- Fe82.R.Feynman. "Simula.t, ing physics with computers "' International Journal of Theoretical Phys.lcs, Vol. 21, nos. 6/7, 1982, pp. 467-488.Google ScholarCross Ref
- Jo91.R.Jozsa. "Characterizing classes of functions comput, able by quantum pa.rallelism "" Proc. R. Soc. Lond. Vol. A435, 1991, pp. 563-574.Google ScholarCross Ref
- Va92.L.Valiant. Personal communication, 1992.Google Scholar
Index Terms
- Quantum complexity theory
Recommendations
Quantum Complexity Theory
In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 ...
Quantum Kolmogorov complexity based on classical descriptions
We develop a theory of the algorithmic information in bits contained in an individual pure quantum state. This extends classical Kolmogorov complexity to the quantum domain retaining classical descriptions. Quantum Kolmogorov complexity coincides with ...
Comments