QMA_plus talk - HackMD

<style> .slides { font-size: 90%; } .reveal h1 .mathjax, .reveal h2 .mathjax, .reveal h3 .mathjax, .reveal h4 .mathjax, .reveal h5 .mathjax, .reveal h6 .mathjax { text-transform: none; } </style> ## $\text{QMA}$ and the power of "positivity" Kunal Marwaha University of Chicago <br/> joint with Roozbeh Bassirian, Bill Fefferman [(arXiv)](https://arxiv.org/abs/2306.13247) see also Jeronimo and Wu [(STOC '23)](https://dl.acm.org/doi/abs/10.1145/3564246.3585248) --- ## Outline 1. An introduction to $\text{QMA}^+$ 2. Proof outline --- ## Outline 1. **An introduction to $\text{QMA}^+$** 2. <span style="color: gray">Proof outline</span> ---- ## Context: $\text{QMA}$ and $\text{QMA}(2)$ <br/> 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}$ <span style="color: gray">Set of decision problems that have a BQP verifier $M$, and: </span> * <span style="color: gray">If YES (completeness): $\exists$ $\text{poly}(n)$-qubit </span>$|\psi_1\rangle \otimes |\psi_2\rangle$ <span style="color: gray">witness that makes $M$ accept w.p. $\ge c(n)$</span>. * <span style="color: gray">If NO (soundness): All $\text{poly}(n)$-qubit </span> $|\psi_1\rangle \otimes |\psi_2\rangle$ <span style="color: gray">witnesses make $M$ accept w.p. $\le s(n)$</span>. ---- ## 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]](https://arxiv.org/abs/1001.0017) <p></p> <br/> **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]](https://dl.acm.org/doi/abs/10.1145/3564246.3585248): $\text{QMA}^+_{c,s}$ <span style="color: gray">Set of decision problems that have a BQP verifier $M$, and: </span> * <span style="color: gray">If YES (completeness): $\exists$ $\text{poly}(n)$-qubit $|\psi\rangle$ witness</span> **with non-negative amplitudes** <span style="color: gray">that makes $M$ accept w.p. $\ge c(n)$</span>. * <span style="color: gray">If NO (soundness): All $\text{poly}(n)$-qubit $|\psi\rangle$ witnesses</span> **with non-negative amplitudes** <span style="color: gray">make $M$ accept w.p. $\le s(n)$</span>. ---- ## [[JW23]](https://dl.acm.org/doi/abs/10.1145/3564246.3585248): $\text{QMA}^+(2)_{c,s}$ <span style="color: gray">Set of decision problems that have a BQP verifier $M$, and: </span> * <span style="color: gray">If YES (completeness): $\exists$ $\text{poly}(n)$-qubit witness</span> $|\psi_1\rangle \otimes |\psi_2\rangle$ **with non-negative amplitudes** <span style="color: gray">that makes $M$ accept w.p. $\ge c(n)$</span>. * <span style="color: gray">If NO (soundness): All $\text{poly}(n)$-qubit witnesses</span> $|\psi_1\rangle \otimes |\psi_2\rangle$ **with non-negative amplitudes** <span style="color: gray">make $M$ accept w.p. $\le s(n)$</span>. ---- ## Does $^+$ add or remove power? What if we instead required non-negative amplitudes only in *completeness*? [[GKS14]](https://arxiv.org/abs/1410.2882) show that this is **equal** to $\text{QMA}$ (or $\text{QMA}(2)$). <br/> *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.  <img src="https://hackmd.io/_uploads/B1xbOUhYh.png" alt="parallel repetition fails" width="600" style="margin-bottom: -30px; margin-top: 0px"> ---- ## "facts" about $\text{QMA}^+$, $\text{QMA}^+(2)$ **Upper bounds** (better than $\text{NEXP}$): Using a semidefinite program **fails**. <br/> *Reason*:  Copositive programming [is hard!](https://ti.inf.ethz.ch/ew/Lehre/ApproxSDP09/notes/copositive.pdf) 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. <br/> $\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]](https://dl.acm.org/doi/abs/10.1145/3564246.3585248): On $\text{QMA}^+(2)$ $\exists$ *other* constants $1 > c > s > 0$, s.t. $\text{QMA}^+(2)_{c,s} = \text{NEXP}$. <br/> 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}$! <img src="https://hackmd.io/_uploads/ryUAU0quh.png" alt="arxiv figure 2" style="margin-bottom: -30px; margin-top: 0px"> ($\frac{c}{s}$ interpolates from $\text{QMA}$ to $\text{NEXP}$)  **NO** gap amplification of $\text{QMA}^+$!  ---- ## Interpreting these results <img src="https://hackmd.io/_uploads/r19m8Cqd3.png" alt="arxiv figure 1" width="600"> "*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. <span style="color: gray">An introduction to $\text{QMA}^+$</span> 2. **Proof outline** --- ## Outline 1. <span style="color: gray">An introduction to $\text{QMA}^+$</span> 2. <span style="color: gray">Proof outline:</span> * **$\text{NP} \subseteq \text{QMA}^+$ with $O(\log n)$-qubit proof** * <span style="color: gray">Scaling up to $\text{NEXP} \subseteq \text{QMA}^+$</span> ---- ## 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).  <br/> *Plan*: Solve this in $\text{QMA}^+$ with $O(\log n)$-sized proof.  ---- ## Amplitude and interference <img src="https://hackmd.io/_uploads/BkD0TT5_h.png" alt="interference image" width="600"> <span style="font-size: 6px; float: right"> edited from <a href="https://upload.wikimedia.org/wikipedia/commons/8/8a/Interference_of_two_waves.png">Wikipedia</a> </span> 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. <br/> **Big idea of** [[JW23]](https://dl.acm.org/doi/abs/10.1145/3564246.3585248): $\langle \psi |+\rangle \propto \||\psi\rangle\|_1$.  ($\Pi_+ := |+\rangle \langle +|$ accepts $|\psi\rangle$ according to its $\ell_1$ norm)  <br/> This is the **only use** of the ($^+$) assumption in both papers.  ---- ## [[JW23]](https://dl.acm.org/doi/abs/10.1145/3564246.3585248)'s use of ($^+$) 1. Notice that $\text{QMA}^+(2) = \text{QMA}^+(k)$ by [[HM10]](https://arxiv.org/abs/1001.0017) (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 ($^+$) <img src="https://hackmd.io/_uploads/ryXkBKNF2.png" alt="success rate of tests" style="margin-top: -20px; margin-bottom: -30px" width="500"> <span style="font-size: 6px; float: right"> concept: Bryan O'Gorman </span> * Tests are orthogonal, so sum of success rates $\le 1$. * Non-negative amplitude states live in green <span style="font-size:0.5em">🟩</span> region. * *Rigid* states at the circled <span style="font-size:0.5em">⚪</span> 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))$*. <br/> 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)$  <img src="https://hackmd.io/_uploads/rJUajGWFn.png" alt="Hadamard test image" width="600">  <span style="font-size: 6px; float: right"> source: <a href="https://upload.wikimedia.org/wikipedia/commons/f/f2/Hadamard_test_measure_real.png">Victory Omole</a> </span> ---- ## The "consistency" unitaries We build the graph $G$ using a step from [[Dinur07]](https://dl.acm.org/doi/abs/10.1145/1236457.1236459): 1. Turn each variable $i \in [n]$ into a *cluster* of vertices. (One vertex <span style="font-size:0.5em">🟠</span> per constraint <span style="font-size:0.5em">◻️</span> involving $i$.)  2. Add a $d$-regular *expander* graph <span style="font-size:0.5em">⚝</span> within each cluster.  Illustration for one variable <span style="font-size:0.5em">⚫</span> and $d = 2$:  ![dinur preprocessing graphic](https://hackmd.io/_uploads/rkCw_97F2.png) $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!)  <br/> 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\}$. <img src="https://hackmd.io/_uploads/ryBVNU-tn.png" alt="Hadamard test image" width="400">  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. <span style="color: gray">An introduction to $\text{QMA}^+$</span> 2. <span style="color: gray">Proof outline:</span> * <span style="color: gray">$\text{NP} \subseteq \text{QMA}^+$ with $O(\log n)$-qubit proof</span> * **Scaling up to $\text{NEXP} \subseteq \text{QMA}^+$** ---- ## A $\text{NEXP}$-hard problem **Input**: *Succinct* <span style="color: gray">CSP instance</span> ($N := 2^n$ variables, <span style="color: gray">bounded alphabet $\Sigma$, $q$-uniform constraints $\{\mathcal{C}_1, \dots, \mathcal{C}_R\}$)</span>  <span style="color: gray">**Output**: Is instance fully satisfiable (for some</span> $x \in \Sigma^{2^n}$<span style="color: gray">)?</span>  PCP Theorem: $\text{NEXP}$-hard <span style="color: gray">for $q = O(1)$, completeness $c=1$ and soundness $s = \frac{1}{2}$ (i.e. *constant* gap).</span>  <br/> *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]](https://dl.acm.org/doi/abs/10.1145/3564246.3585248)) * <span style="color: gray">expanders are exponentially large</span> *Doubly explicit* expander constructions, to build the expanders and decompose them in $\text{polylog}(N)$ time.  * <span style="color: gray">could be exponentially many expanders</span> Use a *$O(1)$-strongly uniform* PCP.  * <span style="color: gray">adjacency lists could be exponentially large</span> Use a *$\text{polylog}(N)$-doubly explicit* PCP.  Everything else works after making these adjustments! :sunglasses:  --- ## 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$. <img src="https://hackmd.io/_uploads/ryUAU0quh.png" alt="arxiv figure 2" style="margin-bottom: -30px">  ($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 <br/> Kunal Marwaha [https://kunalmarwaha.com/about](https://kunalmarwaha.com/about) kmarw@uchicago.edu <p style="font-size: 10px; width: 60%; margin: auto"> 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. </p>