Quantum depth in the random oracle model

DOI10.1145/3564246.3585153MaRDI QIDQ6499289zbMATH OpenWikidataFDO

Authors Atul Singh Arora, Andrea Coladangelo, Matthew Coudron, Alexandru Gheorghiu, Uttam Singh, Hendrik Waldner

Publication date 8 May 2024

Full work available at URL https://doi.org/10.1145/3564246.3585153

zbMATH Keywords

hybrid classical-quantum models of computationproof of quantum depthrandom oracle model

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• BQP and the polynomial hierarchy
• Circuit depth relative to a random oracle
• Classical vs quantum random oracles
• Computations with greater Quantum depth are strictly more powerful (relative to an oracle)
• Cryptography in NC^0
• Exponential algorithmic speedup by a quantum walk
• Forrelation: a problem that optimally separates quantum from classical computing
• From obfuscation to the security of Fiat-Shamir for proofs
• How to record quantum queries, and applications to quantum indifferentiability
• scientific article; zbMATH DE number 5899272 (Why is no real title available?)
• scientific article; zbMATH DE number 2132450 (Why is no real title available?)
• scientific article; zbMATH DE number 1256724 (Why is no real title available?)
• scientific article; zbMATH DE number 1775384 (Why is no real title available?)
• scientific article; zbMATH DE number 7651035 (Why is no real title available?)
• Natural proofs
• Noninteractive zero knowledge for NP from (Plain) Learning With Errors
• On the (im)possibility of obfuscating programs
• On the compressed-oracle technique, and post-quantum security of proofs of sequential work
• On the correlation intractability of obfuscated pseudorandom functions
• On the need for large Quantum depth
• On the Power of Quantum Computation
• On the security of proofs of sequential work in a post-quantum world
• Parity, circuits, and the polynomial-time hierarchy
• Quantum lower bounds for the collision and the element distinctness problems
• Quantum security proofs using semi-classical oracles
• Random oracles and non-uniformity
• The impossibility of obfuscation with auxiliary input or a universal simulator
• The need for structure in quantum speedups
• The random oracle methodology, revisited.
• Time-lock puzzles from randomized encodings
• Verifiable delay functions

Cited in

(4)

• Quantum circuit completeness: extensions and simplifications
• Quantum cryptography and meta-complexity
• Quantum algorithms for longest common and palindromic substrings in the circuit model
• Verifiable quantum advantage without structure

This page was built for publication: Quantum depth in the random oracle model

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