Adaptive Quantum Computers: decoding and state preparation

Interacting with a standard computer can enhance the capabilities of current quantum computers already today, particularly by offloading certain computations to the standard computer. Quantum computers that interact with standard computers to perform computations are called adaptive quantum computers. This work formalizes a model that describes these adaptive quantum computers. As quantum computers are still under development, this work focuses on computations that terminate after a fixed number of steps, as that makes their implementation likely easier in practice. First, we show that adaptive quantum computers are more powerful than standard computers with respect to the practical problem of retrieving information from corrupted digital data. Standard computers struggle to retrieve such information within a fixed number of computation steps. The proof uses a structure-versus-randomness approach that splits the problem in a structured and a random-like component. The potential of adaptive quantum computations follows from a specific example where information is retrieved from corrupted data. Additionally, adaptive quantum computers can even improve standard computations for this problem that are not constrained by a fixed number of computation steps. Next, we show how adaptive quantum computations can improve non-adaptive quantum computations when preparing specific quantum states. We present efficient adaptive quantum algorithms to prepare the uniform superposition state, the GHZ state, the W-state and the Dicke state. These states are often used in other quantum algorithms, so having efficient routines for preparing them also enhances the efficiency of other algorithms. This work concludes by comparing these adaptive quantum computations with non-adaptive ones, analyzing their performance both theoretically and through quantum hardware implementations.