<p>Consider the following function $$f_s: k \rightarrow \lvert \psi_k \rangle$$ 
where $s,k$ are bit strings, and $\lvert \psi_k \rangle$ is a $n$-qubit state.
Assume the function is a one-to-one mapping.</p>

<p>Given only $\big(f, k, \lvert \psi_k \rangle \big) $ is there a way to produce a (zero knowledge) proof $P$ that only verifies that $\lvert \psi_k \rangle$ has been generated from $k$, but not learn any more information about $\lvert \psi_k \rangle$ or $s$?</p>

<hr>

<p>Digression (to the classical world where factoring is difficult)</p>

<p>Consider a classical function $f_s: k \rightarrow p$
so a function $f$ does the following $f_p(q) = p*q*r*s$, where  $p,q,r,s$ are all large primes,
now given only $(f,q, n=p*q*r*s)$, one can easily check $q|n$, but cannot learn $p$ since that requires factoring $p*r*s$</p>

<p>I am looking for something similar for the quantum regime.</p>

CC BY-SA 3.0
2015-03-19T15:03:59.197Z
Surely this depends on the nature of $f_s$. For example, if the the vectors given by $f_s(k)$ all lie within a subspace orthogonal to the other vectors, you can simply measure that you are indeed in that subspace. On the other hand, if there exists some vector generated by another value k' which lies in a subspace spanned by some collection of $|\psi_k\rangle$ for various $s$, it is hard to see how you could distinguish this from the others while respecting linearity.
Joe Fitzsimons
CC BY-SA 3.0
2015-03-20T07:22:08.880Z
@JoeFitzsimons thanks, what about unitary operations? Is it possible to come up with a circuit, that when given $\lvert \psi_k \rangle$ and $\lvert 0^{\otimes m} \rangle$ as input, 'does something' on the ancilla and on measuring only the ancilla, we learn the relation of $k, \lvert \psi_k \rangle$
Subhayan
CC BY-SA 3.0
2015-03-20T12:06:41.307Z
If your only input is one copy of $|\psi_k\rangle$ and a description of $f$ are all you are given, it is impossible if some $f_s'(k')$ lies in the space spanned by $\{f_s(k)\}_{k}$ for some $s\neq s'$, simply due to linearity.
Joe Fitzsimons
CC BY-SA 3.0
2015-03-20T20:17:31.287Z
@JoeFitzsimons Thanks, I see that too. What if we allow the another parameter (something like a 'public key'), can we exploit the stabilizer formalism in anyway?
Subhayan
CC BY-SA 3.0
2015-03-20T21:21:19.190Z
To think about it, I think another way of phrasing my original question is, "how to 'sign' a quantum state?".
Subhayan
CC BY-SA 3.0
2015-03-22T12:13:33.560Z
There is a theorem that signing states is impossible.
Joe Fitzsimons
<quantum-computing><quantum-information>
Proofs to verify quantum states without revealing their description
Subhayan
# Proofs to verify quantum states without revealing their description

(Asked by: username_0 on 2015-03-18)

Consider the following function $$f\_s: k \rightarrow \lvert \psi\_k \rangle$$
where $s,k$ are bit strings, and $\lvert \psi\_k \rangle$ is a $n$-qubit state.
Assume the function is a one-to-one mapping.

Given only $\big(f, k, \lvert \psi\_k \rangle \big) $ is there a way to produce a (zero knowledge) proof $P$ that only verifies that $\lvert \psi\_k \rangle$ has been generated from $k$, but not learn any more information about $\lvert \psi\_k \rangle$ or $s$?

---

Digression (to the classical world where factoring is difficult)

Consider a classical function $f\_s: k \rightarrow p$
so a function $f$ does the following $f\_p(q) = p\*q\*r\*s$, where $p,q,r,s$ are all large primes,
now given only $(f,q, n=p\*q\*r\*s)$, one can easily check $q|n$, but cannot learn $p$ since that requires factoring $p\*r\*s$

I am looking for something similar for the quantum regime.

**Tags:** quantum-computing, quantum-information
> **Comments:**
> **username_1**: Surely this depends on the nature of $f_s$. For example, if the the vectors given by $f_s(k)$ all lie within a subspace orthogonal to the other vectors, you can simply measure that you are indeed in that subspace. On the other hand, if there exists some vector generated by another value k' which lies in a subspace spanned by some collection of $|\psi_k\rangle$ for various $s$, it is hard to see how you could distinguish this from the others while respecting linearity.  
> **username_0**: @JoeFitzsimons thanks, what about unitary operations? Is it possible to come up with a circuit, that when given $\lvert \psi_k \rangle$ and $\lvert 0^{\otimes m} \rangle$ as input, 'does something' on the ancilla and on measuring only the ancilla, we learn the relation of $k, \lvert \psi_k \rangle$  
> **username_1**: If your only input is one copy of $|\psi_k\rangle$ and a description of $f$ are all you are given, it is impossible if some $f_s'(k')$ lies in the space spanned by $\{f_s(k)\}_{k}$ for some $s\neq s'$, simply due to linearity.  
> **username_0**: @JoeFitzsimons Thanks, I see that too. What if we allow the another parameter (something like a 'public key'), can we exploit the stabilizer formalism in anyway?  
> **username_0**: To think about it, I think another way of phrasing my original question is, "how to 'sign' a quantum state?".  
> **username_1**: There is a theorem that signing states is impossible.  

---

## 0 answers

