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

DOI10.1098/rspa.1999.0485zbMath0964.68011arXivquant-ph/9812056OpenAlexW2111166346MaRDI QIDQ4946417

Frederic Green, Randall Pruim, Homer, Steven, Stephen A. Fenner

Publication date: 22 March 2000

Published in: Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/quant-ph/9812056

zbMATH Keywords

quantum computationpolynomial-time hierarchy

Mathematics Subject Classification ID

Quantum computation (81P68) General topics in the theory of software (68N01)

Related Items (8)

Quantum weakly nondeterministic communication complexity ⋮ ANALYSIS OF QUANTUM FUNCTIONS ⋮ Efficient verification of Tunnell's criterion ⋮ Quantum computing, postselection, and probabilistic polynomial-time ⋮ Sumcheck-based delegation of quantum computing to rational server ⋮ A common algebraic description for probabilistic and quantum computations ⋮ Relativized separation of EQP from \(\text{P}^{\text{NP}}\) ⋮ One complexity theorist's view of quantum computing

This page was built for publication: Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy