Related papers: QMA vs. QCMA and Pseudorandomness

QMA vs. QCMA and Pseudorandomness

URL: http://arxiv.org/abs/2411.14416v3
Date: Tue, 26 Nov 2024 18:55:32 GMT
Title: QMA vs. QCMA and Pseudorandomness
Authors: Jiahui Liu, Saachi Mutreja, Henry Yuen,
Abstract summary: We show that such an oracle exists if a certain quantum pseudorandomness conjecture holds. Our result can be viewed as establishing a "win-win" scenario.
Score: 5.483786291093505
License:
Abstract: We study a longstanding question of Aaronson and Kuperberg on whether there exists a classical oracle separating $\mathsf{QMA}$ from $\mathsf{QCMA}$. Settling this question in either direction would yield insight into the power of quantum proofs over classical proofs. We show that such an oracle exists if a certain quantum pseudorandomness conjecture holds. Roughly speaking, the conjecture posits that quantum algorithms cannot, by making few queries, distinguish between the uniform distribution over permutations versus permutations drawn from so-called "dense" distributions. Our result can be viewed as establishing a "win-win" scenario: either there is a classical oracle separation of $\mathsf{QMA}$ from $\mathsf{QCMA}$, or there is quantum advantage in distinguishing pseudorandom distributions on permutations.

Related papers

Quantum-Computable One-Way Functions without One-Way Functions [0.6349503549199401]
We construct a classical oracle relative to which $mathsfP = mathsfNP$ but quantum-computable quantum-secure trapdoor one-way functions exist. Our result implies multi-copy pseudorandom states and pseudorandom unitaries, but also classical-communication public-key encryption, signatures, and oblivious transfer schemes.
arXiv Detail & Related papers (2024-11-04T19:40:01Z)
Oracle Separations for the Quantum-Classical Polynomial Hierarchy [0.0]
We study the quantum-classical hierarchy, QCPH, which is the class of languages solvable by a constant number of alternating classical quantifiers. We give a new switching lemma for quantum algorithms which may be of independent interest.
arXiv Detail & Related papers (2024-10-24T18:12:03Z)
The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
arXiv Detail & Related papers (2024-02-29T01:35:46Z)
Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
arXiv Detail & Related papers (2023-11-07T04:59:02Z)
Connecting classical finite exchangeability to quantum theory [69.62715388742298]
Exchangeability is a fundamental concept in probability theory and statistics. We show how a de Finetti-like representation theorem for finitely exchangeable sequences requires a mathematical representation which is formally equivalent to quantum theory.
arXiv Detail & Related papers (2023-06-06T17:15:19Z)
Quantum Cryptography in Algorithmica [0.7524721345903025]
We show that in a black-box setting, quantum cryptography based on pseudorandom states is possible even if one-way functions do not exist. We also introduce a conjecture that would generalize our results to multi-copy secure pseudorandom states.
arXiv Detail & Related papers (2022-12-01T21:33:38Z)
A distribution testing oracle separation between QMA and QCMA [0.6144680854063939]
It is a long-standing open question in quantum complexity theory whether the definition of $textitnon-deterministic$ quantum computation requires quantum witnesses. We make progress on this question by constructing a randomized classical oracle separating the respective computational complexity classes.
arXiv Detail & Related papers (2022-10-27T12:43:56Z)
Quantum Depth in the Random Oracle Model [57.663890114335736]
We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
arXiv Detail & Related papers (2022-10-12T17:54:02Z)
Why we should interpret density matrices as moment matrices: the case of (in)distinguishable particles and the emergence of classical reality [69.62715388742298]
We introduce a formulation of quantum theory (QT) as a general probabilistic theory but expressed via quasi-expectation operators (QEOs) We will show that QT for both distinguishable and indistinguishable particles can be formulated in this way. We will show that finitely exchangeable probabilities for a classical dice are as weird as QT.
arXiv Detail & Related papers (2022-03-08T14:47:39Z)
Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
arXiv Detail & Related papers (2022-01-06T03:10:53Z)
Quantum Pseudorandomness and Classical Complexity [0.08158530638728499]
We show that cryptographic pseudorandom quantum states and pseudorandom unitary transformations exist. We discuss implications of these results for cryptography, complexity theory, and quantum tomography.
arXiv Detail & Related papers (2021-03-16T20:54:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.