@article {3137, title = {Quantum Depth in the Random Oracle Model}, year = {2022}, month = {10/12/2022}, 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:
(a) BPPQNCBPP\≠BQP. This refutes Jozsa\&$\#$39;s conjecture [QIP 05] in the random oracle model. As a result, this gives the first instantiatable separation between the classes by replacing the oracle with a cryptographic hash function, yielding a resolution to one of Aaronson\&$\#$39;s ten semi-grand challenges in quantum computing.
(b) BPPQNC⊈QNCBPP and QNCBPP⊈BPPQNC. This shows that there is a subtle interplay between classical computation and shallow quantum computation. In fact, for the second separation, we establish that, for some problems, the ability to perform adaptive measurements in a single shallow quantum circuit, is more useful than the ability to perform polynomially many shallow quantum circuits without adaptive measurements.
(c) There exists a 2-message proof of quantum depth protocol. Such a protocol allows a classical verifier to efficiently certify that a prover must be performing a computation of some minimum quantum depth. Our proof of quantum depth can be instantiated using the recent proof of quantumness construction by Yamakawa and Zhandry [STOC 22].

}, keywords = {Computational Complexity (cs.CC), Cryptography and Security (cs.CR), FOS: Computer and information sciences, FOS: Physical sciences, Quantum Physics (quant-ph)}, doi = {10.48550/ARXIV.2210.06454}, url = {https://arxiv.org/abs/2210.06454}, author = {Arora, Atul Singh and Coladangelo, Andrea and Coudron, Matthew and Gheorghiu, Alexandru and Singh, Uttam and Waldner, Hendrik} } @article {3009, title = {Self-Testing of a Single Quantum System: Theory and Experiment}, year = {2022}, month = {3/17/2022}, abstract = {

Certifying individual quantum devices with minimal assumptions is crucial for the development of quantum technologies. Here, we investigate how to leverage single-system contextuality to realize self-testing. We develop a robust self-testing protocol based on the simplest contextuality witness for the simplest contextual quantum system, the Klyachko-Can-Binicio{\u g}lu-Shumovsky (KCBS) inequality for the qutrit. We establish a lower bound on the fidelity of the state and the measurements (to an ideal configuration) as a function of the value of the witness under a pragmatic assumption on the measurements we call the KCBS orthogonality condition. We apply the method in an experiment with randomly chosen measurements on a single trapped 40Ca+ and near-perfect detection efficiency. The observed statistics allow us to self-test the system and provide the first experimental demonstration of quantum self-testing of a single system. Further, we quantify and report that deviations from our assumptions are minimal, an aspect previously overlooked by contextuality experiments.

}, keywords = {Atomic Physics (physics.atom-ph), FOS: Physical sciences, Quantum Physics (quant-ph)}, doi = {https://doi.org/10.48550/arXiv.2203.09003}, url = {https://arxiv.org/abs/2203.09003}, author = {Hu, Xiao-Min and Xie, Yi and Arora, Atul Singh and Ai, Ming-Zhong and Bharti, Kishor and Zhang, Jie and Wu, Wei and Chen, Ping-Xing and Cui, Jin-Ming and Liu, Bi-Heng and Huang, Yun-Feng and Li, Chuan-Feng and Guo, Guang-Can and Roland, J{\'e}r{\'e}mie and Cabello, Ad{\'a}n and Kwek, Leong-Chuan} }