A distribution testing oracle separation between QMA and QCMA

2025-04-30 0 0 1.09MB 45 页 10玖币

侵权投诉

A distribution testing oracle separation between QMA

and QCMA

Anand Natarajan1and Chinmay Nirkhe2

1Massachusetts Institute of Technology

2IBM Quantum Cambridge

It is a long-standing open question in quantum complexity theory whether

the deﬁnition of non-deterministic quantum computation requires quantum

witnesses (QMA)or if classical witnesses suﬃce (QCMA). We make progress

on this question by constructing a randomized classical oracle separating the

respective computational complexity classes. Previous separations [3,13] re-

quired a quantum unitary oracle. The separating problem is deciding whether a

distribution supported on regular un-directed graphs either consists of multiple

connected components (yes instances) or consists of one expanding connected

component (no instances) where the graph is given in an adjacency-list for-

mat by the oracle. Therefore, the oracle is a distribution over n-bit boolean

functions.

1 Introduction

There are two natural quantum analogs of the computational complexity class NP. The ﬁrst

is the class QMA in which a quantum polynomial-time decision algorithm is given access

to a poly(n)qubit quantum state as a witness for the statement. This class is captured by

the QMA-complete local Hamiltonian problem [18] in which the quantum witness can be

interpreted as the ground-state of the local Hamiltonian. The second is the class QCMA

in which the quantum polynomial-time decision algorithm is given access instead to a

poly(n)bit classical state. While it is easy to prove that QCMA ⊆QMA as the quantum

witness state can be immediately measured to yield a classical witness string, the question

of whether QCMA ?

=QMA, ﬁrst posed by Aharonov and Naveh [4], remains unanswered.

If QCMA =QMA, then every local Hamiltonian would have an eﬃcient classical witness

of its ground energy; morally, this can be thought of as an eﬃcient classical description of

its ground state. The relevance of local Hamiltonians to condensed matter physics makes

this question a central open question in quantum complexity theory [2].

Anand Natarajan: anandn@mit.edu, This work was partially completed while a participant in the Simons Institute

for the Theory of Computing program The Quantum Wave in Computing: Extended Reunion. Natarajan thanks

Elizabeth Crosson, Aram Harrow, Zhiyang He, Robin Kothari, Yupan Liu, and Mehdi Soleimanifar for helpful

discussions.

Chinmay Nirkhe: nirkhe@ibm.com, Some of the initial ideas of this work were done while aﬃliated with the

University of California, Berkeley. This work was partially completed while a participant in the Simons Institute

for the Theory of Computing program The Quantum Wave in Computing: Extended Reunion. Nirkhe thanks

Srinivasan Arunachalam, Andrew Childs, Yi-Kai Liu, William Kretschmer, Kunal Marwaha, Umesh Vazirani,

and Elizabeth Yang for helpful discussions.

Accepted in Quantum 2023-08-21, click title to verify. Published under CC-BY 4.0. 1

arXiv:2210.15380v5 [quant-ph] 11 Jun 2024

Because P⊆QCMA ⊆QMA ⊆PSPACE, any unconditional separation of the two com-

plexity classes would imply P̸=PSPACE and seems unlikely without remarkably ingenious

new tools. A more reasonable goal is an oracle separation between the two complexity

classes. The ﬁrst oracle separation, by Aaronson and Kuperberg [3], showed that there

exists a black-box unitary problem for which quantum witnesses suﬃce and yet no poly-

nomial sized classical witness and algorithm can solve the problem with even negligible

success probability. A second black-box separation was discovered a decade later by Fef-

ferman and Kimmel [13]. The Feﬀerman and Kimmel oracle is a completely positive trace

perseving (CPTP) map called an "in-place” permutation oracle. Both oracles [3,13] are

inherently quantum1. Whereas, the "gold-standard” of oracle separations — namely black-

box function separations (also known as classical oracle separations) — only require access

to a classical function that can be queried in superposition2.

1.1 Graph oracles

The major result of this work is to prove that there exists a distribution over black-box

function problems separating QMA and QCMA. Each black-box function corresponds to

the adjacency list of a Ndef

