Over the past several decades, quantum information science has emerged to seek answers
to the question: can we gain some advantage by storing, transmitting and processing …

Quantum computers can execute algorithms that dramatically outperform classical
computation. As the best-known example, Shor discovered an efficient quantum algorithm …

Compiling quantum algorithms for near-term quantum computers (accounting for
connectivity and native gate alphabets) is a major challenge that has received significant …

Quantum computers are unnecessary for exponentially efficient computation or simulation if
the Extended Church-Turing thesis is correct. The thesis would be strongly contradicted by …

We give arguments for the existence of a thermodynamics of quantum complexity that
includes a “second law of complexity.” To guide us, we derive a correspondence between …

Deterministic quantum computation with one pure qubit (DQC1) is an efficient model of
computation that uses highly mixed states. Unlike pure-state models, its power is not derived …

Quantum information science explores the frontier of highly complex quantum states, the"
entanglement frontier." This study is motivated by the observation (widely believed but …

Topological quantum computation is a computational paradigm based on topological
phases of matter, which are governed by topological quantum field theories. In this …

We address the long-standing question of the computational complexity of determining
homology groups of simplicial complexes, a fundamental task in computational topology …

Quantum algorithms for topological data analysis (TDA) seem to provide an exponential
advantage over the best classical approach while remaining immune to dequantization …