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.
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.
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 need not be a Turing machine and, thus, these theorems do not apply directly to it. But 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 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 P and NP differ. As a by-product, an alternative measure of entanglement is proposed which, via Chebyshev's inequality, allows us to establish strict bounds on the required computational time.
The central problem in computer science is the conjecture that two complexity classes, P (polynomial time) and NP (nondeterministic polynomial time-roughly those decision problems for which a proposed solution can be checked in polynomial time), are distinct in the standard Turing model of computation: P not equal NP. As a generality, we propose that each physical theory supports computational models whose power is limited by the physical theory. It is well known that classical physics supports a multitude of implementation of the Turing machine. Non-Abelian topological quantum field theories exhibit the mathematical features necessary to support a model capable of solving all #P problems, a computationally intractable class, in polynomial time. Specifically, Witten [Witten, E. (1989) Commun. Math. Phys. 121, 351-391] has identified expectation values in a certain SU(2)-field theory with values of the Jones polynomial [Jones, V. (1985) Bull. Am. Math. Soc. 12, 103-111] that are #P-hard [Jaeger, F., Vertigen, D. & Welsh, D. (1990) Math. Proc. Comb. Philos. Soc. 108, 35-53]. This suggests that some physical system whose effective Lagrangian contains a non-Abelian topological term might be manipulated to serve as an analog computer capable of solving NP or even #P-hard problems in polynomial time. Defining such a system and addressing the accuracy issues inherent in preparation and measurement is a major unsolved problem.
Abstract. In this paper we study quantum computation from a complexity theoretic viewpoint. Our rst result is the existence of an ecient universal quantum Turing machine in Deutsch’s model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97{117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specied. We prove that O(log T) bits of precision suce to support a T step computation. This justies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the rst formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church{Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class BPP. The class BQP of languages that are eciently decidable (with small error-probability) on a quantum Turing machine satises BPP ⊆ BQP ⊆ P]P. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that O(logT) bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
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.
In contrast to classical many-particle systems for which the number of degrees of freedom grows linearly with the system size, it grows exponentially for quantum many-particle systems. On the one hand, the resulting complexity of the quantum systems has a high potential for technological advances if it can be exploited directly. For example, in recent years, the fundamentals for the realization of quantum computers and their possible applications have been investigated intensely. On the other hand, the high complexity, especially in strongly correlated regimes, often makes the analytical or numerical analysis of underlying physical phenomena very difficult. This is why some systems of high technological relevance, like the high-temperature superconductors, are still unsatisfactorily understood. A main topic of this thesis is the development of efficient numerical methods for the simulation of strongly correlated quantum lattice models. For one-dimensional systems, the density-matrix renormalization-group (DMRG) is such a very successful method. The physical states of interest are approximated within a certain class of ansatz states. These ansatz states are designed in a way that the number of degrees of freedom are prevented from growing exponentially. With the DMRG method, ground states of interacting one-dimensional systems can often be determined with very high precision. This observation indicates already that ground states actually do not exhaust the available exponential number of degrees of freedom but can be described efficiently with much fewer parameters. The ansatz states used in DMRG are the so-called matrix product states. A very useful criterion for the construction of corresponding appropriate ansatz states for higher-dimensional systems is the quantum nonlocality as for example quantified by the entanglement entropy. The ansatz states should be able to reproduce the scaling properties of the quantum nonlocality in the physical states of interest with as few parameters as possible. The first part of the thesis, therefore, provides analytical and numerical analysis of the scaling of quantum nonlocality with the system size or time in different, physically relevant scenarios. For example, the scaling of Renyi entropies and their dependence on boundary conditions is derived within the 1+1-dimensional conformal field theory. Conjectures and analytical indications concerning the properties of entanglement entropy in critical fermionic and bosonic systems are confirmed numerically with high precision. For integrable models in the thermodynamic limit, general preconditions are derived under which subsystems converge to steady states. These steady states are non-thermal and retain information about the initial state. It is shown that the entanglement entropy in such steady states is extensive. For short times, the entanglement entropy grows typically linearly with time, causing an exponential increase in computation costs for the DMRG method. Consequently, time-dependent DMRG simulations usually have no direct access to the long time regime. The second part of the thesis focuses on the development and improvement of the above-mentioned numerical techniques. The time-dependent DMRG is complemented with an extrapolation technique for the evaluated observables. In this way, the problem of the entropy increase can be circumvented, allowing for a precise determination of spectral functions. The method is demonstrated using the example of the Heisenberg antiferromagnet and results are compared to Bethe-Ansatz data for T=0 and quantum Monte Carlo data for T>0. For the simulation of higher-dimensional systems, projected-entangled pair-states (PEPS) and the multiscale entanglement renormalization ansatz (MERA) turn out to be appropriate wavefunction classes. Initially, they could only be used for spin systems. Within this thesis, variants of those state classes are being suggested for the fermionic case. It is shown how the known algorithms for spin systems can be translated into corresponding algorithms for the fermionic systems. The occurring computation costs increase only by a marginal overhead. First numerical benchmarking tests proceeded successfully. Thus, new techniques are available which can for example be used to examine the two-dimensional Hubbard model. This model is a candidate for the description of high-temperature superconductivity.