= 2nvertex constant-degree colored graphs3G= (V, E). Roughly

speaking, a graph is a YES instance if the second eigenvalue of its normalized adjacency

matrix is 1 (equivalently, if it has at least two connected components) and a graph is a NO

instance if it second eigenvalue is at most 1−αfor some ﬁxed constant α(equivalently, the

graph has one connected component and is expanding). We call this problem the expander

distinguishing problem.

Distribution oracles A distribution over functions (equivalently, a distribution over

graphs) is a YES instance if it is entirely supported on YES graphs and a distribution over

functions is a NO instance if it is entirely supported on NO graphs.

In this work, we construct, for every n, families of YES and NO distributions over

graphs such that following hold for the promise problem of distinguishing a graph sampled

from a YES distribution from a graph sampled from a NO distribution.

1. There is a QMA proof system that solves this problem, where the veriﬁer runs in

quantum polynomial time and has black-box query access to the sampled graph, and

the honest prover’s (quantum) witness depends only on the distribution, not on the

speciﬁc sample.

2. No QCMA proof system can solve this problem, provided the prover’s (classical)

witness is only allowed to depend on the distribution, and not on the sample.

Our work is not the ﬁrst to consider oracles that sample from distributions over

functions. The in-place oracle separation of [13] between QMA and QCMA used ora-

cles that sampled random permutations. For a somewhat diﬀerent problem, of separating

1It might be reasonable to wonder if the unitary oracles can be converted into classical oracles by

providing oracle access to the exponentially long classical descriptions of the respective matrices. This is

not known to be true because it is unclear how to use access to the classical description to solve the QMA

problem.

2One reason this model is natural is that if we were given a circuit of size Cto implement this classical

function, then we would automatically get a quantum circuit of size Cto implement the oracle, simply

by running the classical circuit coherently. This is not true for the "in-place" permutation oracle model,

assuming that one-way functions exist.

3A similar problem was previously conjectured to be an oracle separation for these complexity classes

by Lutomirski [22].

Accepted in Quantum 2023-08-21, click title to verify. Published under CC-BY 4.0. 2

Authors Separating black box object Proof techniques used

Aaronson & Kuperberg [3]n-qubit unitaries Adversary method

Feﬀerman & Kimmel [13]n-qubit CPTP maps Combinatorial argument,

Adversary method

This work Distributions over n-bit

boolean functions

Combinatorial argument,

Adversary method,

Polynomial method

Conjectured n-bit boolean function ?

Figure 1: List of known oracle separations

bounded-depth quantum-classical circuits, [8] introduced a related notion called a "stochas-

tic oracle"—the main diﬀerence between this and our model is that a stochastic oracle

resamples an instance every time it is queried.

Comparison with previous oracle separations between QMA and QCMA Figure

1summarizes our work in relation to previous oracle separations. In terms of results,

we take a further step towards the standard oracle model—all that remains is to remove

the randomness from our oracle. In terms of techniques, we combine the use of counting

arguments and the adversary method from previous works with a BQP lower bound for

a similar graph problem, due to [6]. This lower bound was shown using the polynomial

method. We view the judicious combination of these lower bound techniques—as simple

as it may seem—as one of the conceptual contributions of this paper.

Intuition for hardness The expander distinguishing problem is a natural candidate for

a separation between QMA and QCMA because it is an "oracular" version of the sparse

Hamiltonian problem, which is complete for QMA [10, Problem H-4]. To see this, we recall

some facts from spectral graph theory. The top eigenvalue of the normalized adjacency

matrix Afor regular graphs is always 1 and the uniform superposition over vertices is always

an associated eigenvector. If the graph is an expander (the NO case of our problem), the

second eigenvalue is bounded away from 1, but if the graph is disconnected (the YES case

of our problem), then the second eigenvalue is exactly 1. Thus, our oracle problem is

exactly the problem of estimating the minimum eigenvalue of I−A(a sparse matrix for

a constant-degree graph), on the subspace orthogonal to the uniform superposition state.

Viewing I−Aas a sparse Hamiltonian, we obtain the connection between our problem

and the sparse Hamiltonian problem.

One reason to show oracle separations between two classes is to provide a barrier

