\(\text{QMA}\) and the power of "positivity"

Kunal Marwaha

University of Chicago

joint with Roozbeh Bassirian, Bill Fefferman (arXiv)

see also Jeronimo and Wu (STOC '23)

Outline

1. An introduction to \(\text{QMA}^+\)
2. Proof outline

Outline

1. An introduction to \(\text{QMA}^+\)
2. Proof outline

Context: \(\text{QMA}\) and \(\text{QMA}(2)\)

What is the power of unentangled proofs?

Review: \(\text{QMA}_{c,s}\)

Set of decision problems that have a BQP verifier \(M\), and:

• If YES (completeness): \(\exists\) \(\text{poly}(n)\)-qubit \(|\psi\rangle\) witness that makes \(M\) accept w.p. \(\ge c(n)\).
• If NO (soundness): All \(\text{poly}(n)\)-qubit \(|\psi\rangle\) witnesses make \(M\) accept w.p. \(\le s(n)\).

Review: \(\text{QMA}(2)_{c,s}\)

Set of decision problems that have a BQP verifier \(M\), and:

• If YES (completeness): \(\exists\) \(\text{poly}(n)\)-qubit \(|\psi_1\rangle \otimes |\psi_2\rangle\) witness that makes \(M\) accept w.p. \(\ge c(n)\).
• If NO (soundness): All \(\text{poly}(n)\)-qubit \(|\psi_1\rangle \otimes |\psi_2\rangle\) witnesses make \(M\) accept w.p. \(\le s(n)\).

Facts about \(\text{QMA}\), \(\text{QMA}(2)\)

Gap amplification (as long as \(c(n) - s(n) \ge \frac{1}{\text{poly}(n)}\)):

• \(\text{QMA}\): via parallel repetition
• \(\text{QMA}(2)\): using the product test [HM10]

Upper bounds (better than \(\text{NEXP}\)):

• \(\text{QMA} \subseteq \text{PSPACE}\) using semidefinite programming
  (in fact, \(\subseteq \text{PP}\) by Kitaev and Watrous)
• Only \(\text{QMA}(2) \subseteq \text{NEXP}\). Why can't we do better?

[JW23]: \(\text{QMA}^+_{c,s}\)

Set of decision problems that have a BQP verifier \(M\), and:

• If YES (completeness): \(\exists\) \(\text{poly}(n)\)-qubit \(|\psi\rangle\) witness with non-negative amplitudes that makes \(M\) accept w.p. \(\ge c(n)\).
• If NO (soundness): All \(\text{poly}(n)\)-qubit \(|\psi\rangle\) witnesses with non-negative amplitudes make \(M\) accept w.p. \(\le s(n)\).

[JW23]: \(\text{QMA}^+(2)_{c,s}\)

Set of decision problems that have a BQP verifier \(M\), and:

• If YES (completeness): \(\exists\) \(\text{poly}(n)\)-qubit witness \(|\psi_1\rangle \otimes |\psi_2\rangle\) with non-negative amplitudes that makes \(M\) accept w.p. \(\ge c(n)\).
• If NO (soundness): All \(\text{poly}(n)\)-qubit witnesses \(|\psi_1\rangle \otimes |\psi_2\rangle\) with non-negative amplitudes make \(M\) accept w.p. \(\le s(n)\).

Does \(^+\) add or remove power?

What if we instead required non-negative amplitudes
only in completeness?

[GKS14] show that this is equal to \(\text{QMA}\) (or \(\text{QMA}(2)\)).

Lesson: \(\text{QMA} \subseteq \text{QMA}^+\) and \(\text{QMA}(2) \subseteq \text{QMA}^+(2)\), since we also reduce Merlin's cheating in soundness.

"facts" about \(\text{QMA}^+\), \(\text{QMA}^+(2)\)

Gap amplification:
Parallel repetition fails.

Reason: Partial measurements can reintroduce complex phases into remaining state.

"facts" about \(\text{QMA}^+\), \(\text{QMA}^+(2)\)

Upper bounds (better than \(\text{NEXP}\)):
Using a semidefinite program fails.

Reason: Copositive programming is hard!

Optimizing \(\max_{x \ge 0} x^\dagger A x\) can compute independence numbers of graphs, etc.

How powerful is the (\(^+\))?

Every state \(|\psi \rangle\) has \(\frac{1}{4}\) overlap with some state with non-negative amplitudes.

\(\implies\) \(\exists\) constants \(1 > c' > s' > 0\) s.t.
\(\text{QMA}^+_{c',s'} = \text{QMA}\) and \(\text{QMA}^+(2)_{c',s'} = \text{QMA}(2)\).

[JW23]: On \(\text{QMA}^+(2)\)

\(\exists\) other constants \(1 > c > s > 0\), s.t.
\(\text{QMA}^+(2)_{c,s} = \text{NEXP}\).

New way to understand \(\text{QMA}(2)\):
\(\text{QMA}^+(2)\) gap amplification \(\implies\) \(\text{QMA}(2) = \text{NEXP}\)!

Our work: On \(\text{QMA}^+\)

\(\exists\) other constants \(1 > c > s > 0\), s.t.
\(\text{QMA}^+_{c,s} = \text{NEXP}\)!

(\(\frac{c}{s}\) interpolates from \(\text{QMA}\) to \(\text{NEXP}\))

NO gap amplification of \(\text{QMA}^+\)!

Interpreting these results

"Perhaps the power lies in the \(^+\), not the \((2)\)…"

Any technique to amplify the promise gap in \(\text{QMA}^+(2)\)
must fail for \(\text{QMA}^+\).

Outline

1. An introduction to \(\text{QMA}^+\)
2. Proof outline

Outline

1. An introduction to \(\text{QMA}^+\)
2. Proof outline:
   • \(\text{NP} \subseteq \text{QMA}^+\) with \(O(\log n)\)-qubit proof
   • Scaling up to \(\text{NEXP} \subseteq \text{QMA}^+\)

Choosing a \(\text{NP}\)-hard problem

Input: CSP instance (\(n\) variables, bounded alphabet \(\Sigma\),
\(q\)-uniform constraints \(\{\mathcal{C}_1, \dots, \mathcal{C}_R\}\))

Output: Is instance fully satisfiable (for some \(x \in \Sigma^n\))?

PCP Theorem: \(\text{NP}\)-hard for \(q = O(1)\), with completeness \(c=1\) and soundness \(s = \frac{1}{2}\) (i.e. constant gap).

Plan: Solve this in \(\text{QMA}^+\) with \(O(\log n)\)-sized proof.

Amplitude and interference

Intuition: non-negative amplitudes "take the interference" out of \(|\psi\rangle\) (they don't "cancel out"!)

The power of PLUS (\(^+\))

Goal: require Merlin to send a certain type of state.

Big idea of [JW23]: \(\langle \psi |+\rangle \propto \||\psi\rangle\|_1\).

(\(\Pi_+ := |+\rangle \langle +|\) accepts \(|\psi\rangle\) according to its \(\ell_1\) norm)

This is the only use of the (\(^+\)) assumption in both papers.

[JW23]'s use of (\(^+\))

1. Notice that \(\text{QMA}^+(2) = \text{QMA}^+(k)\) by [HM10]
   (so we can assume many copies of \(|\psi\rangle\)).
2. Project \(\Pi_+ |\psi\rangle\) on each copy; count the fraction that accept. (This estimates the \(\ell_1\) norm of \(|\psi\rangle\))

\(\longrightarrow\) check closeness to states of a target \(\ell_1\) norm.

Our use of (\(^+\))

Consider two registers:
question (\(\log n\) qubits) and answer (\(O(1)\) qubits)

We choose one of two tests:

1. \(\Pi_+ \otimes \Pi_+\): (dense as possible)
2. \(\mathbb{I} \otimes (\mathbb{I} - \Pi_+)\)

States with non-negative amplitudes can't perfectly pass Test 2. The best have one answer per question.

\(\longrightarrow\) check closeness to states of a rigid form:

\(\frac{1}{\sqrt{n}}\sum_{j=1}^{n} |j \rangle |f(j) \rangle\)

Our use of (\(^+\))

• Tests are orthogonal, so sum of success rates \(\le 1\).
• Non-negative amplitude states live in green 🟩 region.
• Rigid states at the circled ⚪ point.

How can we use this power?

questions \(\to\) constraints
answers \(\to\) assignments of associated variables

In completeness, \(\exists\) satisfying assignment \(f: [R] \to \Sigma^q\) and proof \(|\psi\rangle := \frac{1}{\sqrt{R}}\sum_{j=1}^{R} |j \rangle |f(j) \rangle\).

With some probability, we test for this rigid form.
Otherwise, we check the constraints \(\{\mathcal{C}_j\}\).

Testing the constraints

For rigid states, checking the constraints is easy:
measure in computational basis, and test \(\mathcal{C}_j(f(j))\).

But Merlin can cheat: sending different values for the same variable depending on the constraint.

So (with some probability), need to check for consistency.

Checking "consistency"

Goal: Construct unitaries \(\{U_1, \dots, U_d\}\) such that:

• Honest: \(|\psi\rangle = U_k |\psi \rangle\) for all \(k\)
• Cheating: \(|\psi\rangle\) "far" from \(U_k |\psi \rangle\) for some \(k\)

Then, the consistency protocol would:

1. Choose uniform \(k \in \{1, \dots, d\}\)
2. Run "Hadamard test" on \((|\psi\rangle, U_k |\psi\rangle)\)

The "consistency" unitaries

We build the graph \(G\) using a step from [Dinur07]:

1. Turn each variable \(i \in [n]\) into a cluster of vertices.
   (One vertex 🟠 per constraint ◻️ involving \(i\).)
2. Add a \(d\)-regular expander graph ⚝ within each cluster.

Illustration for one variable ⚫ and \(d = 2\):

\(G\) is the union of all expander graphs (\(R \cdot q\) vertices).

The "consistency" unitaries

Recall that a rigid state is of the form \(|\psi\rangle := \frac{1}{\sqrt{R}}\sum_{j=1}^{R} |j \rangle |f(j) \rangle\).

It is convenient to separate the variable assignments: \(|\phi\rangle := \frac{1}{\sqrt{R\cdot q}}\sum_{j=1}^{R} \sum_{\iota=1}^q |j,\iota \rangle |f(j)[\iota] \rangle\).
(Then all vertices of \(G\) are in superposition!)

The map \(|\psi\rangle \mapsto |\phi\rangle\) is efficient; see paper for details.

The "consistency" unitaries

We can always decompose a \(d\)-regular graph into \(d\) permutations \(\{\pi_1, \dots, \pi_d\}\).

For \(k \in [d]\), let \(U_k: |j, \iota\rangle |value\rangle \mapsto |\pi_k(j,\iota) \rangle |value\rangle\) for each constraint \(j \in [R]\) and variable index \(\iota \in [q]\).

Honest assignment \(\implies\) \(|\phi\rangle = U_k |\phi \rangle\) for all \(k\)!

Outline

1. An introduction to \(\text{QMA}^+\)
2. Proof outline:
   • \(\text{NP} \subseteq \text{QMA}^+\) with \(O(\log n)\)-qubit proof
   • Scaling up to \(\text{NEXP} \subseteq \text{QMA}^+\)

A \(\text{NEXP}\)-hard problem

Input: Succinct CSP instance (\(N := 2^n\) variables, bounded alphabet \(\Sigma\), \(q\)-uniform constraints \(\{\mathcal{C}_1, \dots, \mathcal{C}_R\}\))

Output: Is instance fully satisfiable (for some \(x \in \Sigma^{2^n}\))?

PCP Theorem: \(\text{NEXP}\)-hard for \(q = O(1)\), completeness \(c=1\) and soundness \(s = \frac{1}{2}\) (i.e. constant gap).

Plan: Solve this in \(\text{QMA}^+\) with \(O(\text{poly}(n))\)-sized proof.

The \(\text{NP}\) protocol ALMOST works

Arthur's protocol needs to be efficient.

Only issue: how to do "consistency" test?

• expanders are exponentially large
• could be exponentially many expanders
• adjacency lists could be exponentially large

Solutions ([JW23])

• expanders are exponentially large
  Doubly explicit expander constructions, to build the expanders and decompose them in \(\text{polylog}(N)\) time.

• could be exponentially many expanders
  Use a \(O(1)\)-strongly uniform PCP.

• adjacency lists could be exponentially large
  Use a \(\text{polylog}(N)\)-doubly explicit PCP.

Everything else works after making these adjustments!

Conclusions

Promise-symmetric classes can be very powerful.

But the promise gap really matters: \(\text{QMA}^+_{c,s}\) interpolates from \(\text{QMA}\) to \(\text{NEXP}\) for constant \(c,s\).

(\(x\)-axis: \(\frac{c}{s}\))

Is there a phase transition in constants?

Conclusions

Suppose you try to prove \(\text{QMA}(2) = \text{NEXP}\) by showing \(\text{QMA}^+(2)\) promise gap amplification.

Then the amplification technique crucially involves unentanglement, since it will fail for \(\text{QMA}^+\).

These techniques may be much more difficult to find.

What does \(\text{QMA}^+(2)\) have that \(\text{QMA}^+\) doesn't?

Thank you

Kunal Marwaha

https://kunalmarwaha.com/about
kmarw@uchicago.edu

This material is based upon work supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-1746045. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.