Quantum State Sanitizing

Question

I was reading these lecture notes from Prof. Aaronson about Waltrous's MA protocol for the group non-membership problem. At the end of the description, there's an approach to distinguish if Merlin cheated or not, to confirm that Marline sent a superposition $|H\rangle$ over the subgroup $H$. So Arthur takes whatever Merlin sends $|H'\rangle$, randomly selects $y\in H$, and computes the superposition $\sum_{h'\in H'}|h'y\rangle$ over the set $H'y$.

But the way group multiplication done is by an oracle promising that its inputs are some superpositions over group elements. What if Merlin cheated by sending a superposition of garbage encodings? In this case, we must try to get rid of the components falling into garbage encoding.

Then I realized it is not just that; if we ever want to compute a superposition over some artificial objects, it is almost inevitable to get your superposition with some components being non-sense encoding. There must (or better be) some way to sanitize the input, right?

In classical computing we usually can easily solve this. In quantum computing, it seems to be not a "big-deal" as well, but I just can't figure this out.

To make it more specific, I might define some subset $E\subseteq \{0,1\}^n$ to be the set of encodings that make sense, and $X:=\{0,1\}^n-E$ to be the set of garbage encodings. Now given a n-qubit input quantum-mechanically $|\psi\rangle\in\mathbb{C}^{\{0,1\}^n}$, $|\psi\rangle$ can always be represented as $|\psi\rangle=|e\rangle+|x\rangle$ where $|e\rangle\in\mathbb{C}^E, |x\rangle\in\mathbb{C}^X$. Is it even possible to extract $|e\rangle$ out of $|\psi\rangle$?

I tried to deterministically do the check (in each branch separately), but then we will get something like,

$$ \sum_{e\in E}c_e|e\rangle|garbage\rangle. $$

This is still not the same as

$$ |e\rangle=\sum_{e\in E}c_e|e\rangle. $$

Answer 1

Then I realized it is not just that; if we ever want to compute a superposition over some artificial objects, it is almost inevitable to get your superposition with some components being non-sense encoding. There must (or better be) some way to sanitize the input, right?

But this is the point! We asume Merlin is powerful enough to prepare a uniform superposition of $|H\rangle$ without having non-sense encodings. If Arthur himself could do it easily, then Group Non-Membership would be in $\mathrm{BQP}$ and not in $\mathrm{QMA}$.

To make it more specific, I might define some subset $E\subseteq \{0,1\}^n$ to be the set of encodings that make sense, and $X:=\{0,1\}^n-E$ to be the set of garbage encodings. Now given a n-qubit input quantum-mechanically $|\psi\rangle\in\mathbb{C}^{\{0,1\}^n}$, $|\psi\rangle$ can always be represented as $|\psi\rangle=|e\rangle+|x\rangle$ where $|e\rangle\in\mathbb{C}^E, |x\rangle\in\mathbb{C}^X$. Is it even possible to extract $|e\rangle$ out of $|\psi\rangle$?

It's certainly not likely to be easily or efficiently done, unless $\mathrm{NP}\subseteq\mathrm{BQP}$. For example, $E$ could be the solutions to some $n$-bit $\mathsf{3SAT}$ instance while $X$ could be those that don't satisfy the $n$-bit $\mathsf{3SAT}$. $|\psi\rangle=|e\rangle+|x\rangle$ could be the uniform superposition over all $n$-bit strings. If Arthur had an easy way to "sanitize" and extract $|e\rangle$ from $|\psi\rangle$ then Arthur could solve $\mathsf{3SAT}$.

I tried to deterministically do the check (in each branch separately)

The protocol assumes that Merlin gives Arthur a uniform superposition of $|H\rangle$. Arthur can perform either the first test to determine if $y\in H'$, or the second test to determine if $H=H'$.

---

EDIT

Further to the comments, let's look at 4 different tests/situations.

(a0) Merlin sends $|H'\rangle$ with $H'=H$ and Arthur tests whether $x\not\in H'$

(a1) Merlin sends $|H'\rangle$ with $H'$ being a non-sense encoding, and Arthur tests whether $x\not\in H'$

(b0) Merlin sends $|H'\rangle$ with $H'=H$ and Arthur tests whether $H'=H$

(b1) Merlin sends $|H'\rangle$ with $H'$ being a non-sense encoding, and Arthur tests whether $H'=H$

It seems like you are worried about the (a1) case - indeed, Arthur might be fooled into thinking that $x\not\in H$ only because Merlin maliciously sent a non-sense encoding.

However as long as Arthur can do the (b) tests sometimes, he has a chance of catching Merlin in a cheat. The (b) tests rely on the group-theoretic fact that Arthur, as weak as he is, can still create and Hadamard $|0\rangle|H'\rangle+|1\rangle |H'y\rangle$, for a $y\in H$ of Arthur's choice.

These (b) tests suffice to make sure that Merlin did not send a non-sense encoding, because if Merlin sent a non-sense encoding, then $\langle H'|H\rangle\le \epsilon$, and Arthur will measure $|1\rangle$ sometimes after Hadamarding $|0\rangle|H'\rangle+|1\rangle |H'y\rangle$.

When a system is in the state $\frac{1}{\sqrt{2}}(|0\rangle|H'\rangle+|1\rangle|H'y\rangle)$ and $|H'\rangle=|H'y\rangle$, then Hadamarding and measuring the left qubit will always return $0$, because the right qubits representing $H'$ and $H'y$ "destructively interfere."

But there's the group-theoretic fact that if $y\not\in H'$, then $|H'\rangle\ne|H'y\rangle$. Then Hadamarding $\frac{1}{\sqrt{2}}(|0\rangle|H'\rangle+|1\rangle|H'y\rangle)$ will sometimes return $1$ in the left qubit, because the right qubits representing $H'$ and $H'y$ do not interfere.