against attempts to collapse the classes in the "real" world. We interpret our results as

conﬁrming the intuition that any QCMA protocol for the sparse Hamiltonian must use

more than just black-box access to entries of the Hamiltonian: it must use some nontrivial

properties of the ground states of these Hamiltonians. In this sense, it emulates the original

quantum adversary lower bound of [9] which showed that any BQP-algorithm for solving

NP-complete problems must rely on some inherent structure of the NP-complete problem

as BQP-algorithms cannot solve unconstrained search eﬃciently.

Naturalness of the randomized oracle model Some care must be taken whenever

one proves a separation in a “nonstandard" oracle model—see for instance the “trivial"

example in [1] of a randomized oracle separating MA1from MA. We believe that our

randomized oracle model is natural for several reasons. Firstly, as mentioned above, ran-

domization was used in the quantum oracle of [13] for essentially the same reason: to

impose a restriction on the witnesses received from the prover. Secondly, it is consistent

Accepted in Quantum 2023-08-21, click title to verify. Published under CC-BY 4.0. 3

with our knowledge that our oracle separates QMA from QCMA even when the randomness

is removed (and indeed we conjecture this is the case, as described below.) Thirdly, the

randomization still gives the prover access to substantial information about the graph: in

particular, the prover knows the full connected component structure of the graph. As we

show, this information is enough for the prover to give a quantum witness state, that in

the YES case convinces the veriﬁer with certainty. Our result shows that even given full

knowledge of the component structure, the prover cannot construct a convincing classical

witness—we believe this sheds light on how a QMA witness can be more powerful than a

QCMA witness.

1.2 Overview of proof techniques

Quantum witnesses and containment in oracular QMA A quantum witness for any

YES instance graph is any eigenvector |ξ⟩of eigenvalue 1 that is orthogonal to the uniform

superposition over vertices. The veriﬁcation procedure is simple: project the witness into

the subspace orthogonal to the uniform superposition over vertices, and then perform one

step of a random walk along the graph, by querying the oracle for the adjacency matrix in

superposition. Verify that the state after the walk step equals |ξ⟩. This is equivalent to a

1-bit phase estimation of the eigenvalue. If a graph is a NO instance, then there does not

exist any vector orthogonal to the uniform superposition (the unique eigenvector of value

1) that would pass the previous test.

Whenever, the graph has a connected component of S⊊V, then an eigenvector orthog-

onal to the uniform superposition of eigenvalue 1 exists. When |S| ≪ N, this eigenvector

is very close to |S⟩, the uniform superposition over basis vectors x∈S. Notice that this

state only depends on the connected component Sand not the speciﬁc edges of the graph.

Furthermore, the state |S′⟩for any subset S′that approximates Sforms a witness that is

accepted with high probability.

Lower bound on classical witnesses The diﬃculty in this problem lies in proving a

lower bound on the ability for classical witnesses to distinguish YES and NO instances. To

prove a lower bound, we argue that any quantum algorithm with access to a polynomial

length classical witness must make an exponential number of (quantum) queries to the ad-

jacency list of the graph in order to distinguish YES and NO instances. This, in turn, lower

bounds the time complexity of any QCMA algorithm distinguishing YES and NO instances

but is actually slightly stronger since we don’t consider the computational complexity of

the algorithm between queries.

Proving lower bounds when classical witnesses are involved is diﬃcult because the

witness could be based on any property of the graph. For example, the classical witness

could describe cycles, triangles, etc. contained in the graph — while it isn’t obvious why

such a witness would be helpful, proving that any such witness is insuﬃcient is a signiﬁcant

challenge. One way to circumvent this diﬃculty is to ﬁrst show a lower bound assuming

some structure about the witness4, and then "remove the training wheels" by showing that

the assumption holds for any good classical witness.

4Assuming structure about a witness is a common technique in theoretical computer science and in

particular lower bounds for classical witnesses of quantum statements. For example, lower bounds against

natural proofs [20]. Another example is the NLTS statement [7] which is about lower bounds for classical

witnesses for the ground energy of a quantum Hamiltonian of a particular form: constant-depth quantum

