On the need for large quantum depth

DOI10.1145/3570637MaRDI QIDQ6567267FDOQ6567267

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)

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

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)

Cites Work

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

Cited In (2)

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

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)