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!

  • 2
    $\begingroup$ Are you interested in multi-partite ent. or bipartite ent.? In the second case, where would the cut be? Also, if this is also you, you can ask the moderators to merge the two accounts. $\endgroup$ Jun 8, 2012 at 3:10
  • 4
    $\begingroup$ Such states appear fairly frequently in quantum information. For example, they occur in quantum fingerprinting (quant-ph/0102001). I'm sure there is a name for this particular class of states, but I can't remember what it is. $\endgroup$ Jun 8, 2012 at 10:16
  • $\begingroup$ I am interested in multipartite entanglement. Also, you are right, that account is also me and I have to thank you for reminding me of this! How exactly can I contact moderators to have them merged? Thanks $\endgroup$ Jun 15, 2012 at 16:28

1 Answer 1


M. G. Parker and V. Rijmen have studied the quantum entanglement of binary and bipolar sequences in arXiv:quant-ph/0107106. I remember reading their paper long ago. They use a lot of terminology from coding theory, so now by just skimming through, I can't understand exactly what their result is, but you can have a deeper look.

Notice also that graph states are a special case of your states. In particular, $\psi$ is a graph state if and only if the sequence $x$ is generated by a quadratic polynomial in GF(2).

  • 4
    $\begingroup$ The class of states corresponds exactly to hypergraph states, where hyper-edges correspond to controlled-controlled-...-controlled-Z gates. $\endgroup$ Jun 8, 2012 at 15:11
  • $\begingroup$ @JoeFitzsimons: true. I am curious to know if anyone has ever used the name hypergraph states. $\endgroup$ Jun 8, 2012 at 15:24
  • 3
    $\begingroup$ I'm not sure if it appears in the literature or not, but certainly I have used it and heard it used in private correspondence. $\endgroup$ Jun 8, 2012 at 15:31
  • $\begingroup$ Alesssandro, thank you for your comment, this is precisely the type of connection I suspected would exist.I will definitely look at this more carefully. Also, a scholar google search of "hypergraph states" yields only 3 results, so I do not think it is a standard term in the literature. $\endgroup$ Jun 11, 2012 at 15:59

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.