Recently, I have been studying a quantum protocol for the "Hidden Matching" problem that makes use of states that can be expressed as $$|\psi\rangle=\frac{1}{\sqrt{n}}\sum_{i=1}^n (-1)^{x_i}|i\rangle$$ where $x_i\in \{0,1\}$ and $n$ is a power of 2. Note that instead of an $n$-level system we can consider these as states of $\log_2{n}$ qubits. I suspect these states to have appeared in other contexts as they are a straightforward and useful way to map an $n$ bit string into an exponentially smaller amount of qubits. Hence I am wondering: have the properties of these types of states been already extensively studied?

I am particularly interested in how the reduced density matrix of each qubit and the entanglement of the state depend on the bit values $x_i$.

Thank you!

  • 1
    $\begingroup$ You may exponentially reduce the number of qubits needed for a certain number of bits but due to its unnaturalness, this formula isn't a helpful "proof" that a qubit is "exponentially more" than a bit. The right map is still that 1 qubit is a generalization of 1 bit and if they can be matched, they should be matched one-by-one. In particular, the reduced density matrix for a qubit may be calculated but it's just a gibberish function of the $x_i$'s. And other common operations with many bits $x_i$ would translate to unnatural, nonlocal, undoable operations with the fewer qubits. $\endgroup$ Jun 8, 2012 at 7:13
  • $\begingroup$ It's also important to mention that bits $x_i$ could be measured - all of them - by a single measurement of a classical computer. On the other hand, you can't find out all the values $x_i$ (and not even "most of them") by doing a single measurement on your state $\psi$. A single measurement of $\psi$ can give you at most $\log_2 n$ bits of information. Still, there's some literature about the "hidden matching", see e.g. scholar.google.com/… $\endgroup$ Jun 8, 2012 at 7:14
  • 1
    $\begingroup$ These types of states are also used in a quantum pseudo-telepathy game (the graph coloring game), quant-ph/0509047. In this and in the example that Luboš Motl gives above, it is significant that two of these states are orthogonal if they differ in $n/2$ positions. $\endgroup$ Jun 8, 2012 at 17:17
  • 1
    $\begingroup$ Luboš, thanks for your comment. I never meant to say that a qubit is "exponentially more" than a bit and the use of the word "matching" in this context does not relate to a matching between bits and qubits. All I intened to say is that this presents a straightforward way to map an $n$ bit string into $\log_2 n$ qubits, and this made me suspect they appear in many scenarios, which truly seems to be the case. $\endgroup$ Jun 11, 2012 at 15:37
  • $\begingroup$ @JuanMiguelArrazola : After 3 years and a PhD on the subject, you probably are the best person now to answer your own question ;-) $\endgroup$ Oct 30, 2015 at 19:07


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.