4 added 542 characters in body
source | link

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 (case-a notation modified)

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 $y\not\in H$$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\gt \epsilon$$\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.

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 (case-a notation modified)

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 $y\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\gt \epsilon$, and Arthur will measure $|1\rangle$ sometimes after Hadamarding $|0\rangle|H'\rangle+|1\rangle |H'y\rangle$.

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.

3 edit (a0) and (a1)
source | link

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 (case-a notation modified)

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

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

(a1) Merlin sends $|H'\rangle$ with $H'$ being a non-sense encoding, and Arthur tests whether $y\not\in H'$$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 $y\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\gt \epsilon$, and Arthur will measure $|1\rangle$ sometimes after Hadamarding $|0\rangle|H'\rangle+|1\rangle |H'y\rangle$.

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 $y\not\in H'$

(a1) Merlin sends $|H'\rangle$ with $H'$ being a non-sense encoding, and Arthur tests whether $y\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 $y\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\gt \epsilon$, and Arthur will measure $|1\rangle$ sometimes after Hadamarding $|0\rangle|H'\rangle+|1\rangle |H'y\rangle$.

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 (case-a notation modified)

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 $y\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\gt \epsilon$, and Arthur will measure $|1\rangle$ sometimes after Hadamarding $|0\rangle|H'\rangle+|1\rangle |H'y\rangle$.

2 added 1263 characters in body
source | link

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 $y\not\in H'$

(a1) Merlin sends $|H'\rangle$ with $H'$ being a non-sense encoding, and Arthur tests whether $y\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 $y\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\gt \epsilon$, and Arthur will measure $|1\rangle$ sometimes after Hadamarding $|0\rangle|H'\rangle+|1\rangle |H'y\rangle$.

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

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 $y\not\in H'$

(a1) Merlin sends $|H'\rangle$ with $H'$ being a non-sense encoding, and Arthur tests whether $y\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 $y\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\gt \epsilon$, and Arthur will measure $|1\rangle$ sometimes after Hadamarding $|0\rangle|H'\rangle+|1\rangle |H'y\rangle$.

1
source | link