4
$\begingroup$

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. $$

$\endgroup$
  • $\begingroup$ Hi Taylor! Welcome to QCSE! I think there's a couple of good questions in here but I'm not clear on a couple of things. I've tidied up the question for clarity. Please let me know if my revisions were not helpful; otherwise I might take a stab at answering what I think your question is. For example I think you are asking for Arthur to do a lot of work to "sanitize" his states - but the protocol is for Merlin to do all of he work (of "sanitization"). $\endgroup$ – Mark S Jul 4 at 17:07
  • $\begingroup$ Hi, thanks for your comment. I think I should expect Arthur to do some sanitizing because when Authur computing each $|h'y\rangle$, he is not sure if the $h'$ even make sense. (I guess? $\endgroup$ – Taylor Huang Jul 4 at 17:18
  • $\begingroup$ I think Arthur has two choices. He can either (a) test whether $x\in H$ by assuming $H=H'$, or (b) he can test whether $H=H'$ by knowingly generating his own $y\in H$. Arthur flips a coin to decide whether to do (a) or (b). Merlin must have provided a uniform superposition of $|H\rangle$ to pass both of Arthur's tests, otherwise Arthur can detect a fail. Arthur might have to do the test more than once, but as long as his choice of action between (a) and (b) is private from Merlin, Arthur should be convinced that Merlin is providing $|H\rangle$. $\endgroup$ – Mark S Jul 4 at 17:52
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Happy 4th! I think I partially get your point that Arthur don't need to santizing input. But he still need to check input format, right? And there might be a problem. When Arthur try to test $H=H'$. It can't be relying on the assumption that Merlin sends good encoding. Though Merlin is powerful, he might be malicious so that he sends non-sense encoding. $\endgroup$ – Taylor Huang Jul 5 at 1:32
  • $\begingroup$ Arthur doesn't assume Merlin has sent a good encoding. If Merlin is malicious and sends non-sense encodings, then $H\ne H'$. Arthur's test of Hadarmarding the first bit in $|0\rangle|H'\rangle+|1\rangle|H'y\rangle$ will work only if Merlin sent $|H'\rangle$ and $H'=H$ (or $\langle H'|H\rangle \le \epsilon$). $\endgroup$ – Mark S Jul 5 at 12:12
  • $\begingroup$ There's a bit of notation differ to the edit and lecture not. I took some slight modification. Please let me know if I get it wrong. $\endgroup$ – Taylor Huang Jul 7 at 7:58
  • $\begingroup$ Ok I kindof get it. For the nonsense encoding $|H'\rangle\in \mathbb{C}^{X}$ because $y$, when seen as an unitary operator on $\mathbb{C}^{E}\otimes \mathbb{C}^{X}$, is closed under both $\mathbb{C}^{E}$ and $\mathbb{C}^{X}$. Therefore in this case, $|H'y\rangle\in\mathbb{C}^{X}$ so $\langle H|H'y\rangle=0$. By the convexity argument we will need to show for the case where $H'$ contains only those encoding that make sense. $\endgroup$ – Taylor Huang Jul 7 at 8:29
  • 1
    $\begingroup$ If $x\in H$, the test will eventually yield 0 on the left qubit with probability 1. So we will only need to make sure that when $x\not\in H$, the rejecting probability is non-negligible, instead of making 1/3, 2/3 distintion. Is that correct? $\endgroup$ – Taylor Huang Jul 8 at 1:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.