Adaptive Quantum Computers: decoding and state preparation
Niels M. P. Neumann

Abstract:
The concept of computers dates back to the late 19th century. Over the years, significant progress has been made towards their physical realization. Today, we can hardly imagine a world without computers and we use them for a wide range of applications in our daily life. Extensive research efforts focus on enhancing the power of computers and exploring new ways of performing computations. One promising approach is quantum computing. Future quantum computers have the potential to solve specific problems significantly faster than current methods. These quantum computers will have to interact with a standard computer to operate effectively.

Current quantum computers are still under development and have limited capabilities. However, the interaction with a standard computer can already enhance their functionality, 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. The work is divided into two main parts.

The first part shows that adaptive quantum computers are more powerful than standard computers. It focuses on 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.

The second part explores how adaptive quantum computations can improve non-adaptive quantum computations, for instance by performing various quantum computations faster. Using these faster computations, adaptive quantum computers can also prepare quantum states more efficiently than their non-adaptive counterparts. Quantum states describe the computational units of a quantum computer, making the task of preparing them inherently quantum. This work presents efficient adaptive quantum computations to prepare quantum states such as 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.