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.
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.
We formulate and investigate the simplest version of time-optimal quantum computation theory (TO-QCT), where the computation time is defined by the physical one and the Hamiltonian contains only one- and two-qubit interactions. This version of TO-QCT is also considered as optimality by sub-Riemannian geodesic length. The work has two aims: One is to develop a TO-QCT itself based on a physically natural concept of time, and the other is to pursue the possibility of using TO-QCT as a tool to estimate the complexity in conventional gate-optimal quantum computation theory (GO-QCT). In particular, we investigate to what extent is true the following statement: Time complexity is polynomial in the number of qubits if and only if gate complexity is also. In the analysis, we relate TO-QCT and optimal control theory (OCT) through fidelity-optimal computation theory (FO-QCT); FO-QCT is equivalent to TO-QCT in the limit of unit optimal fidelity, while it is formally similar to OCT. We then develop an efficient numerical scheme for FO-QCT by modifying Krotov's method in OCT, which has a monotonic convergence property. We implemented the scheme and obtained solutions of FO-QCT and of TO-QCT for the quantum Fourier transform and a unitary operator that does not have an apparent symmetry. The former has a polynomial gate complexity and the latter is expected to have an exponential one which is based on the fact that a series of generic unitary operators has an exponential gate complexity. The time complexity for the former is found to be linear in the number of qubits, which is understood naturally by the existence of an upper bound. The time complexity for the latter is exponential in the number of qubits. Thus, both the targets seem to be examples satisfyng the preceding statement. The typical characteristics of the optimal Hamiltonians are symmetry under time reversal and constancy of one-qubit operation, which are mathematically shown to hold in fairly general situations.
Is the universe computable? If yes, is it computationally a polynomial place? In standard quantum mechanics, which permits infinite parallelism and the infinitely precise specification of states, a negative answer to both questions is not ruled out. On the other hand, empirical evidence suggests that NP‐complete problems are intractable in the physical world. Likewise, computational problems known to be algorithmically uncomputable do not seem to be computable by any physical means. We suggest that this close correspondence between the efficiency and power of abstract algorithms on the one hand, and physical computers on the other, finds a natural explanation if the universe is assumed to be algorithmic; that is, that physical reality is the product of discrete sub‐physical information processing equivalent to the actions of a probabilistic Turing machine. This assumption can be reconciled with the observed exponentiality of quantum systems at microscopic scales, and the consequent possibility of implementing Shor’s quantum polynomial time algorithm at that scale, provided the degree of superposition is intrinsically, finitely upper‐bounded. If this bound is associated with the quantum‐classical divide (the Heisenberg cut), a natural resolution to the quantum measurement problem arises. From this viewpoint, macroscopic classicality is an evidence that the universe is in BPP, and both questions raised above receive affirmative answers. A recently proposed computational model of quantum measurement, which relates the Heisenberg cut to the discreteness of Hilbert space, is briefly discussed. A connection to quantum gravity is noted. Our results are compatible with the philosophy that mathematical truths are independent of the laws of physics.
The interface between the quantum and the classical is an intriguing and, at times, hotly contested subject of ongoing research. The quantum regime is characterized by interference, made possible by the superposition principle, while such phenomena are absent in macroscopic, everyday experience. Here, we investigate the link of this absence (or, as we will argue, unobservability) to computational complexity. We show how the assumption that quantum systems cannot solve NP-complete problems efficiently implies that certain formally valid quantum measurements on finite-dimensional systems are unperformable. We study several consequences of this restriction. First, Pauli matrices in an inconveniently transformed basis are a simple example of unobservables. Furthermore, some quantum states are not connected by any physically realizable time evolution. Finally there are quantum states whose coherence cannot be observed, i.e. superpositions of pure quantum states which are indistinguishable from mixtures. We discuss the connection of this phenomenon to the presence of superselection sectors. Our results suggest that the apparent classicality of macroscopic systems may be partly due to limitations on measurements and time evolutions imposed by computational complexity.
Physical consequences of P=NP
Computational complexity theory contains a corpus of theorems and conjectures regarding the time a Turing machine will need to solve certain types of problems as a function of the input size. Nature {\em need not} be a Turing machine and, thus, these theorems do not apply directly to it. But {\em classical simulations} of physical processes are programs running on Turing machines and, as such, are subject to them. In this work, computational complexity theory is applied to classical simulations of systems performing an adiabatic quantum computation (AQC), based on an annealed extension of the density matrix renormalization group (DMRG). We conjecture that the computational time required for those classical simulations is controlled solely by the {\em maximal entanglement} found during the process. Thus, lower bounds on the growth of entanglement with the system size can be provided. In some cases, quantum phase transitions can be predicted to take place in certain inhomogeneous systems. Concretely, physical conclusions are drawn from the assumption that the complexity classes {\bf P} and {\bf NP} differ. As a by-product, an alternative measure of entanglement is proposed which, via Chebyshev's inequality, allows to establish strict bounds on the required computational time.
Many natural problems in quantum computing involve constructing a quantum state or implementing a unitary transformation. However, relatively little is known about the computational complexity of these problems compared to that of computing boolean functions. In this thesis we do the following:• We prove upper bounds on the complexity of constructing arbitrary states and implementing arbitrary unitaries with the help of a classical oracle. • We prove bounds on the complexity of computing parity in QAC0, a quantum analogue of AC0, by way of a reduction to the task of constructing a certain type of state. • We prove upper bounds on the circuit size and depth required to construct arbitrary states and implement arbitrary unitaries, in various quantum circuit models. Many of these bounds are tight. • We define models of interactive proofs for constructing states and implementing unitaries with the help of an untrusted prover. We prove a quantum state analogue of the inclusion PSPACE ⊆ QIP, and obtain somewhat analogous results for unitaries and with multiple entangled provers. • We present barriers to improving several of the above results.
Abstract Entropy has played an essential role in the history of physics. Its mathematical definition and applications have changed over time till today. In this paper, we first review the historical evolution of these various points of view, from the thermodynamic definition to information entropy from Shannon in classical physics, up to the modern concept of Neumann’s quantum entropy. As a specific example, we consider entanglement entropy and compare the phase space approach in classical physics to the Hilbert space approach in quantum physics in simple model systems. We derive a general expression for the entanglement entropy of fermions and bosons in arbitrary partitions of Hilbert space, valid beyond the thermodynamic limit. Next, we compare thermodynamic heat engines with quantum heat engines. Finally, we proceed to the more general concept of quantum (computational) complexity and argue, using the concept of entanglement entropy, that the Heisenberg time in classically chaotic systems coincides with the time when maximal complexity is reached in the quantum case for systems with all–all interactions.