In quantum information, the hidden matching problem is a computational complexity problem that can be solved using quantum protocols: Let n {\displaystyle n} be a positive even integer. In the hidden matching problem, Alice is given x ∈ { 0 , 1 } n {\displaystyle x\in \{0,1\}^{n}} and Bob is given M ∈ M n {\displaystyle M\in {\mathcal {M}}_{n}} ( M n {\displaystyle {\mathcal {M}}_{n}} denotes the family of all possible perfect matchings on n {\displaystyle n} nodes). Their goal is to output a tuple ⟨ i , j , b ⟩ {\displaystyle \langle i,j,b\rangle } such that the edge ( i , j ) {\displaystyle (i,j)} belongs to the matching M {\displaystyle M} and b = x i ⊕ x j {\displaystyle b=x_{i}\oplus x_{j}} . It has been used to find quantum communication problems that demonstrate super-polynomial advantage of over classical ones.
Background Communication complexity is a model of computation first introduced by Andrew Yao in 1979. Two parties (normally called Alice and Bob) each hold a piece of data and want to solve some computational task that jointly depends on their data. Alice knows only information x {\displaystyle x} and Bob knows only information y {\displaystyle y} , and they want to solve some function f ( x , y ) {\displaystyle f(x,y)} . In order to do so, they will need to communicate between themselves, and their goal is to solve the problem with minimal communication obeying the restrictions of a specific communication model. There are two key communication models that can be considered:
One-way communication is the model where Alice sends a single message to Bob who has to give an answer, based on the content of the message and his part of input. Interactive (two-way) communication is the model where the players can interactively exchange messages till Bob decides to give an answer, based on the communication transcript and his part of input. Communication tasks can be either functional, meaning that there is exactly one correct answer corresponding to every possible input, or relational, when multiple correct answers are allowed.
History The hidden matching problem was first defined in 2004 by Zir Bar-Yossef, T. S. Jayram and Ionardis Kerenidis. Through its definition, they were able to provide the first exponential separation between quantum and bounded-error randomized one-way communication complexity. They proved that the quantum one-way communication complexity of the hidden matching problem is O ( log n ) {\displaystyle {\mathcal {O}}(\log n)} , yet any randomized one-way protocol with bounded error must use Ω ( n ) {\displaystyle \Omega ({\sqrt {n}})} bits of communication. The hidden matching problem is a relational problem. Alice sends a superposition 1 n ∑ i = 1 n ( − 1 ) x i | i ⟩ {\displaystyle {\frac {1}{\sqrt {n}}}\sum _{i=1}^{n}(-1)^{x_{i}}|i\rangle } to Bob. Bob uses his perfect matching to project this quantum state onto one of n/2 orthogonal 2D projectors, with a projector onto the space spanned by { | i ⟩ , | j ⟩ } {\displaystyle \{|i\rangle ,|j\rangle \}} for pairing of i and j. After measurement, the quantum state is specified by the measured projector. The bit b determines whether the resulting state is 1 2 ( | i ⟩ ± | j ⟩ ) {\displaystyle {\frac {1}{\sqrt {2}}}\left(|i\rangle \pm |j\rangle \right)} . With a classical message, Alice has to send on order of O ( n ) {\displaystyle {\mathcal {O}}\left({\sqrt {n}}\right)} bits of information specifying the value of x for that many nodes. By the birthday problem, the probability is close to 1 that at least two nodes in that subset are connected by an edge. In the same paper, the authors proposed a boolean version of the problem, the boolean hidden matching problem, and conjectured that the same quantum-classical gap holds for it as well. This was later proven to be true by Dmitry Gavinsky et al in 2007. In 2008, Gavinsky further improved on Bar-Yossef et al.’s result by showing an exponential separation between one-way quantum communication and two-way classical communication.
… excerpt ends here. Continue reading the full article.
