Showing 2026Show all
2 papers · 1 filter
quant-ph2026
Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem
Mark Bun, Joao F. Doriguello, John Kallaugher +1
We study the one-way communication complexity of the -Boolean Hidden Partition problem. Here, Alice is given an -bit string and Bob is given disjoint blocks of its ind…
quant-ph2026
Random Order in Quantum Streaming: Replenishment and Robust Lower Bounds
Nadezhda Voronova
How can random order change the role of quantum memory in streaming? Later classical input can restore the usefulness of a quantum state consumed by earlier queries. We call this r…