Computer Science

Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy

Document Type

Article

Abstract

It is shown that determining whether a quantum computation has a non-zero probability of accepting is at least as hard as the polynomial-time hierarchy. This hardness result also applies to determining in general whether a given quantum basis state appears with non-zero amplitude in a superposition, or whether a given quantum bit has positive expectation value at the end of a quantum computation. This result is achieved by showing that the complexity class NQP (a quantum analogue of NP) of Adleman, Démarrais and Huang is equal to the counting class coC-P. © 1999 The Royal Society.

Publication Title

Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences

Publication Date

1999

Volume

455

Issue

1991

First Page

3953

Last Page

3966

ISSN

1364-5021

DOI

10.1098/rspa.1999.0485

Keywords

complexity theory, polynomial-time hierarchy, quantum computing, quantum np

APA Citation

Fenner, S., Green, F., Homer, S., & Pruim, R. (1999). Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 455(1991), 3953-3966.

Link to Full Text

Share

COinS