Quantum communication upper-bound conjecture for Hidden Hypermatching

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/α)11/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.

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

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.