Comment: Would you like this article to be moved to the Draft namespace? It should be moved before it is reviewed. Noahfgodard (talk) 15:26, 7 December 2020 (UTC)

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}$ .^[1]

It has been used to find quantum communication problems that demonstrate super-polynomial advantage of over classical ones.^[1]^[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.^[3] 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 to restrictions of a specific communication model.

There are two key communication models that can be considered:^[2]

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.^[2]

History

The Hidden Matching Problem was first defined in 2004 by Bar-Yossef, Jayram and Kerenidis.^[5] Through this 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.

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.^[1] This was later proven to be true by Gavinsky et al.^[6]

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.^[2]

Applications

The Hidden Matching Problem was used as the basis of Gavinsky's 2012 Quantum Coin Scheme.^[7] 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. 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}}$

References

^ ^a ^b ^c Bar-Yossef, Ziv; Jayram, T. S.; Kerenidis, Iordanis (2004-06-13). "Exponential separation of quantum and classical one-way communication complexity". Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. STOC '04. Chicago, IL, USA: Association for Computing Machinery: 128–137. doi:10.1145/1007352.1007379. ISBN 978-1-58113-852-8.
^ ^a ^b ^c ^d Gavinsky, Dmitry (2008-05-17). "Classical interaction cannot replace a quantum message". Proceedings of the fortieth annual ACM symposium on Theory of computing. STOC '08. Victoria, British Columbia, Canada: Association for Computing Machinery: 95–102. doi:10.1145/1374376.1374393. ISBN 978-1-60558-047-0.
^ ^a ^b Doriguello, João F. (2020). "Exponential quantum communication reductions from generalizations of the Boolean Hidden Matching problem" (PDF). 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020).
^ Yao, Andrew Chi-Chih (1979-04-30). "Some complexity questions related to distributive computing(Preliminary Report)". Proceedings of the eleventh annual ACM symposium on Theory of computing. STOC '79. Atlanta, Georgia, USA: Association for Computing Machinery: 209–213. doi:10.1145/800135.804414. ISBN 978-1-4503-7438-5.
^ Bar-Yossef, Ziv; Jayram, T. S.; Kerenidis, Iordanis (2004-06-13). "Exponential separation of quantum and classical one-way communication complexity". Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. STOC '04. Chicago, IL, USA: Association for Computing Machinery: 128–137. doi:10.1145/1007352.1007379. ISBN 978-1-58113-852-8.
^ Gavinsky, Dmitry; Kempe, Julia; Kerenidis, Iordanis; Raz, Ran; de Wolf, Ronald (2007-06-11). "Exponential separations for one-way quantum communication complexity, with applications to cryptography". Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. STOC '07. San Diego, California, USA: Association for Computing Machinery: 516–525. doi:10.1145/1250790.1250866. ISBN 978-1-59593-631-8.
^ Gavinsky, D. (2012-06). "Quantum Money with Classical Verification". 2012 IEEE 27th Conference on Computational Complexity: 42–52. doi:10.1109/CCC.2012.10. {{cite journal}}: Check date values in: |date= (help)

[:0-1] Bar-Yossef, Ziv; Jayram, T. S.; Kerenidis, Iordanis (2004-06-13). "Exponential separation of quantum and classical one-way communication complexity". Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. STOC '04. Chicago, IL, USA: Association for Computing Machinery: 128–137. doi:10.1145/1007352.1007379. ISBN 978-1-58113-852-8.

[:1-2] Gavinsky, Dmitry (2008-05-17). "Classical interaction cannot replace a quantum message". Proceedings of the fortieth annual ACM symposium on Theory of computing. STOC '08. Victoria, British Columbia, Canada: Association for Computing Machinery: 95–102. doi:10.1145/1374376.1374393. ISBN 978-1-60558-047-0.

[:2-3] Doriguello, João F. (2020). "Exponential quantum communication reductions from generalizations of the Boolean Hidden Matching problem" (PDF). 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020).

[4] Yao, Andrew Chi-Chih (1979-04-30). "Some complexity questions related to distributive computing(Preliminary Report)". Proceedings of the eleventh annual ACM symposium on Theory of computing. STOC '79. Atlanta, Georgia, USA: Association for Computing Machinery: 209–213. doi:10.1145/800135.804414. ISBN 978-1-4503-7438-5.

[5] Bar-Yossef, Ziv; Jayram, T. S.; Kerenidis, Iordanis (2004-06-13). "Exponential separation of quantum and classical one-way communication complexity". Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. STOC '04. Chicago, IL, USA: Association for Computing Machinery: 128–137. doi:10.1145/1007352.1007379. ISBN 978-1-58113-852-8.

[6] Gavinsky, Dmitry; Kempe, Julia; Kerenidis, Iordanis; Raz, Ran; de Wolf, Ronald (2007-06-11). "Exponential separations for one-way quantum communication complexity, with applications to cryptography". Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. STOC '07. San Diego, California, USA: Association for Computing Machinery: 516–525. doi:10.1145/1250790.1250866. ISBN 978-1-59593-631-8.

[7] Gavinsky, D. (2012-06). "Quantum Money with Classical Verification". 2012 IEEE 27th Conference on Computational Complexity: 42–52. doi:10.1109/CCC.2012.10. {{cite journal}}: Check date values in: |date= (help)

[1]

[2]

[3]

[4]

[5]

[6]

[7]