Hidden Matching Problem Explained

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 l{M} _{n} (l{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} ⊕ x _{j} .^[1]

It has been used to find quantum communication problems that demonstrate super-polynomial advantage of over classical ones.^{[2] [3]}

Background

Communication complexity is a model of computation first introduced by Yao in 1979.^[4] 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.^[1] 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

l{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

(1)/(\sqrt n) \sum ^{n} _{i =1} ( -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 (1)/(\sqrt 2) \left( |i\rangle \pm |j\rangle\right) .

With a classical message, Alice has to send on order of

l{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.^[5]

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.^[6] 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} it{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 it{HMP} _{4} ifb = \begin{cases}x _{1} ⊗ x _{2+m} , if a = 0 \\x _{3-m} ⊗ x _{4,} if a =1 , \end{cases} it{HMP} _{4} refers to the four bit version of the Hidden Matching Problem.

References

1. Book: Bar-Yossef. Ziv. Jayram. T. S.. Kerenidis. Iordanis. Proceedings of the thirty-sixth annual ACM symposium on Theory of computing . Exponential separation of quantum and classical one-way communication complexity . 2004-06-13. https://doi.org/10.1145/1007352.1007379. STOC '04. Chicago, IL, USA. Association for Computing Machinery. 128–137. 10.1145/1007352.1007379. 978-1-58113-852-8. 557748.
2. Book: Gavinsky, Dmitry. Proceedings of the fortieth annual ACM symposium on Theory of computing . Classical interaction cannot replace a quantum message . 2008-05-17. https://doi.org/10.1145/1374376.1374393. STOC '08. Victoria, British Columbia, Canada. Association for Computing Machinery. 95–102. 10.1145/1374376.1374393. 978-1-60558-047-0. 6659329.
3. Doriguello. João F.. 2020. Exponential quantum communication reductions from generalizations of the Boolean Hidden Matching problem.. 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs) . 158 . 1:1–1:16 . 10.4230/LIPIcs.TQC.2020.1 . free . 2001.05553 . 9783959771467 . 210701354 .
4. Book: Yao, Andrew Chi-Chih. Proceedings of the eleventh annual ACM symposium on Theory of computing - STOC '79 . Some complexity questions related to distributive computing(Preliminary Report) . 1979-04-30. Atlanta, Georgia, USA. Association for Computing Machinery. 209–213. 10.1145/800135.804414. 978-1-4503-7438-5. 999287. free.
5. Book: Gavinsky. Dmitry. Kempe. Julia. Kerenidis. Iordanis. Raz. Ran. de Wolf. Ronald. Proceedings of the thirty-ninth annual ACM symposium on Theory of computing . Exponential separations for one-way quantum communication complexity, with applications to cryptography . 2007-06-11. https://doi.org/10.1145/1250790.1250866. STOC '07. San Diego, California, USA. Association for Computing Machinery. 516–525. 10.1145/1250790.1250866. 978-1-59593-631-8. 444057.
6. Book: Gavinsky, D.. 2012 IEEE 27th Conference on Computational Complexity . Quantum Money with Classical Verification . June 2012. https://ieeexplore.ieee.org/document/6243380/;jsessionid=l1Ejmk825UmS2aFqTn3Hy19mgrDv9AmeSGJmzzAZe1oZE3dAk7ch!614573127. 42–52. 10.1109/CCC.2012.10. 1109.0372. 978-0-7695-4708-4. 11673644.