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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Joe Fitzsimons Mar 19 '15 at 15:03
  • $\begingroup$ @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$ $\endgroup$ – Subhayan Mar 20 '15 at 7:22
  • $\begingroup$ 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. $\endgroup$ – Joe Fitzsimons Mar 20 '15 at 12:06
  • $\begingroup$ @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? $\endgroup$ – Subhayan Mar 20 '15 at 20:17
  • $\begingroup$ To think about it, I think another way of phrasing my original question is, "how to 'sign' a quantum state?". $\endgroup$ – Subhayan Mar 20 '15 at 21:21

Your Answer

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

Browse other questions tagged or ask your own question.