Hidden Matching Problem

The Hidden Matching Problem is a computation complexity problem that can be solved using quantum protocols: Let $n$ be a positive even integer. In the Hidden Matching Problem, Alice is given $x\in \{0,1\}^{n}$ and Bob is given $M\in {\mathcal {M}}_{n}$(${\mathcal {M}}_{n}$ denotes the family of all possible perfect matchings on $n$ nodes). Their goal is to output a tuple $\langle i,j,b\rangle$ such that the edge $(i,j)$ belongs to the matching $M$ and $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 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$ and Bob knows only information $y$, and they want to solve some function $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 Bar-Yossef, Jayram and 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 ${\mathcal {O}}(\log n)$, yet any randomized one-way protocol with bounded error must use $\Omega ({\sqrt {n}})$ bits of communication. The Hidden Matching Problem is a relational problem.

Alice sends a superposition ${\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\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 ${\frac {1}{\sqrt {2}}}\left(|i\rangle \pm |j\rangle \right)$.

With a classical message, Alice has to send on order of ${\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 Gavinsky et al.

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.

Applications

The Hidden Matching Problem was used as the basis of Gavinsky's 2012 Quantum Coin Scheme. Bob has been given a coin as payment for some goods or services. This coin consists of a quantum register containing multiple qubits. Bob wishes to verify that the coin is legitimate.

In a classical scenario, a digital coin is made up of a unique string of classical bits, a coin holder sends this string to the bank and the bank compares it to a static database of valid strings. If the string exists in the database then the bank confirms that the coin is valid. However, this leaves the potential for an adversary to masquerade as the bank and steal a coin holder's coin under the pretence of verifying it.

Using the Hidden matching problem, the coin holder can send the relevant information to the bank and the bank can verify that the coin is legitimate but an adversary masquerading as a bank will not learn enough to be able to reproduce the coin.

In the protocol Bob will provide  values $(a_{i},b_{i})$ to the bank. These values $(a_{i},b_{i})$ are attained by Bob measuring certain quantum registers in his coin. The bank holds the values $x_{i}$ (the classical bit strings) and $m_{i}$. If $\forall i\;(x_{i},m_{i},a_{i},b_{i})\in {\textit {HMP}}_{4}$, then the bank can verify that Bob does in fact hold a valid coin corresponding to the classical values $x_{i}$.

For $x\in \{0,1\}^{4}$ and $m,a,b\in \{0,1\}$, we say that $(x,m,a,b)\in {\textit {HMP}}_{4}$ if

$b={\begin{cases}x_{1}\otimes x_{2+m},\quad {\text{if }}a=0\\x_{3-m}\otimes x_{4},\quad {\text{if }}a=1,\end{cases}}$

${\textit {HMP}}_{4}$ refers to the four bit version of the Hidden Matching Problem.