Quantum Query Lower Bounds for Time/Space Tradeoffs

252 / BBB

2025-09-23

J. M.

16:30

Due to the severe limitations of current quantum computers regarding qubit count, this thesis aims to advance the knowledge about quantum time/space tradeoff lower bounds in terms of quantum query complexity. To this end, we leverage the recording query framework
of Hamoudi and Magniez to analyze the Text-to-Pattern Hamming Distance problem. For input size 𝑁 , we obtain a lower bound on the time/space product of 𝑇 · 𝑆 ∈ Ω(𝑁^3/2) using Golomb rulers and 𝑇 · 𝑆 ∈ Ω(𝑁^2) by reducing from the convolution problem using a result of Beame, Kornerup, and Whitmeyer. The latter coincides with a classical result by Abrahamson thereby showing that for this problem quantum algorithms cannot exhibit an advantage over classical ones in terms of the time/space product. Our construction may also be of interest for other problems.

Further, we address an open problem by Hamoudi and Magniez to analyze the quantum sorting problem in an adaptive setting where an algorithm may choose when to produce which output depending on the input. In particular, we prove a query lower bound in the heavily restricted space regime: Any quantum algorithm that solves the quantum sorting problem in the adaptive setting with space polylog 𝑁 must make Ω(𝑁^4/3) queries to the input. We also discuss barriers to proving stronger bounds.

Finally, we address an open problem by Aaronson on the computational power of in-place (or minimal/erasing) oracles without access to their inverses. Although we cannot settle said problem, we are able to prove additional requirements to obtain a desired separation for a candidate problem of Holman, Ramachandran, and Yirka. We further discuss the limitations of current methods.