On Quantum Query Complexity, Divide-and-Conquer, and Regular Languages
Our recent work investigated the use of divide-and-conquer strategies in the design of quantum query algorithms. Following a brief review of these findings, this talk will focus on ongoing work aimed at strengthening one of our earlier results. In particular, we will propose a randomized quantum query algorithm for checking membership in a specific regular language. The analysis of this algorithm will be discussed, with an emphasis on some of the technical details. We conclude with some of the potential implications of our research.
Local Hamiltonians and the Quantum PCP Conjecture
The Quantum PCP Conjecture (QPCP) claims that estimating ground-state energies of local Hamiltonians to constant precision is hard for quantum computers. If true, QPCP implies the existence of local Hamiltonians with non-trivial low-energy space properties, and a recent trend has been to construct (or conjecture) such Hamiltonians independently of QPCP. This proposal will focus on topics surrounding QPCP and one such implication, the No Low-energy Sampleable States (NLSS) Conjecture.