Implementation complexity of physical processes as a natural extension of computational complexity

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. (Abstract Copyright [2006], Wiley Periodicals, Inc.)