We study the computational complexity of certain integrable quantum theories in 1+1 dimensions. We formalize a model of quantum computation based on these theories. In this model, distinguishable particles start out with known momenta and initial superposition of different configurations. Then the label of these particles are measured at the end. We prove that additive approximation to single amplitudes of these models can be obtained by the one-clean-qubit model, if no initial superpositions are allowed. However, if arbitrary initial states and non-adaptive intermediate measurements are allowed, we show that conditioned on infinite polynomial hierarchy assumption it is hard to sample from the output distribution of these models on a classical randomized computer. A classical analogue of this model is also formalized and its computational power is pinned down within the complexity classes below BPP and NP.
Computational Complexity of Some Quantum Theories in 1+1 Dimensions
We study the computational complexity of certain integrable quantum theories in 1+1 dimensions. We formalize a model of quantum computation based on these theories. In this model, distinguishable particles start out with known momenta and initial superposition of different configurations. Then the label of these particles are measured at the end. We prove that additive approximation to single amplitudes of these models can be obtained by the one-clean-qubit model, if no initial superpositions are allowed. However, if arbitrary initial states and non-adaptive intermediate measurements are allowed, we show that conditioned on infinite polynomial hierarchy assumption it is hard to sample from the output distribution of these models on a classical randomized computer. A classical analogue of this model is also formalized and its computational power is pinned down within the complexity classes below BPP and NP.
Inspired by connections to two dimensional quantum theory, we define several models of computation based on permuting distinguishable particles (which we call balls), and characterize their computational complexity. In the quantum setting, we find that the computational power of this model depends on the initial input states. More precisely, with a standard basis input state, we show how to approximate the amplitudes of this model within additive error using the model DQC1 (the class of problems solvable with one clean qubit), providing evidence that the model in this case is weaker than universal quantum computing. However, for specific choices of input states, the model is shown to be universal for BQP in an encoded sense. We use representation theory of the symmetric group to partially classify the computational complexity of this model for arbitrary input states. Interestingly, we find some input states which yield a model intermediate between DQC1 and BQP. Furthermore, we consider a restricted version of this model based on an integrable scattering problem in 1+1 dimensions. We show it is universal under postselection, if we allow intermediate destructive measurements and specific input states. Therefore, the existence of any classical procedure to sample from the output distribution of this model within multiplicative error implies collapse of polynomial hierarchy to its third level. Finally, we define a classical version of this model in which one can probabilistically permute balls. We find this yields a complexity class which is intermediate between L and BPP. Moreover, we find a nondeterministic version of this model is NP-complete.
We define several models of computation based on permuting distinguishable particles (which we call balls) and characterize their computational complexity. In the quantum setting, we use the representation theory of the symmetric group to find variants of this model which are intermediate between BPP and DQC1 (the class of problems solvable with one clean qubit) and between DQC1 and BQP. Furthermore, we consider a restricted version of this model based on an exactly solvable scattering problem of particles moving on a line. Despite the simplicity of this model from the perspective of mathematical physics, we show that if we allow intermediate destructive measurements and specific input states, then the model cannot be efficiently simulated classically up to multiplicative error unless the polynomial hierarchy collapses. Finally, we define a classical version of this model in which one can probabilistically permute balls. We find this yields a complexity class which is intermediate between L and BPP, and that a nondeterministic version of this model is NP-complete.
Deterministic quantum computation with one quantum bit (DQC1), or the one clean qubit model, [E. Knill and R. Laflamme, Phys. Rev. Lett. {\bf81}, 5672 (1998)] is a model of quantum computing where the input is the tensor product of a single pure qubit and many completely-mixed states, and only the single qubit is measured at the end of the computation. In spite of its naive appearance, the DQC1 model can efficiently solve some problems for which no classical efficient algorithms are known, and therefore it has been conjectured that the DQC1 model is more powerful than classical computing (under the assumption of $\mbox{BPP}\subsetneq\mbox{BQP}$). Here we show that the output probability distribution of the DQC1 model cannot be classically efficiently approximated (exactly within a polynomial bit length or in the fully polynomial randomized approximation scheme (FPRAS) with at most a constant error) unless $\mbox{BQP}\subseteq\mbox{BPP}$.
Deterministic quantum computation with one quantum bit (DQC1) [E. Knill and R. Laflamme, Phys. Rev. Lett. 81, 5672 (1998)] is a model of quantum computing where the input is restricted to containing a single qubit in a pure state and has all other qubits in a completely mixed state. Only the single pure qubit is measured at the end of the computation. While it is known that DQC1 can efficiently solve several problems for which no known classical efficient algorithms exist, the question of whether DQC1 is really more powerful than classical computation remains open. In this Letter, we introduce a slightly modified version of DQC1, which we call DQC1(k), where k output qubits are measured, and show that DQC1(k) cannot be classically efficiently simulated for any k≥3 unless the polynomial hierarchy collapses at the third level.
We study quantum communication protocols, in which the players' storage starts out in a state where one qubit is in a pure state, and all other qubits are totally mixed (i.e. in a random state), and no other storage is available (for messages or internal computations). This restriction on the available quantum memory has been studied extensively in the model of quantum circuits, and it is known that classically simulating quantum circuits operating on such memory is hard when the additive error of the simulation is exponentially small (in the input length), under the assumption that the polynomial hierarchy does not collapse. We study this setting in communication complexity. The goal is to consider larger additive error for simulation-hardness results, and to not use unproven assumptions. We define a complexity measure for this model that takes into account that standard error reduction techniques do not work here. We define a clocked and a semi-unclocked model, and describe efficient simulations between those. We characterize a one-way communication version of the model in terms of weakly unbounded error communication complexity. Our main result is that there is a quantum protocol using one clean qubit only and using O(log n) qubits of communication, such that any classical protocol simulating the acceptance behaviour of the quantum protocol within additive error 1/poly(n) needs communication Ω(n). We also describe a candidate problem, for which an exponential gap between the one-clean-qubit communication complexity and the randomized communication complexity is likely to hold, and hence a classical simulation of the one-clean-qubit model within constant additive error might be hard in communication complexity. We describe a geometrical conjecture that implies the lower bound.
We classify two-qubit commuting Hamiltonians in terms of their computational complexity. Suppose one has a two-qubit commuting Hamiltonian H which one can apply to any pair of qubits, starting in a computational basis state. We prove a dichotomy theorem: either this model is efficiently classically simulable or it allows one to sample from probability distributions which cannot be sampled from classically unless the polynomial hierarchy collapses. Furthermore, the only simulable Hamiltonians are those which fail to generate entanglement. This shows that generic two-qubit commuting Hamiltonians can be used to perform computational tasks which are intractable for classical computers under plausible assumptions. Our proof makes use of new postselection gadgets and Lie theory.