Quantum communication upper-bound conjecture for Hidden Hypermatching
Quantum communication upper-bound conjecture for Hidden Hypermatching
Let , and let denote the -ary Hidden Hypermatching problem with parameters , , and . A protocol uses quantum communication measured in qubits.
Quantum Hidden Hypermatching upper-bound conjecture. If , there is a protocol for using
qubits.
The conjectured bound would improve the known quantum upper bound in the regime and match the corresponding classical communication complexity. The surrounding discussion presents it as motivated by the lower bounds, while the general case remains unresolved.
Sources & referencesView supporting material
Primary source
Srinivasan Arunachalam and Joao F. Doriguello, “Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case”, arXiv:2109.02600 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.