arXiv:1310.7766

A Constructive Quantum Lovász Local Lemma for Commuting Projectors

Itai Arad, Or Sattath

Published Oct 29, 2013• 6 citations

Abstract

The Quantum Satisfiability problem generalizes the Boolean satisfiability problem to the quantum setting by replacing classical clauses with local projectors. The Quantum Lovász Local Lemma gives a sufficient condition for a Quantum Satisfiability problem to be satisfiable [AKS12], by generalizing the classical Lovász Local Lemma. The next natural question that arises is: can a satisfying quantum state be efficiently found, when these conditions hold? In this work we present such an algorithm, with the additional requirement that all the projectors commute. The proof follows the information theoretic proof given by Moser's breakthrough result in the classical setting [Mos09]. Similar results were independently published in [CS11,CSV13].

DOI: 10.48550/arxiv.1310.7766

Related papers

A constructive quantum Lovasz local lemma for commuting projectors

Or Sattath, Itai Arad

The Quantum Satisfiability problem generalizes the Boolean satisfiability problem to the quantum setting by replacing classical clauses with local projectors. The Quantum Lov\'asz Local Lemma gives a sufficient condition for a Quantum Satisfiability problem to be satisfiable~\cite{ambainis2012quantum}, by generalizing the classical Lov\'asz Local Lemma. The next natural question that arises is: can a satisfying quantum state be \emph{efficiently} found, when these conditions hold? In this work we present such an algorithm, with the additional requirement that all the projectors commute. The proof follows the information theoretic proof given by Moser's breakthrough result in the classical setting~\cite{moser2009constructiveSTOC}. Similar results were independently published in~\cite{cubitt2011constructive, cubitt2013quantum}.

Quantum Information and ComputationSep 1, 20156 citations

A constructive quantum Lovász local lemma for commuting projectors

SattathOr, AradItai

Quantum Information and ComputationSep 1, 20150 citations

An Information-Theoretic Proof of the Constructive Commutative Quantum Lovász Local Lemma

Martin Schwarz, Toby S. Cubitt, Frank Verstraete

The Quantum Lovász Local Lemma (QLLL) [AKS12] establishes non-constructively that any quantum system constrained by a local Hamiltonian has a zero-energy ground state, if the local Hamiltonian terms overlap only in a certain restricted way. In this paper, we present an efficient quantum algorithm to prepare this ground state for the special case of commuting projector terms. The related classical problem has been open for more than 34 years. Our algorithm follows the breakthrough ideas of Moser's [Moser09] classical algorithm and lifts his information theoretic argument to the quantum setting. A similar result has been independently published by Arad and Sattath [AS13] recently.

arXiv:1311.6474Nov 25, 20137 citations

A constructive commutative quantum Lovasz Local Lemma, and beyond

Toby S. Cubitt, Martin Schwarz

The recently proven Quantum Lovasz Local Lemma generalises the well-known Lovasz Local Lemma. It states that, if a collection of subspace constraints are "weakly dependent", there necessarily exists a state satisfying all constraints. It implies e.g. that certain instances of the kQSAT quantum satisfiability problem are necessarily satisfiable, or that many-body systems with "not too many" interactions are always frustration-free. However, the QLLL only asserts existence; it says nothing about how to find the state. Inspired by Moser's breakthrough classical results, we present a constructive version of the QLLL in the setting of commuting constraints, proving that a simple quantum algorithm converges efficiently to the required state. In fact, we provide two different proofs, one using a novel quantum coupling argument, the other a more explicit combinatorial analysis. Both proofs are independent of the QLLL. So these results also provide independent, constructive proofs of the commutative QLLL itself, but strengthen it significantly by giving an efficient algorithm for finding the state whose existence is asserted by the QLLL. We give an application of the constructive commutative QLLL to convergence of CP maps. We also extend these results to the non-commutative setting. However, our proof of the general constructive QLLL relies on a conjecture which we are only able to prove in special cases.

arXiv:1112.1413Dec 6, 20117 citations

On Preparing Ground States of Gapped Hamiltonians: An Efficient Quantum Lovász Local Lemma

András Gilyén, Or Sattath

A frustration-free local Hamiltonian has the property that its ground state minimises the energy of all local terms simultaneously. In general, even deciding whether a Hamiltonian is frustration-free is a hard task, as it is closely related to the QMA1-complete quantum satisfiability problem (QSAT) - the quantum analogue of SAT, which is the archetypal NP-complete problem in classical computer science. This connection shows that the frustration-free property is not only relevant to physics but also to computer science. The Quantum Lovasz Local Lemma (QLLL) provides a sufficient condition for frustration-freeness. Is there an efficient way to prepare a frustration-free state under the conditions of the QLLL? Previous results showed that the answer is positive if all local terms commute. These works were based on Moser's “compression argument” which was the original analysis technique of the celebrated resampling algorithm. We generalise and simplify the “compression argument”, so that it provides a simplified version of the previous quantum results, and improves on some classical results as well. More importantly, we improve on the previous constructive results by designing an algorithm that works efficiently for non-commuting terms as well, assuming that the system is “uniformly” gapped, by which we mean that the system and all its subsystems have an inverse polynomial energy gap. Similarly to the previous results, our algorithm has the charming feature that it uses only local measurement operations corresponding to the local Hamiltonian terms.

arXiv:1611.08571Annual Symposium on Foundations of Computer ScienceOct 1, 201712 citations

A quantum Lovász local lemma

Andris Ambainis, Julia Kempe, Or Sattath

The Lovász Local Lemma (LLL) is a powerful tool in probability theory to show the existence of combinatorial objects meeting a prescribed collection of “weakly dependent” criteria. We show that the LLL extends to a much more general geometric setting, where events are replaced with subspaces and probability is replaced with relative dimension, which allows to lower bound the dimension of the intersection of vector spaces under certain independence conditions. Our result immediately applies to the k - qsat problem (quantum analog of k - sat ): For instance we show that any collection of rank-1 projectors, with the property that each qubit appears in at most 2 k /( e ċ k ) of them, has a joint satisfiable state. We then apply our results to the recently studied model of random k - qsat . Recent works have shown that the satisfiable region extends up to a density of 1 in the large k limit, where the density is the ratio of projectors to qubits. Using a hybrid approach building on work by Laumann et al. [2009, 2010] we greatly extend the known satisfiable region for random k - qsat to a density of Ω(2 k / k 2 ). Since our tool allows us to show the existence of joint satisfying states without the need to construct them, we are able to penetrate into regions where the satisfying states are conjectured to be entangled, avoiding the need to construct them, which has limited previous approaches to product states.

arXiv:0911.1696Journal of the ACMOct 1, 201222 citations