On the need for large quantum depth

DOI10.1145/3570637MaRDI QIDQ6567267zbMATH OpenFDO

Authors Nai-Hui Chia, Kai-Min Chung, Ching-Yi Lai

Publication date 4 July 2024

Published in Journal of the ACM (Search for Journal in Brave)

zbMATH Keywords

oracle separationd-shuffling Simon's problemhybrid quantum-classical computernear-term quantum computersmall-depth quantum circuit

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• On the need for large Quantum depth
• Computational Depth Complexity of Measurement-Based Quantum Computation
• Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games
• Oracle Separation of BQP and PH
• Oracle separation of BQP and PH

Cites work

• scientific article; zbMATH DE number 1962817 (Why is no real title available?)
• Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games
• BQP and the polynomial hierarchy
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.
• Complexity-theoretic foundations of quantum supremacy experiments
• Computational Complexity
• Computations with greater Quantum depth are strictly more powerful (relative to an oracle)
• Exponential algorithmic speedup by a quantum walk
• Parallel quantum computation and quantum codes
• Quantum computing and hidden variables
• Quantum fan-out is powerful
• Quantum security proofs using semi-classical oracles
• Random Oracles and Auxiliary Input
• Random oracles and non-uniformity
• Revocable Quantum Timed-Release Encryption
• The impossibility of obfuscation with auxiliary input or a universal simulator

Cited in

(2)

• Quantum complexity for discrete logarithms and related problems
• The NISQ complexity of collision finding

This page was built for publication: On the need for large quantum depth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6567267)