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.
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.
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.
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.
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.
Quantum annealing is a quantum algorithm proposed recently for combinatorial optimization problems. It manipulates time evolution of a quantum mechanical state and obtain an approximate solution. In order to implement the algorithm in classical computers, we propose to apply the density matrix renormalization group method. Simulation of the time evolution of a quantum mechanical state becomes possible by the density matrix renormalization group method for problems of large size. We explain quantum annealing and the density matrix renormalization group method, and present results of numerical simulation using them.
The work that we present in this thesis tries to be at the crossover of quantum information science, quantum many-body physics, and quantum field theory. We use tools from these three fields to analyze problems that arise in the interdisciplinary intersection. More concretely, in Chapter 1 we consider the irreversibility of renormalization group flows from a quantum information perspective by using majorization theory and conformal field theory. In Chapter 2 we compute the entanglement of a single copy of a bipartite quantum system for a variety of models by using techniques from conformal field theory and Toeplitz matrices. The entanglement entropy of the so-called Lipkin-Meshkov-Glick model is computed in Chapter 3, showing analogies with that of (1+1)-dimensional quantum systems. In Chapter 4 we apply the ideas of scaling of quantum correlations in quantum phase transitions to the study of quantum algorithms, focusing on Shor's factorization algorithm and quantum algorithms by adiabatic evolution solving an NP-complete and the searching problems. Also, in Chapter 5 we use techniques originally inspired by condensed-matter physics to develop classical simulations, using the so-called matrix product states, of an adiabatic quantum algorithm. Finally, in Chapter 6 we consider the behavior of some families of quantum algorithms from the perspective of majorization theory. The structure within each Chapter is such that the last section always summarizes the basic results. Some general conclusions and possible future directions are briefly discussed in Chapter 7. Appendix A, Appendix B and Appendix C respectively deal with some basic notions on majorization theory, conformal field theory, and classical complexity theory.
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.