circuits.

Accepted in Quantum 2023-08-21, click title to verify. Published under CC-BY 4.0. 4

Lower bound against "subset witnesses" One structure we can assume is that the

witness only depends on the set of vertices contained in the connected component S. This

is certainly the case for the quantum witness state in eq. (24). Our result shows that

any polynomial-length witness only depending on the vertices in Srequires an exponential

query complexity to distinguish YES and NO instance graphs.

The starting point for this statement is the exponential query lower bound in the

absence of a witness (i.e. for BQP) for the expander distinguishing problem proven by

Ambainis, Childs and Liu [6], using the polynomial method. In [6], the authors deﬁne two

distributions over constant-degree regular colored graphs: the ﬁrst is a distribution P1over

random graphs with overwhelming probability of having a second normalized eigenvalue

at most 1−ϵ0. The second is a distribution Pℓover random graphs with overwhelming

probability of having ℓconnected components. Since, almost all graphs in P1are NO

graphs and all graphs in Pℓare YES graphs, any algorithm distinguishing YES and NO

instances must be able to distinguish the two distributions. We ﬁrst show that a comparable

query lower bound still holds even when the algorithm is given a witness consisting of

polynomially many random points Ffrom any one connected component.

Next, we show that if there were a QCMA algorithm where the optimal witness depends

only on the set of vertices Sin one of the connected components, by a counting argument,

there must exist a combinatorial sunﬂower of subsets Sthat correspond to the same witness

string. A sunﬂower, in this context, is a set of subsets such that each subset contains a

core F⊂Vand every vertex of V\Foccurs in a small fraction of subsets. This implies

that there exists a BQP algorithm which distinguishes YES instances corresponding to the

sunﬂower from all NO instances. Next, we show using an adversary bound [5], a quantum

query algorithm cannot distinguish the distribution of YES instances corresponding to the

sunﬂower from the uniform distribution of YES instances such that the core Fis contained

in a connected component (the ideal sunﬂower).

This indistinguishability, along with the previous polynomial method based lower bound,

proves that QCMA algorithm — whose witness only depends on the vertices in the con-

nected component — for the expander distinguishing problem must make an exponential

number of queries to the graph.

Removing the restriction over witnesses Our proof, thus far, has required the re-

striction that the witness only depends on the vertices in the connected component. In

some sense, this argues that there is an oracle separation between QMA and QCMA if

the prover is restricted to being "near-sighted": it cannot see the intricacies of the edge-

structure of the graph, but can notice the separate connected components of the graph. If

the near-sighted prover was capable of sending quantum states as witnesses, then she can

still aid a veriﬁer in deciding the expander distinguishing problem, whereas if she could

only send classical witnesses, then she cannot aid a veriﬁer.

It now remains to remove the restriction that the witness can only depend on the

vertices in the connected component. We do this by introducing randomness into the

oracle, precisely designed to "blind" the prover to the local structure of the graph. In the

standard oracle setting, the veriﬁer and prover both get access to an oracle x∈ {0,1}N, and

the prover provides either a quantum witness, |ξ(x)⟩ ∈ (C2)⊗poly(n)or a classical witness,

ξ(x)∈ {0,1}poly(n). The veriﬁer then runs an eﬃcient quantum algorithm Vxwhich takes

as input |ξ(x)⟩(or ξ(x), respectively) and consists of quantum oracle gates applying the

unitary transform deﬁned as the linear extension of

|i⟩ 7→ (−1)xi|i⟩for i∈[N].(1)

Accepted in Quantum 2023-08-21, click title to verify. Published under CC-BY 4.0. 5

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

AdistributiontestingoracleseparationbetweenQMAandQCMAAnandNatarajan1andChinmayNirkhe21MassachusettsInstituteofTechnology2IBMQuantumCambridgeItisalong-standingopenquestioninquantumcomplexitytheorywhetherthedefinitionofnon-deterministicquantumcomputationrequiresquantumwitnesses(QMA)orifclassicalwitnes...

展开>> 收起<<

A distribution testing oracle separation between QMA and QCMA.pdf

共45页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

A distribution testing oracle separation between QMA and QCMA

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: