2023 · 11 citations · 22 references
ComputingComputer ScienceCryptographyQuantum ComputingTheory Of ComputationCircuit ComplexityQuantum CircuitsQuantum Complexity TheoryQuantum ComputationQuantum CryptographyQuantum Information TheoryBqpQipQuantum Circuit Depth ReductionQuantum Circuit ModelQuantum Complexity ClassesRandom Oracle ModelSearch Problems
We give a comprehensive characterisation of the computational power of shallow quantum circuits combined with classical computation. Specifically, for classes of search problems, we show that the following statements hold, relative to a random oracle:
22
A variational eigenvalue solver on a photonic quantum processor
Alberto Peruzzo, Jarrod R. McClean, Peter Shadbolt et al. · Nature Communications · 2014 · 4.6K citations · Full text
Natural Sciences, Chemistry, Physics +17
Generating hard instances of lattice problems (extended abstract)
Miklós Ajtai · 1996 · 1.3K citations · Full text
On the Power of Quantum Computation
Daniel Simón · SIAM Journal on Computing · 1997 · 1.3K citations
Computing, Computer Science, Physics +14
Measurement-based quantum computation
Hans J. Briegel, Dan E. Browne, Wolfgang Dür et al. · Nature Physics · 2009 · 1.1K citations · Full text
Computing, Computer Science, Physics +15
The random oracle methodology, revisited
Ran Canetti, Oded Goldreich, Shai Halevi · Journal of the ACM · 2004 · 978 citations · Full text