FET: Small: Quantum Time-Space Tradeoffs and Classical Lifting

Quantum computers offer the potential for substantial speed-ups over classical computers. This project focusses on the extent to which such speed-ups are limited by constraints on the amount of quantum memory available. These constraints are likely to be considerable, particularly in the near term.

Considering the resources of time and quantum memory together is critical for understanding which applications will be able to make best use of quantum computers. This project will build on methods developed by the investigator to analyze the combinations of time and quantum memory necessary for computational tasks, extending these methods to understand the trade-offs between these two resources required for a wide variety of computational tasks.

This project also focuses on improving and extending methods, known as lifting theorems, that allow one to translate the understanding of computation by individual computing devices to computations involving interacting devices. Such theorems have been at the heart of many results in the last decade that have resolved longstanding open questions and have the potential to achieve much more.

Thus there will be positive impacts on the field of complexity theory as well as development of near-term quantum computing devices. In addition, there will be training and mentoring of both undergraduate and graduate students, who will have the benefit of working in interdisciplinary research.

The space used by a quantum algorithm is the maximum number of qubits that need to be maintained in simultaneous superposition during the algorithm's execution. Maintaining a large number of qubits in simultaneous superposition is a particularly difficult challenge, making space an even more important resource for quantum algorithms than space is for classical algorithms.

The investigator recently introduced a technique for producing strong time lower bounds for space-bounded quantum algorithms and applied it to a number of computational problems in linear algebra and Boolean algebra, matching or improving the best classical lower bounds and yielding optimal results in many cases. This project will focus on extending this technique, and related analyses in quantum computation, to a wide variety of other computational problems for which classical time-space trade-off lower bounds are currently known.

It will also focus on developing new methods for obtaining quantum time-space trade-off lower bounds for problems with sub-linear-time quantum algorithms. This project also aims to improve the parameters and extend the range of communication models in current lifting theorems that derive communication complexity lower bounds from query complexity lower bounds.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.