Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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.… – Luboš Motl Jun 8 '12 at 7:14
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
@JuanMiguelArrazola : After 3 years and a PhD on the subject, you probably are the best person now to answer your own question ;-) – Frédéric Grosshans Oct 30 '15 at 19:07

Your Answer


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

Browse other questions tagged or ask your own question.