{'fraction_non_alphanumeric': 0.042931200219719856, 'fraction_numerical': 0.012136088986542158, 'mean_word_length': 4.1655435360879585, 'pattern_counts': {'":': 1, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On preparing ground states of gapped Hamiltonians: An efficient Quantum Lov\'asz Local Lemma

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 Lov\'asz Local Lemma (QLLL) provides a sufficient condition for frustration-freeness. A natural question is whether there is 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. In this work 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. Also, our analysis works under the most general condition for the QLLL, known as Shearer's bound. Similarly to the previous results, our algorithm has the charming feature that it uses only local measurement operations corresponding to the local Hamiltonian terms.


Introduction
Frustration-free Hamiltonians and quantum satisfiability. Most physical systems and models are described by a local Hamiltonian H = i H i where each k-local term H i acts nontrivially only on at most k of its subsystems. Such a Hamiltonian is called frustration-free if its ground state is also the ground state of each of the local terms H i . Frustration-free Hamiltonians appear in various areas, for example: quantum error correcting codes [18], parent Hamitlonians for PEPS (a 2-D generalisation of matrix-product-states) [33], and various models in many-body quantum physics.
An equivalent way to ask whether a Hamiltonian H is frustration-free is whether H = The Classical and Quantum Lovász Local Lemma. We would like to understand the QSAT problem, so it is natural to first look at the classical SAT and the techniques that were useful in studying it. A "local" version of SAT is called k-SAT which asks whether a Boolean formula of the following form can be satisfied: i∈[m] C i , where each C i is a clause containing the or ( ) function of k Boolean variables or their negation. A natural question is, when can we be sure that a satisfying assignment exists? Since each k-SAT constraint excludes a p = 2 −k fraction of assignments, pm < 1 is a sufficient condition (by the union bound). If we have the additional information that none of the constraints share variables, then it is clearly satisfiable. What can we say in the intermediate regime, where each constraint shares variables with at most d constraints (including itself)? The (symmetric) Lovász Local Lemma [3,13,40], applied to this setting, implies that pde ≤ 1 is a sufficient condition for satisfiability. Shearer generalised the Lovász Local Lemma and showed the weakest possible sufficient condition in this framework [38].
How hard is it to find such a satisfying assignment? A series of works [6,26,31,32] have culminated in an efficient constructive algorithm, even under Shearer's condition.
It is natural to ask the analogous questions in the quantum setting, where the Boolean variables are replaced by qubits and the clauses by rank-1 k-local projectors. The resemblance between k-SAT clauses and rank-1 projector is the following: a k-SAT clause excludes one out of the 2 k possible configurations of the relevant variables, whereas a rank-1 k-local projector excludes one dimension out of the 2 k relevant dimensions. In the quantum setting it makes sense to generalise and consider rank-r projectors. So given a set of k-local rank-r projectors acting on n qubits, under what conditions can we guarantee that the system is frustration-free? A "dimension-counting" argument can be used to show that the Lovász condition (2 −k rde ≤ 1) [4] is indeed sufficient, as is Shearer's condition [35].
Is there an algorithm which efficiently prepares a ground state under these conditions? In the past, such constructions have been achieved only for commuting Hamiltonians, i.e. [Π i , Π j ] = 0 for all i, j. Commuting Hamiltonians are somewhat "half-way" between classical and quantum. For example, the commuting 2-local Hamiltonian problem is in (the purely classical class) NP for qudits of all dimensions [9], whereas 2-local QSAT is QMA 1 -Complete if the dimension of the qudits is large enough [2]. Yet commuting Hamiltonians, such as the toric code, can have the striking quantum property of topological order [25]. Also, the commuting existential QLLL is a direct corollary of the (classical) existential LLL.
The analysis of the previous algorithms [34,36], that worked only in the commuting case, used a compression argument, while requiring the symmetric Lovász condition. There was another attempt [12] to prove a stronger version inspired by the classical "backward-looking" analysis of Moser and Tardos [26,32]. However, as noted on the arXiv [12], there is an unresolved gap in the proof of the main result, due to an issue of non-commutativity of subsequent resamplings. (The resampling operation is to replace some (qu)bits with uniformly random (qu)bits.) In fact, on the classical side, Kolmogorov [27] argued that this kind of "backwardlooking" analysis requires a sort of commutation property for resamplings, which, as we show in Appendix E, fails in general for the quantum case, even when the projectors commute.
Recently Harvey and Vondrák [19] introduced a classical "forward-looking" analysis technique which gives slightly worse bounds on the expected number of resamplings, but works in a more general framework and requires only Shearer's condition. This framework is quite flexible and allowed us to transform the results to the quantum setting as well as addressing the non-commuting case.
The gap constraint. The gap of a Hamiltonian -the energy difference between its (distinct) lowest energy levels -denoted ∆(H), plays an important role both in physics and computer science, particularly in Hamiltonian complexity theory, see, e.g., [1,11,14,21]. Suppose H = i∈[m] Π i , then we call the uniform gap of H: (For H = 0 we define ∆(H ) = ∞.)

γ(H) := min
This notion of uniform gap plays an important role in another recent state preparation algorithm [17]. The running time of our algorithm has inverse quadratic dependence on the uniform gap.
Our contribution. In this work we prove a constructive Quantum Lovász Local Lemma for non-commuting projectors. We will only consider systems of n qubits, but all the results generalise trivially to qudits. Our improvements are due to two main new ingredients. The first ingredient is the adaptation of the "forward-looking" analysis technique [19] to the quantum setting. This analysis technique enables us to go beyond the symmetric Lovász condition, and prove efficiency under Shearer's (weaker) condition. Technically, for this to work, we need to bound not only the probabilities of some bad events, but show that the quantum state is bounded above by a uniformly mixed state in the satisfying subspace (see Definition 24,and Lemma 27).
The second technique is the use of weak measurements coupled with a quantum Zeno effect. We consider this to be the main contribution, and devote the next two subsections to explain its purpose and behaviour in our context.
In the next arXiv version of this manuscript, we will also present an alternative algorithm for the non-commuting case working under the symmetric Lovász condition. The analysis of that algorithm is somewhat simpler and also gives improved bounds on the running time, as it is based on the entropy compression argument of [34,36].
Loop invariant. The classical analysis techniques we mentioned differ in how they prove bounds on the runtime of the constructive algorithms. However the basic idea for proving correctness is the same for the corresponding algorithms. The initial state is a uniformly random state. The algorithm starts without knowing which constraints are satisfied, and its goal is to enlarge that list of satisfied constraints. It checks whether a constraint is satisfied: if it is satisfied, it is added to the list. Otherwise, it uses a recovery procedure: it resamples all the variables involved in that constraint, and removes all the constraints from the list that may have been affected by the resampling. The algorithm terminates when the list is complete, and thus a satisfying assignment is found.
This correctness proof works in the classical case and carries through for the commuting quantum case, but fails in the non-commuting case. The main problem is with the loop invariant: if a set of constraints S was satisfied, and then another constraint projector Π f was checked (i.e., measured) and found to be satisfied, the post-measurement state does not necessarily satisfy all the constraints in S (to be more specific, the constraints in S that share qubits with Π f ), because of the collapse caused by the measurement.
Weak measurements. We get around the difficulty of maintaining the loop invariant by using a kind of weak measurement and the quantum Zeno effect. This approach is somewhat similar to the ideas described in [10]. Instead of measuring whether Π f is satisfied, we repeat the following many times: we perform a weak measurement (as explained below) to find whether Π f is satisfied. If it is not, we just apply the usual resampling step. If it is satisfied, we (strongly) measure whether all constraints in S are simultaneously satisfied. If they are not then we abort, and repeat otherwise. When the loop ends, we measure whether S ∪ {Π f } is simultaneously satisfied, and abort if they are not.
By tuning the weak measurement parameter and the number of repetitions, we can control and reduce the probability of aborting in this procedure. Therefore, the two probable outcomes are that we either end up with adding Π f to the set of satisfied clauses, or we use the same recovery procedure, that worked in previous cases, and still works in the non-commuting case.
One may wonder: if the probability of abort is kept small, are these measurements really necessary? Yes -similar to the "hot pot never boils" phenomenon, and the quantum Zeno effect, even though the outcome of the measurement is known with very high probability in advance, the measurement changes the overall state dramatically when applied frequently.
Now we explain what we mean by a weak measurement, and how it can be combined with the quantum Zeno effect. Consider the two-outcome measurement {Π f , Id − Π f }. We can implement a weak measurement on |ψ with intensity parameter θ using an ancilla qubit and a Π f -controlled rotation We simply apply Π θ f on |ψ ⊗ |0 and do a projective measurement on the ancilla qubit. Let us denote by |ψ 1 = √ θΠ f |ψ the (unnormalised) state corresponding to outcome 1. So |ψ 1 ∝ Π f |ψ just as we expect from a projective (strong) measurement. Similarly let Suppose |ψ = Π V |ψ for some other orthogonal projector Π V . The probability of measuring 0 on the ancilla qubit and finding the state outside the support of Π V has probability On the other hand we can argue, that conditioned on never seeing a 1 outcome, ∼ 1/θ repetitions of the weak and strong measurements dissipate the overlap of |ψ with Π f almost completely, while leaving the part lying in im (Π V ) ∩ ker (Π f ) undisturbed. Observe that the overall probability of error, i.e., moving out of the support of Π V , is at most ∼ θ. Analogously to the quantum Zeno effect, setting θ small enough we can go below any desired error probability. This argument lies at the heart of the proof.
In some sense our error bound is even stronger than in the usual quantum Zeno effect: the probability of moving out of the support of Π V is proportional to Π f |ψ 2 , so the smaller the overlap with Π f gets, the smaller the error probability becomes. Because of this we can show that the overall probability of this error is bounded by θ independent of the number of repetitions.
The algorithm. The above argument shows that by using weak enough measurements in the following algorithm, we can ensure a high probability of termination with "SUCCESS" if we can bound the number of repetitions of the main while loop. This bound is obtained by using the techniques of [19]. The following algorithm maintains a list of already checked projectors C. We denote by Π C the orthogonal projection having kernel equal to the intersection of the kernels of all the projectors in C. (Note that C and thus Π C changes during the algorithm.) Algorithm 1 High-level description of the main algorithm 1: input constraints {Π f } f ∈F 2: set all qubits to the maximally mixed state, and mark all constraints as unchecked. 3: while there is a Π f which is unchecked do 4: repeat T times do 5: measure Π f weakly 6: if the measurement found Π f violated then 7: resample all qubits of Π f , i.e., replace them by uniformly random qubits 8: mark all constraints Π f that share qubits with Π f as unchecked 9: go back to the beginning of the main while loop 10: end if 11: measure Π C if it is violated then terminate with "ERR: MEASURE WEAKER" 12: end repeat 13: mark Π f as checked 14: measure Π C if it is violated then terminate with "ERR: USE LARGER T" 15: end while 16: terminate with "SUCCESS" We develop an approximate version of the above algorithm which overcomes the need for using non-local operators Π C . The only quantum operations that our approximate algorithm uses are (weak and strong) measurements of the projectors and resampling of qubits. As we show in Corollary 47, under the symmetric Lovász condition, the runtime of our quantum algorithm isÕ m 3 ·n 2 γ 2 · ln 1 δ · ln 1 , 2 where n is the number of qubits, m is the number of projectors, γ is the uniform gap (see (1)), δ is the desired maximum trace distance from a density operator which is supported on the ground space, and is the desired upper bound on the probability of termination with "ERROR". The exact formula for the runtime bound we prove in the general Shearer case is more complicated, but it is easy to compare to the classical case. Let R c be the upper bound of [26] on the expected number of resamplings of the classical Moser-Tardos algorithm. Then, our quantum algorithm has runtimeÕ R 2 c n 2 m 2 γ 2 log 1 δ · log 1 , see Corollary 46.
New existential proof Our work does not require any of the previous existential proofs, and therefore provides an alternative proof for the results in [4] and [35], see Corrolary 32.
Structure of the paper In Section 2 we list the most important definitions and the notations that we use throughout the paper.
In Section 3 we describe our generalisation of the projective measurement step from the commuting [34,36] to the non-commuting case in terms of quantum channels. In 3.1 we describe our loop-invariants which define progress in terms of subspaces. In 3.1.1 we define our ideal quantum channel introduced for the non-commuting case. Since we cannot implement this ideal operation efficiently we describe more realistic requirements for a progressive quantum channel 3.1.2 which are sufficient for the "forward-looking" analysis technique to work. In 3.2 we prove the key Lemma for progressive quantum channels and in 3.3 we use the key Lemma to prove that the resampling algorithm (Alg. 2) works efficiently under Shearer's condition. In 3.4 we draw the conclusions for various scenarios, while in 3.5 we compare the results with classical algorithms.
In Section 4 we show how to efficiently implement a progressive quantum channel using only weak and strong measurements, and how to implement approximate versions of the required measurement operators. Finally we put all pieces together to prove the main theorem on the runtime of our quantum algorithm, while in Section 5 we consider a possible generalisation.

Definitions and notation
In this work, for simplicity, we focus on the case of 2-level systems (qubits), but all the results in this work apply equally well for d-level systems (qudits). Also, in order to maintain convenient formulation, pure states such as |ψ and mixed states such as ρ will not necessarily be normalised. For the rest of the paper we are going to refer to the generalised "quantum clauses", i.e., our projectors and their image, as flaws that we want to avoid.
Definition 2 (Flaws as local projectors and the assigned probabilities) Let F be a set of (labels of ) flaws and for each f ∈ F let Π f be an orthogonal projector on n qubits representing a {0, 1}valued binary measurement operator which indicates presence of flaw f with measurement outcome 1. Later we also use labels {G, B} for the measurement outcomes corresponding to "Good" (i.e., 0) and "Bad" (i.e., 1) outcomes respectively.
For all f ∈ F there is a given subset of the qubits b(f ) ⊆ [n], such that the projector Π f acts trivially on [n] \ b(f ). For S ⊆ F we extend this notation by defining b(S) : Let Π loc f denote Π f restricted to b(f ), so that we can write Π f = Π loc f ⊗ Id [n]\b(f ) . Let p f = Tr(Π f )/2 n = Tr(Π loc f )/2 |b(f )| , and for S ⊆ F let p S = f ∈S p f . Note that p f is the probability of measurement outcome 1 for Π f on a maximally mixed state. Definition 4 (Independent set polynomial) Consider a vector of numbers (x f ) f ∈F . For every I ∈ Ind(F ) we define the polynomial q I in the variables (x f ) as follows: Let e = 2.718 . . . denote the base of the natural logarithm in the following definition: Evaluating the Independent set polynomial is # P-hard [23]. Nevertheless, due to the importance of the condition (SHC) to repulsive lattice gas models in many-body physics [37], it is well understood for many lattices [5,15,16,22,41]. The existential proof showing that the condition (SHC) implies frustration-freeness has been used to prove frustration-freeness of QSAT instances with various lattice topologies, and to derive new numerical lower-bounds on the SAT/UNSAT transition of quantum satisfiability on random Erdős-Rényi models [35].
Proof. Let d be as in (SLC) and let x f = 1/d for all f ∈ F , then (GLC) holds: It is well known in the literature of the classical Lovász Local Lemma, that (SHC) is a weaker condition than (GLC) or (CEC). For direct proofs of these implications see, e.g., [ Definition 9 (Sign function) For x ∈ R let us denote the sign function by For a diagonal matrix Σ we define sgn (Σ) element-wise.
Definition 10 (Quantum-classical states) For the description of quantum-classical states consisting of an N dimensional quantum system and a k dimensional classical system we are going to use elements of C N ×N ⊗ R k . We can interpret these as quantum states of restricted form via defining an embedding of R k to C k×k using diagonal matrices.
Definition 11 (Trace norm and distance) The trace norm of a matrix is the sum of its singular values: For elements of C N ×N ⊗ R k we define the trace norm via the embedding of Definition 10.
Definition 12 (Approximate quantum channels) Let Q,Q be quantum channels between the spaces : 3 The algorithm and the key lemma for the analysis The following algorithm is inspired by the classical MaximalSetResample algorithm from Harvey and Vondrák [19]. To adapt the algorithm to the quantum setting we introduce a quantum channel Q C f , which performs some quantum operation on the n-qubit quantum register determined by the classical input (C, f ), where C is the set of already "checked" flaws, and f is the next flaw to address. In the case of commuting projectors Q C f will be simply the application of a projective measurement (Π f , Id − Π f ) where the measurement outcomes are labelled with (B, G) standing for ("Bad","Good") respectively.

Algorithm 2 Maximal independent set resampling algorithm
1: set C ← ∅ ( C ⊆ F is going to store the checked flaws which were found "good" ) 2: start with the maximally mixed state ρ 0 = Id/2 n 3: while C = F do 4: set I ← ∅ ( I ⊆ F is going to store the flaws resampled in this round ) 5: while C ∪ Γ + (I) = F do 6: pick the minimal f ∈ F \ (C ∪ Γ + (I)) according to some fixed ordering (≤, F ) 7: if outcome label is E then terminate with "ERROR" 9: Definition 13 For f ∈ F the resampling operation on ρ in line 13 can be formally described Definition 14 Lines 3-16 will be called a round. Due to the selection rule of f in line 6, I will always be an independent set. We will denote the independent set at the end of the i-th round by I i .

Required properties of the quantum channel Q
In this subsection we define some properties of Q under which we can analyse Algorithm 2 nicely. Later we show that Algorithm 3 satisfies these requirements.
In order to prove that Algorithm 2 converges to a good quantum state, we would like Q not to disturb the "good" part of the quantum state, but efficiently project out its "bad" part. When Q fails to project out the "bad" part, it should transform the "bad" part of the state to the image of the failed projector, for reasons that will be explained later.
We define progress in terms of "good" subspaces, because we want to ensure that the flaws that are marked as checked (denoted by C ⊆ F ) are indeed satisfied. We hope for an algorithm that works for low-energy subspaces as well, not just for zero-energy ones, and the high-level analysis works in this case as well -see Appendix G. This is why we define the somewhat abstract concept of a subspace progress measure. However, we will be mostly concerned about zero-energy subspaces, and thus use the exact progress measure as defined below.
We will mostly be concerned with the following natural subspace progress measure, aiming at frustration-free states. In the following definition V F is the kernel of H, the subspace to which we would like to gradually converge.
When we are only concerned with termination of Algorithm 2 we will consider the following trivial subspace progress measure:

The exact quantum channel -ideal non-commuting generalisation
Now we introduce our generalisation of the measurement procedure for the non-commuting setting. We argue that this is probably the most faithful generalisation of the commuting algorithm for the non-commuting case. The proposed quantum operation applies a measurement conditionally followed by a unitary operation. The combined procedure both respects the loopinvariant of the exact progress measure, and handles new flaws in a way which seems essential for the resampling algorithm. (In the following definition we use notation V C = f ∈C ker(Π f ) corresponding to the exact progress measure.)

Definition 18
We define the exact quantum channel, denoted here by Q, in the following way: conditional on receiving classical information C ⊆ F and f ∈ F , the quantum channel If the outcome is Π V C∪{f } it labels its output with G standing for "Good". If the outcome is Id − Π V C∪{f } it labels its output with B standing for "Bad", then it applies the unitary operation For the output state corresponding to pure input state |ψ we use notation

Remark 19
In the above definition we have some ambiguity about the map W U † , since the singular value decomposition is not unique. However one can show that the map W sgn (Σ) U † is well defined (see Appendix B), and this is enough in our case, since we are always acting on input states that lie in But then the action of W U † only depend on W sgn (Σ) U † , as we can show using (7) from the next Proposition: To justify our generalisation and explain better its main purpose we show that this quantum channel preserves two important properties of the commuting quantum case. Before we prove the corresponding Lemma 21, we need some identities of the relevant subspaces. In the following we use concise rank arguments, but the reader may get more insight on the structure of the examined subspaces by looking at Jordan's Theorem in Appendix D.
Proposition 20 Let us fix some f ∈ F and C ⊆ F . Let us use notation , then the following identities hold: Here, the second equality is justified by rank(A) = rank A † , and the third equality by The proof follows form the following line of (in)equalities which we justify below: , implying the first equality. The penultimate equality is due to Π f Π V f = Π V f Π f , which follows from the fact that these operators act on disjoint qubits. Finally note that Using the above proposition we can easily show in the following lemma that the properties of our interest hold. However one might be puzzled why is it important to transform states to the "Bad" image of Π f . The reason is that it ensures that the resampling operation uniformly mixes quantum states, for more details see the proof of Lemma 27; Appendix F presents a simple example showing how things can go wrong when this transformation step is skipped.
Lemma 21 Suppose |ψ respects the exact progress measure with respect to checked flaws C ⊆ F , i.e., |ψ = Π V C |ψ . If we apply the exact quantum channel Q C f on |ψ , then Using (7) we can see (9).
For completeness we show that Definition 18 is indeed a generalisation of the commuting case.

Proposition 22
Suppose that all local projectors commute, and that the input state |ψ is such that |ψ = Π V C |ψ , then the output of the exact quantum channel Q C f coincides with the output of the projective measurement ( Proof. Since all local projectors commute we have

Remark 23
The properties proven in Lemma 21 enable one to use the exact quantum channel of Definition 18 in the non-commuting setting together with the compression argument of [34,36] to show that, under the condition (SLC), the algorithms in [34,36] find a ground state quickly.
For now we do not continue in the direction of Remark 23 for two reasons. The first reason is, that we do not know how to prove efficiency up Shearer's bound (SHC) using a compression argument. The second reason is that we cannot implement the exact quantum channel efficiently. In Section 4 we show how to efficiently implement a closely related quantum channel. That quantum channel fits the proof techniques of the "forward-looking" analysis, however, it has the drawback that even if the input is a pure quantum sate its outputs can in general only be described by a probabilistic mixture of pure states. Although this feature can also be handled using the entropy compression argument of [34], it requires some additional analysis of the procedure. The main advantage of using the compression argument is, that it improves the runtime bound in the (SLC) case, therefore we plan to work out the details in the next arXiv version of this paper.

Progressive quantum channels -an efficient non-commuting version
Because of the probabilistic mixtures appearing we can no longer work with the convenient pure state formalism, so from now on, we will use density operators instead. The following definition formulates the requirements of the "forward-looking" analysis technique in terms of density operators. The most important criterion is that if the input is a (mixed) quantum state ρ, which is supported on some subspace respecting the loop-invariant and is upper bounded by a uniform mixture, then the output state should also lie in a nice subspace and should also be upper bounded by a corresponding uniform mixture. Since we can only implement approximate versions of our channels, there is some other criterion concerning error probabilities.

Definition 24
We say that Q is a progressive quantum channel with respect to the subspace progress measure {V C : C ⊆ F } with error parameter θ ∈ [0, 1] if the following holds: Conditional on receiving classical information C ⊆ F and f ∈ F , the quantum channel Q C f performs the quantum operation Q C f : C N ×N → C N ×N ⊗ R 3 , satisfying the following properties: (In the following definition think about Π V as an unnormalised quantum state representing uniform distribution on V .) (i) The quantum channel labels its output with the classical labels (G, B, E) corresponding to ("Good","Bad","Error") outcomes, so that for input ρ the output state is written as: (ii) For a uniformly mixed input state on Π V C , the output state labelled as "Good" is upper bounded by a uniform mixture on the better subspace Π V C∪{f } : (iii) For a uniformly mixed input state on Π V C , the output state labelled as "Bad" is upper bounded by a uniform mixture on a subspace of tensor product form: (iv) For ρ supported on V C (i.e., ρ = Π V C ρΠ V C ), this has small "Error": At this point the requirement Tr Q C f,E (ρ) ≤ 2θ · Tr Q C f,B (ρ) may feel weird, in fact it would be enough to require Tr Q C f,E (ρ) ≤ 2θ · Tr Q C f (ρ) , but our channels happen to satisfy the stronger condition, which results in slightly better runtime bounds. The scaling of the error parameter θ by 2 is somewhat arbitrary, but it fits nicely with the analysis of Algorithm 3.

Proposition 25
The exact quantum channel is a progressive quantum channel with respect to the exact progress measure with error parameter θ = 0.
This proposition is a direct corollary of Lemma 21, and it shows that progressive quantum channels are indeed generalisations of the ideal exact channel we described before.

The key lemma for the high-level analysis
In this subsection we prove the key lemma. To do so we need to define some more concepts. Note that there are logs that the algorithm can never encounter. For example, a log may contain only one E, and it should be the last letter, since Algorithm 2 immediately terminates after measurement outcome E. Also we cannot see |F | + 1 consecutive "G" because seeing |F | "G" in a row would necessarily set C = F , and thus would terminate the algorithm.
Since Algorithm 2 is deterministic apart from the labels obtained via the application of Q, we can completely reconstruct the inner variables C and I of the algorithm for any given log. For L ∈ L let C L and I L denote the inner variables C and I of Algorithm 2 after it has seen and processed the measurement results described by L, i.e., including the changes made to C and I in lines 8-14 of Algorithm 2. Also let ρ L denote the unnormalised quantum state after having seen and processed all measurement results in L, i.e., including the resampling step in line 13 if the last result was "B". Let f , where L f denotes the number of resamplings of f given that we see L ∈ L. Also for X ∈ {G, B, E} let (L, X) ∈ {G, B, E} T +1 be the log obtained by adding X to the end of log L. If the algorithm did not terminate after L, i.e. C L = F , E / ∈ L then let f L denote the next flaw Algorithm 2 will address.
Lemma 27 (Key lemma) If Q is a progressive quantum channel with respect to the subspace progress measure {V C : C ⊆ F } with error parameter θ ∈ [0, 1], then for every L ∈ L \ L E we have Moreover if (L, E) ∈ L, then Proof. We prove (10) and (11)  First we show the inductive step for (L, G): Now we show the inductive step for (L, B): For the proof of (11), first note that (L, E) ∈ L implies that Algorithm 2 does not terminate after seeing L and thus also (L, B) ∈ L. Finally due to property (iv) of Q, we have

Upper bounds by stable set sequences
In Appendix A we present some upper bounds on weighted sums of stable set sequences developed by Harvey and Vondrák [19]. In this subsection we show how to use these bounds for deducing upper bounds on the expected number of resamplings performed by Algorithm 2.

Proposition 29
The sequence of sets of flaws produced by a run of Algorithm 2 is always a stable set sequence. (Note that we ignore the empty set produced by the final round.) Proof. If no resamplings happen in a round, then Algorithm 2 terminates and thus, apart from the final round, I i is non-empty. Let U i = F \ C denote the unchecked flaws at the end of the i-th round. Due to the condition in line 5, U i ⊆ Γ + (I i ). But observe that the flaws that become unchecked by a resampling during the (i + 1)-st round cannot be addressed in this round, again by the condition in line 5. So I i+1 ⊆ U i ⊆ Γ + (I i ) as required.
Proposition 30 For every L ∈ L B we can uniquely determine the stable-set sequence I L ∈ IS that is produced by Algorithm 2 after all measurement results in L were processed. Moreover, this mapping is injective.
Proof. The unique determination of I L follows from the deterministic nature of the classical part of Algorithm 2; the selection rule in line 6 plays a crucial role for establishing determinism. For injectivity note that for L ∈ L B(k) we get I L = k. So it is enough to consider L = L ∈ L B(k) and show that I L and I L differ. Since both L and L are in L B(k) it cannot happen that one is the continuation of the other. Let i + 1 be the first position where they differ. Let L i ∈ L i denote the common part of L and L before the i + 1-st position. Without loss of generality, assume L is a continuation of (L i , B) and L is the continuation of (L i , G). Let us assume that after seeing L i , the algorithm is in its j-th round and let f L i be the next flaw it will address. Then I j (the j-th independent set in I L ) contains f L i , whereas I j (the j-th independent set in I L ) does not contain f L i , so I L and I L are clearly different. Now we have all the tools for proving upper bounds on the expected number of resamplings that Algorithm 2 perform.
Theorem 31 Let Q be a progressive quantum channel with respect to some subspace progress measure {V C : C ⊆ F } with error parameter θ ∈ [0, 1]. Let E[#Resamplings] denote the expected number of resamplings that Algorithm 2 performs while using Q in line 7. If (p f ) f ∈F ∈ (0, 1) |F | satisfies the condition Moreover if Algorithm 2 terminates with "SUCCESS", then the resulting quantum state lies in V F , and the probability of terminating with "ERROR" is less than 2θ · R.

Proof.
For the upper bound on E[#Resamplings] we invoke the results of Harvey and Vondrák [19] as presented in Corollary 51 in our Appendix A, using the following argument: Now we apply Corollary 51 (from Appendix A), using the additional observation that log 1 q∅ = O(n). To see this bound, first note, that since we work with qubits we have p f · 2 |b(f )| ∈ N, and therefore by Definition 4 (q ∅ · 2 n ) ∈ Z. Due to Proposition 6, (SHC) holds, but (SHC) requires q ∅ > 0. This implies q ∅ ≥ 2 −n , and thus log 1 q∅ = O(n). Finally in the case of (SLC) we use the reduction of Proposition 6 to the case (GLC).
The statements about the quantum state at termination and the error probability follow from Lemma (27).
Corollary 32 (Existential Theorem) Suppose the projectors (Π f ) f ∈F satisfy any of our four conditions (SLC)-(SHC). Then the local Hamiltonian H = f ∈F Π f is frustration-free, or in other words f ∈F ker (Π f ) has dimension at least 1.
Proof. Proposition 25 shows that the exact quantum channel constructed in Definition 18 is a zero-error progressive quantum channel with respect to the exact progress measure. Moreover, Theorem 31 shows that if run Algorithm 2 using such a progressive quantum channel, then the resulting algorithm terminates with "SUCCESS" with probability 1 and at termination the quantum state lies in the kernel of H. Therefore, dim(ker(H)) = dim f ∈F ker (Π f ) ≥ 1.
Corollary 32 is almost equivalent to [4, Corollary 1.6] and [35, Theorem 1]; the only difference is, that the previous results provide a non-trivial lower-bound on dim(ker(H)), whereas our results only show that dim(ker(H)) ≥ 1.

Runtime bounds on different versions of the quantum algorithm
Corollary 33 If we run Algorithm 2 with Q C f replaced by projective measurements Π f , then the bounds on the expected number of resamplings from Theorem 31 hold.
Proof. Observe that the projective measurements Π f implement a zero-error (i.e., θ = 0) progressive quantum channel with respect to the trivial progress measure of Definition 17.  12R , and supposeQ is a 1 6(|F |+6R·d) -approximation (Def. 12) of Q. Suppose we run Algorithm 2 while usingQ in line 7, and terminate it with "TIMEOUT" if it attempts to do more than 6R resamplings. This quantum algorithm terminates with "SUCCESS" with probability at least 1/2, while usingQ at most (|F | + 6R · d) times in total. Conditional on termination with "SUCCESS", its output quantum stateρ is 1/2-close in trace distance to a quantum state ρ supported on the ground state space of H.

Proof.
First suppose we use the quantum channel Q in line 7. Theorem 31 states that Algorithm 2 terminates with "ERROR" with probability at most 1/6. Using Markov's inequality we can see, that the probability of termination with "TIMEOUT" has probability at most 1/6 also. Let ρ denote the output state when the algorithm uses Q and let ρ S denote the unnormalised output state corresponding to termination with "SUCCESS", finally let p S = Tr [ρ S ] denote its probability. As we have show p S ≥ 2/3 and Theorem 31 shows that ρ S is supported on the kernel of H.
Let T denote the number of applications of the quantum channelQ. We claim that T ≤ |F | + 6R · d. This can be seen by observing that each timeQ returns with "GOOD", |C| is increased by one, and when it returns with "BAD", i.e., a resampling occurs, |C| decreases by at most d − 1. Since we allow at most 6R resamplings |C| ≥ T − d · 6R, but |F | ≥ |C| proving the claim.
Letρ denote the output state when the algorithm usesQ and letρ S denote the unnormalised output state corresponding to termination with "SUCCESS", finally letp S = Tr [ρ S ] denote its probability.

Comparison with other LLL algorithms
In the classical setting, the expected number of resamplings done by the Moser-Tardos algorithm, under the condition as proven by Moser and Tardos [32].
In all cases our bound for the quantum case in Theorem 31 is worse by a linear factor in the number of qubits. This extra n factor is a side effect of the "forward-looking" analysis technique, and in the next version we will show how it can eliminated in the (SLC) case, using the compression argument. We conjecture that this extra factor can be removed in the other cases as well. We use the above definition for γ throughout this section. The QSAT instances that satisfy any of our four conditions (SLC)-(SHC) are frustration-free as shown by Corollary 32. Since we only consider instances that satisfy some of these conditions, the two definitions for γ (Definition 36 and Eq. (1)) are equivalent for all the Hamiltonians in this work.

Non-commuting weak measurement procedure
The key idea for constructing a progressive quantum channel for non-commuting projectors is using the quantum Zeno effect, and performing several weak measurements of Π f with intensity θ, using the weak measurement operators Note For an intuitive explanation of these operators see the Introduction.
The algorithm below implements a progressive quantum channel using some non-local measurements, and therefore it is not efficient in its present form. Later we show how to implement an approximate version of these non-local operations by using only local measurements in Algorithm 4. The algorithm below can be interpreted as an approximate version of the exact quantum channel (Def. 18), followed by a decoherence channel -see Appendix C. Also it can be understood from a geometric point of view using Jordan's Theorem -see Appendix D, Algorithm 3 M θ Non-commutative measurement for checked flaws C ⊆ F and f ∈ F 1: input quantum state ρ and classical information C ⊆ F , f ∈ F and t ∈ N 2: ( Let us write The following lemma proves that Algorithm 3 implements a progressive quantum channel. We prove slightly stronger properties than required by Definition 24, as it fits the proof better.
Let us fix C ⊆ F , f ∈ F and θ ∈ (0, 1], and use notation Lemma 37 For the input state ρ 0 let us denote the output of Algorithm 3 by M θ (ρ). If t ≥ ln(3/θ) θ·min(γ C∪{f } ,1) , then Algorithm 3 implements a progressive quantum channel with respect to the exact progress measure and with error parameter θ, as the following properties hold: (We only distinguish E1 and E2 for the sake of analysis, but we treat both of them just as E.) Proof. First observe that the output state of Algorithm 3 corresponding to the 4 possible outcome labels can be described as Finally it is easy to see from (14) that M θ B (Π V f ) = 0, but we can also argue by trace preservation using (ii): Claim 38 For all t ∈ N + and θ, σ ∈ (0, 1] the following inequality holds: Proof.
The last inequality holds because: Property (iv): The following inequality is a manifestation of the quantum Zeno effect, and proves an error bound which is proportional to the intensity θ of the measurement.
Now we use (Id − Π V ) · Id · Π V = 0, and subtract this zero operator: (12)) (12), (14)) Due to the assumption ρ = Π V ρΠ V , this result implies Now we start bounding the other type of error arising from doing few iterations (i.e., small t): (19)) To continue we need to bound ( Note that since M θ is a quantum channel, it is trace-preserving: ⇓ sum up the above 4 equalities Equation (25) and (28) show that with the above choice of a, b, c, d, the conditions of Claim 39 hold and so Proof. Note θ ∈ (0, 1], so if a = 0, then d ≤ θ · b trivially holds. Else if a > 0 This completes the proof that properties (i)-(iv) hold.

Approximate kernel projection procedure
Let S ⊆ F , and V = V S = ker(H S ) = f ∈S ker(Π f ). For the implementation of Algorithm 3 we need the non-local measurement operator Π V , but it turns out that for the purposes of the algorithm it is enough to implement a "destructive" version of this measurement operator which we denote byΠ S .
Definition 40 (Destructive non-local measurement channel) For S ⊆ F letΠ S denote the quantum channel which performs the projective measurement on V = V S , followed by a completely depolarising channel conditioned on the V ⊥ outcome, and which labels its outputs with classical labels (P, D) corresponding to ("Projected","Depolarised -was not in V "). Formallỹ Π S : C N ×N → C N ×N ⊗ R 2 , such that for input 0 ρ ∈ C N ×N the output of the channel is We implement an approximate version of the above channel via the following algorithm: Algorithm 4Π S,τ -Non-commutative kernel projection 1: input quantum state ρ 2: repeat τ times do 3: choose f ∈ S uniformly at random 4: measure Π f

5:
if result "flaw f is present" then 6: completely depolarise qubits ( i.e., resample all qubits ) 7: return "D" 8: end repeat 9: return "P " Note that when Algorithm 3 uses this algorithm as a subroutine, it throws away the output if it is labelled by D, since it indicates measurement outcome V ⊥ . Therefore later we can safely ignore the depolarisation step in line 6, as it is added just for the sake of analysis.
In the proof of the following lemma we are going to use a special case of Hölder's inequality: Proof. This is a special case of Hölder's inequality for Schatten p-norms [7, Cor. IV.2.6].
Lemma 42 For S ⊆ F , τ ∈ N and 0 ρ ∈ C N ×N letΠ S,τ (ρ) denote the output state of Algorithm 4. Then its trace distance from the output of the ideal quantum channelΠ S (ρ) can be bounded as follows: Proof. Let us first examine the case τ = 1, with outcome P : Observe, that by definition for all f ∈ S we have ker(Π f ) ⊆ V , thus Π V Π f = 0 and so Also observe that due to the iterative structure of Algorithm 4 we havẽ Combining (30) and (31) using induction yields Now let us turn to the case τ = 1, with outcome D: Combining this inequality with a trace-preservation argument yields From the form of equation (29) we can see that ⇓(by taking the adjoint of both sides) ⇓(by linearity) ⇓(by taking the adjoint and by linearity) Using equation (31) recursively and applying (37) together with (33), results in Claim 43 Proof. For τ = 0 this definitely holds, we proceed by induction. Suppose the statement holds (by the ind. hyp.) Now we are ready to calculate the trace distance betweenΠ S (ρ) and its approximatioñ Π S,τ (ρ). Since (P, D) are classical labels We first handle the outcome P : (recall that we assumed 0 ρ ) (by (32) and (39)) Now we handle the outcome D: (32)) Using (38) we can conclude that Finally, we use that both channels depolarise their output D: Combining the bounds that we got for output cases P and D and using (40) we can conclude that for ρ 0:
Proof. Algorithm 3 with the above parameters implements a progressive quantum channel with respect to the exact progress measure with error parameter θ if we use the destructive non-local measurement channels of Definition 40, as shown by Lemma 37. Also Algorithm 4 implements a β (t+1) -approximation of the destructive non-local measurement channels, as shown by Lemma 42. Since Algorithm 3 uses these channel at most t + 1 times, the triangle inequality shows that the approximate algorithm is β-close to the ideal one using the exact version of the destructive non-local measurement channel. The upper bound on the number of measurements performed can be easily deduced from the loop structure of Algorithm 3 and Algorithm 4. · (log(|F |) + log(R) + log (1/γ)) (weak and strong) measurements. Conditional on termination with "SUCCESS", its output quantum state is 1/2-close in trace distance to a quantum state supported on the ground state space of H.
Corollary 46 Let R be the upper bound on the resamplings in Theorem 31, and let d = max {|Γ + (f )| : f ∈ F }. Then for all δ, ∈ (0, 1], there is a quantum algorithm that uses only local (weak) measurements of the projectors Π f and terminates with success with probability at least 1 − , performing at mostÕ R·|F |·(|F |+R·d) γ 2 · log 1 + |F | γ F · log 1 δ · log 1 measurements in total, where γ is the uniform gap and γ F is the gap of H as in Definition 36. Conditional on termination with "SUCCESS", the output quantum state is δ-close in trace distance to a quantum state supported on the ground space of H.

Proof.
We boost the previous theorem using standard techniques. After performing the algorithm described in Theorem 45 we get result "SUCCESS" with probability 1/2, conditioned on this outcome we run Algorithm 4 with τ = |F | γ F · ln 8 δ . Since the output state was 1/2 close to a ground state, a projective measurement of the kernel of H finds the state in the kernel with probability at least 1/2, so Algorithm 4 finds a flaw with probability at most 1/2. Moreover conditioned on not finding a flaw the state becomes δ-close to a ground state due to Lemma 42 and a straightforward triangle inequality argument. If we repeat the whole procedure 4 · ln 1 times, then the probability of all runs failing is less than .
Corollary 47 For the case of (SLC) the runtime bound of Corollary 46 is Proof. Use that in Theorem 31 in the case of (SLC) we get R = O n·|F | d .

Discussion
In the non-commuting case, it is computationally hard to distinguish between a state which has 0-energy, and a state which has an exponentially small energy. Therefore, it seems unlikely that an efficient algorithm will be able to construct exactly a 0-energy state. The energy levels in the classical and commuting case are integers, and so the energy gap was never an issue in previous works.
The main question that this work leaves open is whether there exists a polynomial time randomized approximation scheme (FPRAS) for this problem: given an energy level find, with a constant probability, a state which is supported on energy levels below , with the runtime scaling polynomially in the input parameters and 1 . Appendix G shows how a simple extension of our framework can be adapted to the FPRAS requirements, and a surprising phenomenon that poses a barrier for showing an FPRAS: Suppose a state |ψ has energy E, for H 1 + H 2 where both terms are positive semi-definite. Now, suppose the energy of the state is measured only with respect to H 1 . It could be that the energy will increase above E, with high probability (even though we subtracted H 2 , and therefore the expected energy cannot increase).

Author Contributions
A.G. is the principal author of this paper. A.G. adapted the ideas of [19] to the commuting quantum setting. O.S. showed that a modified version of the resulting algorithm terminates in the non-commuting case. A.G. generalised the measurement procedure to fit the non-commuting setting and proposed the use of weak measurements and the quantum Zeno effect for efficient implementation, and analysed the resulting algorithms.
where in the last step we used Lemma 48.
The next theorem is an improved version of the above, and uses results of [20] showing that there is a considerable slack naturally appearing.
For ease of notation let us introduce the shorthand q I := q I (p f ).
Theorem 50 If (p f ) f ∈F ∈ (0, 1) |F | satisfies the condition Proof. In the following proof it will be convenient to prove the statements in reversed order: [20,Lemma 5.33]. As shown in [20,Claim 5.23] 1 Let r = ln(1 + ) · t, then applying Theorem 49 completes the proof using the additional observation that ∈ (0, 1] and thus  [20,Corollary 5.38]. Substituting this formula into the (SHC) case gives the required result.
If the vector of probabilities (p f ) f ∈F ∈ (0, 1) |F | satisfies the condition Proof. Choose t = 0 and let T be the number we get from Theorem 50, then ∞ k=1 min   1,

B Ambiguity in singular value decomposition
In this appendix we show that for any square matrix A = W ΣU † the linear map W sgn (Σ) U † is well defined, i.e., it is independent of the choice of unitaries in the singular value decomposition.
, as the following shows:

C Decoherence
In this appendix we illustrate how decoherence arises from our weak measurement procedure (Algorithm 3). We study the ideal limiting case where the weakness parameter of the measurement θ is infinitesimally small, and we do infinitely many repetitions of the weak and strong measurements. Our argument is hand-wavy but can be made precise by taking the appropriate limits.
Let Π f Π V = W ΣU † , σ i = Σ ii , and w i = W .i , u i = U .i be the i-th column of W and U respectively. Let |ψ t denote the unnormalised state after t weak and strong measurements, corresponding to the case when no positive Π f neither negative Π V measurement outcomes were observed, and let |ψ t = j a t j |u j , where a t j is the amplitude of |u j in |ψ t . The argument described in the introduction shows, that |ψ t+1 ≈ Π V |ψ t − θ/2Π V Π f |ψ t . Assuming that For small θ we can move to a continuous time approximation, and use the differential equatioṅ a j ≈ − θ 2 σ 2 j a j , which yields the solution a t j ≈ e − θ 2 σ 2 j t a 0 j . Let ρ t denote the unnormalised density operator corresponding to cases when a positive Π f measurement outcome was observed in the t-th iteration, and therefore Algorithm 3 terminated.
where we defined ρ in ij = u i |ρ in |u j with ρ in = |ψ 0 ψ 0 |. The change of basis u i → w j in ρ in → ρ out corresponds to the unitary map W U † , which we described as the exact quantum channel.
This little calculation also explains, that for infinitesimally small θ the procedure is always successful, and projects out the complete overlap with Π f if repeated indefinitely. Also it is converging exponentially to its infinite version. The strength of the decoherence depends on the difference between the singular values, and does not happen at all if the singular values equal, since then 2σ i σ j σ 2 i +σ 2 j = 1. Note that this phenomenon is only present for non-commuting projectors, since in the commuting case σ i ∈ {0, 1}.

D Jordan's Theorem on two orthogonal projectors
In order to get insight to the interplay between two orthogonal projectors we refer to the work of Camille Jordan [24] from 1875. The structure theorem we invoke also plays an important role in many other results form quantum computation, often in an implicit way, see e.g. [28,39]. A modern treatment of the following theorem together with a proof can be found in [7, Theorem VII.1.8]: Theorem 52 For any two orthogonal projectors Π f , Π V acting on the Hilbert space H there exists an orthogonal decomposition of H into one-dimensional and two-dimensional subspaces that are invariant under both Π f and Π V . Moreover, inside each two-dimensional subspace, Π f and Π V are rank-one projectors (in other words, inside each two-dimensional subspace there are two unit vectors |w i and |u i such that Π f projects on |w i and Π V projects on |u i ), and | w i |u i | / ∈ {0, 1}.
The theorem above gives a lot of insight to our algorithms, and explains why and how the singular values govern the behaviour of Algorithm 3 -compare Appendix C. For example it shows that the unitary operation W U † in Definition 18 basically performs a rotation inside each two-dimensional subspace, while sends |u i to |w i . We can also use this theorem to give a more insightful proof of Proposition 20.
Note that in the commuting case, when Π V and Π f commute, they can be diagonalized simultaneously, implying that all the subspaces are 1 dimensional, and therefore W U † = Id.

E A note on the commutativity of resampling operations
A notion of commutativity plays a crucial role in the analysis of generalised Moser-Tardos algorithms in the unifying work of Kolmogorov [27]. The commutativity of two resampling operations basically refers to the case when resampling two independent flaws in different orders gives the same result. We will now give an example showing that this can fail to hold even if all projectors commute. Thus in this appendix we assume that all projectors commute.
In the quantum setting, an individual resampling operation on flaw f should consist of replacing qubits b(f ) by maximally mixed ones. This step would itself commute if applied on non-adjacent flaws, but this operation may also be followed by doing measurements on adjacent flaws. This measurement step is necessary to actually keep track of which flaws are present. So one step would be M We mention as a curiosity that when we tried disproving equation (42) using Kitaev's toric code [25] interestingly our simulations showed commutation in the resampling operations.

F An example justifying our quantum channel definitions
Throughout this appendix we are going to use • for composition. Also for a projector Π we interpret Π • ρ as ΠρΠ.
In this appendix, we will give a "correct" algorithm, in the sense that it respects the loop invariant, and therefore successfully finds a ground state upon termination. The point of this algorithm is to explain why it is crucial to resample the qubits only after Π f is violated, and not only when the state has been found to have some overlap with Π f (by measuring Π C∩{f } ). if the measurement was violated then 6: resample all qubits of Π f , i.e., replace them by uniformly random qubits 7: mark all constraints in Γ + (Π f ) as unchecked 8: else 9: mark Π f as checked 10: end if 11: end while 12: terminate with "SUCCESS" The induction hypothesis for the loop invariant is that in the entrance to the while loop Π C • ρ = ρ. We show that the induction hypothesis remains true after failed measurement, which is the interesting case: In the first equation we used the fact that the resampling the qubits b(f ), and measuring Π C\Γ(f ) commute, since they act on different qubits; and the induction hypothesis.
In the following example, the parameters that govern the number of resamplings in our main algorithm -see Theorem 31 -are kept fixed, yet the number of resamplings in the suggested algorithm above are unbounded.
Suppose we start with |ψ init in the state |00 or |01 (which happens with probability 1/2). When we test Π 1 the answer will almost always be "checked", and the state might change a little bit if we started with |00 and won't change at all if we started with |01 . When we test Π 1,2 the outcome will almost always be "no", and the second qubit will be resampled. But this will not help, as we (almost) go back to one of the initial states: we are very close to either |00 or |01 (and very far from the only accepted state |10 ).

G Failed attempt towards an FPRAS
It seems fairly straightforward to adapt the progressive channel formalism to the setting of a quantum fully polynomial random approximation scheme (FPRAS); by this we mean the construction of a quantum algorithm, which for any given , should find a state ρ with support on energy levels below , but can terminate with "error" with probability 1 2 (which can be reduced exponentially by repetition). The running time should grow polynomially in the input size and in 1/ . The challenge is to implement at the t'th iteration, a progressive quantum channel as in Definition 24, where we replace Π V C with Π t V C which is the projection onto all eigenstates with energy up to t with respect to f ∈C Π f , and similarly replace Π V C∪{f } with Π (t+1) V C∪{f } , and replace Π V C\Γ + (f ) with Π (t+1) V C\Γ + (f ) . This guarantees that if the number of channels applied in the algorithm is T , and the algorithm terminates successfully, the energy of the final state is below T .
The main issue can be understood via the following example, which arises with the use of (weak or strong) measurements: Suppose |ψ lies in Π t V C . Now, suppose we do a (strong) measurement of Π f , then we are tempted to think that Π f |ψ lies in Π t V C\Γ + (f ) . Surprisingly this need not to be true, as it can happen that |ψ is not an element of the subspace Π t V C\Γ + (f ) . Next, we will show how another attempt to implement such a channel fails. Consider the adaptation to the exact quantum channel as in Definition 18, where we use Π This construction would not have property (iii). Essentially, the reason is that unlike before, Π V Π V ∪{f } = Π V ∪{f } . Therefore, it could be that a state has low energy with respect to a Hamiltonian, and that when the energy of that state is measured of with respect to a sub-Hamiltonian, its energy would be higher than before.