Quantum Depth in the Random Oracle Model

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

2023 · 11 citations · 22 references

DOIFull text

Open access

Concepts

Abstract

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:

References

22