4 added 542 characters in body edited Jul 7 at 13:24 Mark S 2,59111 gold badge44 silver badges2828 bronze badges 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) edit approved Jul 7 at 13:01 Taylor Huang 6555 bronze badges 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 edited Jul 5 at 12:32 Mark S 2,59111 gold badge44 silver badges2828 bronze badges 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 answered Jul 4 at 18:17 Mark S 2,59111 gold badge44 silver badges2828 bronze badges