Relativized separation of EQP from \(\text{P}^{\text{NP}}\)

DOI10.1016/S0020-0190(01)00176-4zbMath1003.68053MaRDI QIDQ1607126

Frederic Green, Randall Pruim

Publication date: 25 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

quantum polynomial time

Mathematics Subject Classification ID

Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

THE DEUTSCH–JOZSA ALGORITHM REVISITED IN THE DOMAIN OF CRYPTOGRAPHICALLY SIGNIFICANT BOOLEAN FUNCTIONS ⋮ ANALYSIS OF QUANTUM FUNCTIONS ⋮ Quantum and classical complexity classes: Separations, collapses, and closure properties ⋮ Error-bounded probabilistic computations between MA and AM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Approximation Algorithms for # P
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Oracle Quantum Computing
• Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy