Quantum communication upper-bound conjecture for Hidden Hypermatching

About 5 years old · traced to

Let r,t>2r,t>2, and let r-HH(α,t,n)r\text{-}{\mathsf{HH}}(\alpha,t,n) denote the rr-ary Hidden Hypermatching problem with parameters α\alpha, tt, and nn. A protocol uses quantum communication measured in qubits.

Quantum Hidden Hypermatching upper-bound conjecture. If t,r>2t,r>2, there is a protocol for r-HH(α,t,n)r\text{-}{\mathsf{HH}}(\alpha,t,n) using

O(log⁡(rn)(n/α)1−1/⌈t/2⌉)O\left(\log(rn)(n/\alpha)^{1-1/\lceil t/2\rceil}\right)

qubits.

The conjectured bound would improve the known quantum upper bound in the regime t,r>2t,r>2 and match the corresponding classical communication complexity. The surrounding discussion presents it as motivated by the lower bounds, while the general case remains unresolved.

References

Primary source

Srinivasan Arunachalam and Joao F. Doriguello, “Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case”, arXiv:2109.02600 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.