Title | Quantum Depth in the Random Oracle Model |

Publication Type | Journal Article |

Year of Publication | 2022 |

Authors | Arora, ASingh, Coladangelo, A, Coudron, M, Gheorghiu, A, Singh, U, Waldner, H |

Date Published | 10/12/2022 |

Keywords | Computational Complexity (cs.CC), Cryptography and Security (cs.CR), FOS: Computer and information sciences, FOS: Physical sciences, Quantum Physics (quant-ph) |

Abstract | We give a comprehensive characterization 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: |

URL | https://arxiv.org/abs/2210.06454 |

DOI | 10.48550/ARXIV.2210.06454 |