We address two sets of long-standing open questions in linear algebra and probability theory, from a computational complexity perspective: stochastic matrix divisibility, and divisibility and decomposability of probability distributions. We prove that finite divisibility of stochastic matrices is an NP-complete problem, and extend this result to nonnegative matrices, and completely-positive trace-preserving maps, i.e. the quantum analogue of stochastic matrices. We further prove a complexity hierarchy for the divisibility and decomposability of probability distributions, showing that finite distribution divisibility is in P, but decomposability is NP-hard. For the former, we give an explicit polynomial-time algorithm. All results on distributions extend to weak-membership formulations, proving that the complexity of these problems is robust to perturbations.
We address two sets of long-standing open questions in linear algebra and probability theory, from a computational complexity perspective: stochastic matrix divisibility, and divisibility and decomposability of probability distributions. We prove that finite divisibility of stochastic matrices is an NP-complete problem, and extend this result to nonnegative matrices, and completely-positive trace-preserving maps, i.e. the quantum analogue of stochastic matrices. We further prove a complexity hierarchy for the divisibility and decomposability of probability distributions, showing that finite distribution divisibility is in P, but decomposability is NP-hard. For the former, we give an explicit polynomial-time algorithm. All results on distributions extend to weak-membership formulations, proving that the complexity of these problems is robust to perturbations.
This dissertation investigates the theory of quantum stochastic processes and its applications in quantum many-body physics. The main goal is to analyse complexity-theoretic aspects of both static and dynamic properties of physical systems modelled by quantum stochastic processes. The thesis consists of two parts: the first one addresses the computational complexity of certain quantum and classical divisibility questions, whereas the second one addresses the topic of Hamiltonian complexity theory. In the divisibility part, we discuss the question whether one can efficiently sub-divide a map describing the evolution of a system in a noisy environment, i.e. a CPTP- or stochastic map for quantum and classical processes, respectively, and we prove that taking the nth root of a CPTP or stochastic map is an NP-complete problem. Furthermore, we show that answering the question whether one can divide up a random variable X into a sum of n iid random variables Yi, i.e. X=∑i=1nYi, is poly-time computable; relaxing the iid condition renders the problem NP-hard. In the local Hamiltonian part, we study computation embedded into the ground state of a many-body quantum system, going beyond "history state" constructions with a linear clock. We first develop a series of mathematical techniques which allow us to study the energy spectrum of the resulting Hamiltonian, and extend classical string rewriting to the quantum setting. This allows us to construct the most physically-realistic QMAEXP-complete instances for the LOCAL HAMILTONIAN problem (i.e. the question of estimating the ground state energy of a quantum many-body system) known to date, both in one- and three dimensions. Furthermore, we study weighted versions of linear history state constructions, allowing us to obtain tight lower and upper bounds on the promise gap of the LOCAL HAMILTONIAN problem in various cases. We finally study a classical embedding of a Busy Beaver Turing Machine into a low-dimensional lattice spin model, which allows us to dictate a transition from a purely classical phase to a Toric Code phase at arbitrarily large and potentially even uncomputable system sizes.
We connect both discrete and algebraic complexity theory with the satisfiability problem in certain non-Boolean lattices. Specifically, quantum logic was introduced in 1936 by Garrett Birkhoff and John von Neumann as a framework for capturing the logical peculiarities of quantum observables: in the 1D case it coincides with Boolean propositional logic but, starting with dimension two, violates the distributive law. We introduce the weak and strong satisfiability problem for quantum logic propositional formulae. It turns out that in dimension two, both are also NP --complete. For higher-dimensional spaces ℝ d and ℂ d with d ≥ 3 fixed, on the other hand, we show both problems to be complete for the nondeterministic Blum-Shub-Smale (BSS) model of real computation. This provides a unified view on both Turing and real BSS complexity theory, and extends the (still relatively scarce) list of problems established NP ℝ --complete with one, perhaps, closest in spirit to the classical Cook-Levin Theorem. More precisely, strong satisfiability of ∧ ∨ ∧ --terms is complete, while that of ∧ ∨--terms (i.e., those in conjunctive form) can be decided in polynomial time in dimensions d ≥ 2. The decidability of the infinite-dimensional case being still open, we proceed to investigate the case of indefinite finite dimensions. Here, weak satisfiability still belongs to NP R and strong satisfiability is still hard; the latter, in fact, turns out as polynomial-time equivalent to the feasibility of noncommutative integer polynomial equations over matrix rings.
Ever since entanglement was identified as a computational and cryptographic resource, researchers have sought efficient ways to tell whether a given density matrix represents an unentangled, or separable, state. This paper gives the first systematic and comprehensive treatment of this (bipartite) quantum separability problem, focusing on its deterministic (as opposed to randomized) computational complexity. First, I review the one-sided tests for separability, paying particular attention to the semidefinite programming methods. Then, I discuss various ways of formulating the quantum separability problem, from exact to approximate formulations, the latter of which are the paper’s main focus. I then give a thorough treatment of the problem’s relationship with NP, NP-completeness, and co-NP. I also discuss extensions of Gurvits ’ NP-hardness result to strong NP-hardness of certain related problems. A major open question is whether the NP-contained formulation (QSEP) of the quantum separability problem is Karp-NP-complete; QSEP may be the first natural example of a problem that is Turing-NP-complete but not Karp-NP-complete. Finally, I survey all the proposed (deterministic) algorithms for the quantum separability problem, including the bounded search for symmetric extensions (via semidefinite programming), based on the recent quantum de Finetti theorem [1, 2, 3]; and the entanglement-witness search (via interior-point algorithms and global optimization) [4, 5]. These two algorithms have the lowest complexity, with the latter being the best under advice of asymptotically optimal point-coverings of the sphere.
Ever since entanglement was identified as a computational and cryptographic resource, researchers have sought efficient ways to tell whether a given density matrix represents an unentangled, or separable, state. This paper gives the first systematic and comprehensive treatment of this (bipartite) quantum separability problem, focusing on its deterministic (as opposed to randomized) computational complexity. First, I review the one-sided tests for separability, paying particular attention to the semidefinite programming methods. Then, I discuss various ways of formulating the quantum separability problem, from exact to approximate formulations, the latter of which are the paper's main focus. I then give a thorough treatment of the problem's relationship with the complexity classes NP, NP-complete, and co-NP. I also discuss extensions of Gurvits' NP-hardness result to strong NP-hardness of certain related problems. A major open question is whether the NP-contained formulation (QSEP) of the quantum separability problem is Karp-NP-complete; QSEP may be the first natural example of a problem that is Turing-NP-complete but not Karp-NP-complete. Finally, I survey all the proposed (deterministic) algorithms for the quantum separability problem, including the bounded search for symmetric extensions (via semidefinite programming), based on the recent quantum de Finetti theorem; and the entanglement-witness search (via interior-point algorithms and global optimization). These two algorithms have the lowest complexity, with the latter being the best under advice of asymptotically optimal point-coverings of the sphere.
Ever since entanglement was identified as a computational and cryptographic resource, researchers have sought efficient ways to tell whether a given density matrix represents an unentangled, or \emph{separable}, state. This paper gives the first systematic and comprehensive treatment of this (bipartite) quantum separability problem, focusing on its deterministic (as opposed to randomized) computational complexity. First, I review the one-sided tests for separability, paying particular attention to the semidefinite programming methods. Then, I discuss various ways of formulating the quantum separability problem, from exact to approximate formulations, the latter of which are the paper's main focus. I then give a thorough treatment of the problem's relationship with NP, NP-completeness, and co-NP. I also discuss extensions of Gurvits' NP-hardness result to strong NP-hardness of certain related problems. A major open question is whether the NP-contained formulation (QSEP) of the quantum separability problem is Karp-NP-complete; QSEP may be the first natural example of a problem that is Turing-NP-complete but not Karp-NP-complete. Finally, I survey all the proposed (deterministic) algorithms for the quantum separability problem, including the bounded search for symmetric extensions (via semidefinite programming), based on the recent quantum de Finetti theorem \cite{DPS02,DPS04,qphCKMR06}; and the entanglement-witness search (via interior-point algorithms and global optimization) \cite{ITCE04,IT06}. These two algorithms have the lowest complexity, with the latter being the best under advice of asymptotically optimal point-coverings of the sphere.
In this work, we study the computational complexity of quantum determinants, a q-deformation of matrix permanents: Given a complex number q on the unit circle in the complex plane and an n×n matrix X, the q-permanent of X is defined as Perq(X)=∑σ∈Snqℓ(σ)X1,σ(1)…Xn,σ(n), where ℓ(σ) is the inversion number of permutation σ in the symmetric group Sn on n elements. The function family generalizes determinant and permanent, which correspond to the cases q=−1 and q=1 respectively. For worst-case hardness, by Liouville's approximation theorem and facts from algebraic number theory, we show that for primitive m-th root of unity q for odd prime power m=pk, exactly computing q-permanent is ModpP-hard. This implies that an efficient algorithm for computing q-permanent results in a collapse of the polynomial hierarchy. Next, we show that computing q-permanent can be achieved using an oracle that approximates to within a polynomial multiplicative error and a membership oracle for a finite set of algebraic integers. From this, an efficient approximation algorithm would also imply a collapse of the polynomial hierarchy. By random self-reducibility, computing q-permanent remains to be hard for a wide range of distributions satisfying a property called the strong autocorrelation property. Specifically, this is proved via a reduction from 1-permanent to q-permanent for O(1/n2) points z on the unit circle. Since the family of permanent functions shares common algebraic structure, various techniques developed for the hardness of permanent can be generalized to q-permanents.