This chapter contains sections titled: Introduction Similar Complexity Bounds for Different Tasks Relating Control Problems to Hard Computational Problems The Need for a Control-theoretic Foundation of Complexity Hamiltonians that Compute Autonomously References
Abstract The theory of computational complexity in computer science investigates the time and space resources required to solve a computational problem. We show that an analogous complexity theory can be developed for quantum control problems which do not stem from computational problems. First we use the same mathematical concept to show similar lower bounds on the complexity of the following tasks: (1) Computing the boolean function “Majority”, (1) Optimal algorithmic cooling on n> two‐level systems, (2) Optimal work extraction by a heat engine acting on 2n> hot and 1 cold two‐level system, (3) Preparing appropriate n‐qubit entanglement for improving frequency standards in Ramsey spectroscopy, (4) Implementing a von‐Neumann measurement that is strongly incompatible with macroscopic observables. We describe furthermore instances of the problems “optimal heat engines” and “precise measurements” which are likely to be complex since NP‐ or even PSPACE‐complete computational problems can be reduced to them. In order to define implementation complexity also for other systems than n qubit registers we rephrase some approaches to define complexity measures using a set of available interactions and explore the complexity of analogue to digital conversion using a Jaynes Cumming interaction as an example. Furthermore we argue that, from a physical perspective of complexity, operations should only considered to be simple if there is a physically reasonable Hamiltonian that can implement them by its autonomous time evolution within a short time interval. Therefore we discuss a Hamiltonian whose natural time evolution can implement computation processes.
A computer is a physical device that helps us process information by executing algorithms. An algorithm is a well-defined procedure, with finite description, for realizing an information-processing task. An information-processing task can always be translated into a physical task. When designing complex algorithms and protocols for various information-processing tasks, it is very helpful, perhaps essential, to work with some idealized computing model. However, when studying the true limitations of a computing device, especially for some practical reason, it is important not to forget the relationship between computing and physics. Real computing devices are embodied in a larger and often richer physical reality than is represented by the idealized computing model. Quantum information processing is the result of using the physical reality that quantum theory tells us about for the purposes of performing tasks that were previously thought impossible or infeasible. Devices that perform quantum information processing are known as quantum computers. In this book we examine how quantum computers can be used to solve certain problems more efficiently than can be done with classical computers, and also how this can be done reliably even when there is a possibility for errors to occur. In this first chapter we present some fundamental notions of computation theory and quantum physics that will form the basis for much of what follows. After this brief introduction, we will review the necessary tools from linear algebra in Chapter 2, and detail the framework of quantum mechanics, as relevant to our model of quantum computation, in Chapter 3. In the remainder of the book we examine quantum teleportation, quantum algorithms and quantum error correction in detail. We are often interested in the amount of resources used by a computer to solve a problem, and we refer to this as the complexity of the computation. An important resource for a computer is time. Another resource is space, which refers to the amount of memory used by the computer in performing the computation. We measure the amount of a resource used in a computation for solving a given problem as a function of the length of the input of an instance of that problem.