6
$\begingroup$

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!

Improve this question
$\endgroup$
5
  • 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$
    – Luboš Motl
    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$
    – Luboš Motl
    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$
    – Dan Stahlke
    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$
    – Juan Miguel Arrazola
    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$
    – Frédéric Grosshans
    Oct 30, 2015 at 19:07

0

Reset to default

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.