Take the 2-minute tour ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free, no registration required.

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!

share|improve this question
1  
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. –  Luboš Motl Jun 8 '12 at 7:13
    
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/… –  Luboš Motl Jun 8 '12 at 7:14
1  
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. –  Dan Stahlke Jun 8 '12 at 17:17
    
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. –  Juan Miguel Arrazola Jun 11 '12 at 15:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.