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]

^ ^a ^b 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. pp. 128–137. doi:10.1145/1007352.1007379. ISBN 978-1-58113-852-8. S2CID 557748.
^ 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. pp. 95–102. doi:10.1145/1374376.1374393. ISBN 978-1-60558-047-0. S2CID 6659329.
^ 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). Leibniz International Proceedings in Informatics (LIPIcs). 158: 1:1–1:16. arXiv:2001.05553. doi:10.4230/LIPIcs.TQC.2020.1. ISBN 9783959771467. S2CID 210701354.

[: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. pp. 128–137. doi:10.1145/1007352.1007379. ISBN 978-1-58113-852-8. S2CID 557748.

[: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. pp. 95–102. doi:10.1145/1374376.1374393. ISBN 978-1-60558-047-0. S2CID 6659329.

[: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). Leibniz International Proceedings in Informatics (LIPIcs). 158: 1:1–1:16. arXiv:2001.05553. doi:10.4230/LIPIcs.TQC.2020.1. ISBN 9783959771467. S2CID 210701354.

[1]

[2]

[3]