betaFeedback

WorksPhysics and Astronomy

Faster than square-root run-time in adiabatic quantum algorithms for Exact Cover 3

Abstract

By intertwining ideas from sequential and adiabatic quantum computing, we propose a quantum algorithm for the problem class Exact Cover 3, which is a sub-class of 3-satisfiability (3-SAT) problems and NP (nondeterministic polynomial time) complete. We find a quantum run-time which is significantly faster than the square-root run-time N→N1/2N\to N^{1/2} of the Grover algorithm. Depending on the structure of the problem (e.g., connectivity of clauses), the run-time scaling may range from approximately third root N→N1/3N\to N^{1/3} to nearly fourth root N→N1/4N\to N^{1/4}, possibly even faster.

Introduction After the pioneering works of Feynman [1], Shor [2], Grover [3] and many others (see, e.g., [4]), it has been a long standing question of which advantages quantum algorithms can offer for solving classical problems. The Grover search algorithm [3] for finding a specific item (e.g., the zero of a complicated function) in an unsorted database containing NN entries offers a quadratic speed-up N→N1/2N \to N^{1/2} in comparison to a classical brute-force search. In the absence of any structure in the problem, it can be shown [5] that this quadratic quantum speed-up N→N1/2N \to N^{1/2} is optimal, i.e., some additional information about the problem or its solution is required for achieving further speed-up. The most prominent example is Shor’s factoring algorithm [2] with an exponential speed-up N→O([ln⁡N]3)N \to O([\ln N]^3).

Typically NP (nondeterministic polynomial time) problems are considered promising candidates for quantum algorithms [6]. Simply put, the solution of an NP problem is easy to verify but may be hard to find [7]. Examples are factoring, the eight-queens problem or the sudoku puzzles in newspapers. A sub-class of this complexity class are the NP complete problems, onto which all other NP problems can be mapped efficiently. In this sense, NP complete problems are the hardest problems in NP. Note that factoring, for example, is not NP complete. In this Letter, we shall focus on the problem class Exact Cover 3 (EC3) which is NP complete.

In the usual scheme of sequential quantum computing, the final state ∣ψout⟩|\psi_{\mathrm{out}}\rangle containing the solution to the problem is obtained after applying a sequence of quantum gates to some initial state ∣ψin⟩|\psi_{\mathrm{in}}\rangle. In contrast, adiabatic quantum computing is based on the idea of constructing a suitable Hamiltonian H^out\hat{H}_{\mathrm{out}} such that the sought-after state ∣ψout⟩|\psi_{\mathrm{out}}\rangle is its ground state, see, e.g., [8]. To arrive at the desired state ∣ψout⟩|\psi_{\mathrm{out}}\rangle, the strategy is to start with an initial Hamiltonian H^in\hat{H}_{\mathrm{in}}, whose ground state ∣ψin⟩|\psi_{\mathrm{in}}\rangle is known and can be prepared easily, and then to slowly transform from H^in\hat{H}_{\mathrm{in}} to H^out\hat{H}_{\mathrm{out}}. Usually, a direct interpolation scheme with a switching function f(t)f(t) is considered

H^(t)=[1−f(t)]H^in+f(t)H^out,(1)\hat{H}(t) = [1-f(t)]\hat{H}^{\mathrm{in}} + f(t)\hat{H}^{\mathrm{out}}, \tag*{(1)}

but we employ a different scheme here, see also [9, 10, 11, 12, 13, 14, 15, 16, 17, 18].

Via the adiabatic theorem [19], the run-time required for adiabatic evolution (i.e., staying close to the instantaneous ground state all the time) is determined by the energy gap ΔE\Delta E between the ground and the first excited state(s), which typically becomes quite small at some point. Estimating this minimum energy gap ΔE\Delta E and thereby the required run-time for general problems is still an open question. It has been suggested that adiabatic quantum algorithms might be exponentially speed-up for NP complete problems [20], but this claim is debated [21, 22, 23, 24, 25, 26]. For example, based on Anderson like localization phenomena, it has been argued [24] that such adiabatic quantum algorithms should not be faster than the square-root Grover run-time N→N1/2N \to N^{1/2} for large NN, at least for the conventional scheme (1). For a specific class of Hamiltonians H^in\hat{H}^{\mathrm{in}} for which the minimum gap ΔEmin⁡\Delta E_{\min} could be calculated or estimated analytically, a square-root run-time has been found [22, 27].

In the following, we intertwine ideas from sequential and adiabatic quantum computing and propose adiabatic quantum algorithms deviating from the conventional scheme (1). We show that the achievable run-time is much faster than in the Grover case N→N1/2N \to N^{1/2}, such as N→N1/3N \to N^{1/3} or N→N1/4N \to N^{1/4}.

Exact Cover 3 The problem class [20, 28] Exact Cover 3 (EC3) can be formulated in the following way: For nn bits zμ∈{0,1}z_\mu\in\{0,1\}, we seek a sequence ww (referred to as the solution) such as w=10…01w = 10\ldots01 (where we would have z1w=1,z2w=0,…,zn−1w=0,znw=1z_1^w = 1, z_2^w = 0,\ldots,z_{n-1}^w = 0,z_n^w = 1) which satisfies mm constraints zμw+zνw+zρw=1z_\mu^w + z_\nu^w + z_\rho^w = 1 (referred to as clauses). The arrangement of these mm triples μ,ν,ρ\mu,\nu,\rho then defines the specific problem to be solved [29].

Here we assume that the problem has a unique solution ww (or at least a very small number of solutions) since these are typically the hard problems [20, 30]. Thus, we need at least m≥n/3m \ge n/3 clauses to cover all bits. Excluding the case of contradicting clauses (such that no solution exists), there would still be a huge number of possible solutions for this small mm. Adding more and more clauses then restricts the number of solutions further and further, until this number drops down to unity (or a small number) at a percolation like threshold at a ratio of m/nm/n between 60 % and 80 % [23, 30, 31, 32]. To be specific, we take m≈2n/3m \approx2n/3 in the following [30].

As a result, each bit is involved in two clauses on average. Actually, this is also the most relevant case: Obviously, a bit which is not involved in any clause can be omitted, such that every bit must be involved in at least one clause. If a bit is involved in only one clause, it could also be omitted and the remaining two bits then would have to satisfy the two-bit clause zμzν=0z_\mu z_\nu= 0. In the other direction, a bit involved in many clauses does also allow us to reduce the complexity by a distinction of cases: If it is 1, all other bits involved in these clauses must be 0; if it is 0, these three-bit clauses turn to two-bit clauses zμ+zν=1z_\mu+ z_\nu= 1 which also reduce the complexity. Thus, in the following, we assume that almost all bits are involved in two clauses, with some rare exceptions (e.g., one or three clauses), see also [33].

An even more compelling argument applies to pairs of bits. If two bits, say zμz_\mu and zνz_\nu, are involved in two clauses, such as zμ+zν+zρ=1z_\mu+ z_\nu+ z_\rho= 1 and zμ+zν+zλ=1z_\mu+ z_\nu+ z_\lambda= 1, then the remaining third bits must be equal zρ=zλz_\rho= z_\lambda, which would again allow us to reduce the complexity. Thus, we assume (without exceptions) that each pair shares at most one clause [16].

Adiabatic Quantum Algorithm In order to construct a Hamiltonian whose ground state encodes the sought after solution ww for Exact Cover 3, one option is [34, 35]

H^EC3=14∑μνρclauses(σμz+σνz+σρz−1)2=m1−∑μNμ2σμz+∑μνTμν4σμzσνz.(2)\begin{aligned} \hat{H}^{\mathrm{EC3}} = \frac{1}{4} \sum_{\mu\nu\rho}^{\text{clauses}} \left(\sigma_\mu^z + \sigma_\nu^z + \sigma_\rho^z - 1\right)^2 \\ &= m \mathbf{1} - \sum_\mu\frac{N_\mu}{2}\sigma_\mu^z + \sum_{\mu\nu}\frac{T_{\mu\nu}}{4}\sigma_\mu^z\sigma_\nu^z . \tag*{(2)} \end{aligned}

where the Pauli spin matrix σμz=(∣0⟩⟨0∣−∣1⟩⟨1∣)μ\sigma_\mu^z = (|0\rangle\langle0| - |1\rangle\langle1|)_\mu acts on the qubit at position μ\mu. Here, TμνT_{\mu\nu} and NμN_\mu denote the number of clauses involving the pair μ,ν\mu,\nu of bits or the single bit μ\mu, respectively. As explained above, TμνT_{\mu\nu} is either zero or one while NμN_\mu is typically two. As a result, the Hamiltonian (2) corresponds to a frustrated anti-ferromagnet with local fields in a complex geometry [36]. The Hamiltonian (2) is non-negative and the solution ww to all clauses is its ground state, i.e., the kernel H^EC3∣w⟩=0\hat{H}^{\mathrm{EC3}}|w\rangle= 0.

Following the usual scheme of adiabatic quantum computing, one could start from a suitable initial Hamiltonian such as H^in=±∑μσμx\hat{H}^{\mathrm{in}} = \pm\sum_\mu\sigma_\mu^x and then interpolate from H^in\hat{H}^{\mathrm{in}} to H^out=H^EC3\hat{H}^{\mathrm{out}} = \hat{H}^{\mathrm{EC3}} via (1), see, e.g., [20, 27].

However, here we propose a different scheme. Instead of switching on all clauses simultaneously, we first split up the set of all mm clauses into two sub-sets of m1m_1 and m2m_2 clauses, respectively, such that m=m1+m2m = m_1 + m_2 and the first m1m_1 clauses are non-overlapping. Here non-overlapping means that none of the first m1m_1 clauses share the same qubit, i.e., no qubit involved in one of the first m1m_1 clauses is involved in any other of these m1m_1 clauses (but typically in one of the other m2m_2 clauses). Thus, these first m1m_1 clauses are disconnected and we may switch them on (or implement them) independently of each other, see Figure 1. More precisely, we split up the Hamiltonian (2) into these two sub-sets H^EC3=H^1EC3+H^2EC3\hat{H}^{\mathrm{EC3}} = \hat{H}_1^{\mathrm{EC3}} + \hat{H}_2^{\mathrm{EC3}} and first switch on H^1EC3\hat{H}_1^{\mathrm{EC3}}. The ground-state manifold of H^1EC3\hat{H}_1^{\mathrm{EC3}}, i.e., its kernel, contains all computational basis states ∣z⟩|z\rangle which satisfy the first m1m_1 clauses, i.e., H^1EC3∣z⟩=0\hat{H}_1^{\mathrm{EC3}}|z\rangle= 0. Preparing an initial state ∣ψin⟩|\psi_{\mathrm{in}}\rangle within this manifold (as specified below) then amounts to implementing the first m1m_1 clauses.

Figure 1. Comparison between the conventional scheme (1) and the step-wise algorithm (6) proposed here for a specific example. The top panel depicts the considered Exact Cover 3 instance with 21 bits (black horizontal lines) and 14 clauses (green triangles). The m1=7m_1 = 7 non-overlapping clauses are arranged on the left-hand side and the remaining m2=7m_2 = 7 clauses to their right. The unique solution ww is given in the column on the right-hand side. The middle panel shows the lowest two eigenvalues (black and red curve) of the Hamiltonian (1) as a function of the interpolation parameter f(t)f(t) as well as the probability overlap between the instantaneous ground state ∣ψ0(t)⟩|\psi_0(t)\rangle and the initial ground state ∣s⟩=∣+…+⟩|s\rangle= |+ \ldots+\rangle (yellow curve) and the final ground state ∣w⟩|w\rangle (green curve), respectively. In analogy, the bottom panel displays these values for the step-wise algorithm (6), where the initial ground state ∣s~⟩|\tilde{s}\rangle is the reduced superposition state (4). For the latter, the minimum gap is around a factor of three larger and the Landau-Zener two-mode description (7) a much better approximation.

Initial State Within this manifold, the initial state ∣ψin⟩|\psi_{\mathrm{in}}\rangle is chosen such that it coincides with a W state

∣W⟩=∣001⟩+∣010⟩+∣100⟩3(3)|W\rangle= \frac{|001\rangle+ |010\rangle+ |100\rangle}{\sqrt{3}} \tag*{(3)}

for each triple of qubits involved in one of the first m1m_1 clauses, i.e., a superposition of the three solutions of that clause with equal weight [37]. For qubits which are not involved in any of the first m1m_1 clauses, we take the plus state ∣+⟩=(∣0⟩+∣1⟩)/2|+\rangle= (|0\rangle+ |1\rangle)/\sqrt{2}. The desired initial state after implementing the first m1m_1 clauses would then be the tensor product of the W states (3) for the triples involved in the first m1m_1 clauses and the plus states ∣+⟩|+\rangle for the remaining single qubits. As a result, it is the reduced superposition state

∣ψin⟩=∣s~⟩=1N1∑z∈{0,1}nm1 clauses∣z⟩(4)|\psi_{\mathrm{in}}\rangle= |\tilde{s}\rangle= \frac{1}{\sqrt{N_1}} \sum_{z\in\{0,1\}^n}^{m_1\ \mathrm{clauses}} |z\rangle \tag*{(4)}

of all the N1N_1 solutions of the first m1m_1 clauses, i.e., those computational basis states obeying H^1EC3∣z⟩=0\hat{H}_1^{\mathrm{EC3}}|z\rangle= 0. Note that, for a sufficiently large number m1m_1 of first clauses, this number N1N_1 is much smaller N1≪NN_1 \ll N than the total number N=2nN = 2^n of computational basis states.

In order to stabilize the initial state (4) as the unique ground state of the initial Hamiltonian H^in\hat{H}^{\mathrm{in}}, we may add H^in=H^1EC3+H^mix\hat{H}^{\mathrm{in}} = \hat{H}_1^{\mathrm{EC3}} + \hat{H}^{\mathrm{mix}} a suitable scrambling or mixing Hamiltonian H^mix\hat{H}^{\mathrm{mix}} of the form

H^mix=∑μνm1 clausesTμν2(1−σμxσνx−σμyσνy−σμzσνz)(5)\hat{H}^{\mathrm{mix}} = \sum_{\mu\nu}^{m_1\ \mathrm{clauses}} \frac{T_{\mu\nu}}{2}\left(1 - \sigma_\mu^x\sigma_\nu^x - \sigma_\mu^y\sigma_\nu^y - \sigma_\mu^z\sigma_\nu^z\right) \tag*{(5)}

where the sum over μ\mu and ν\nu is restricted to those pairs of qubits which are connected by one of the first m1m_1 clauses. Note that the above form (5) has already been suggested in [35] and encodes SWAP operations on the qubit pairs μ\mu and ν\nu. For the remaining single qubits ∣zρ⟩|z_\rho\rangle not involved in any of the first m1m_1 clauses, we may add the usual term (1−σρx)/2(1 - \sigma_\rho^x)/2 in order to stabilize their plus states.

Adiabatic Evolution In order to evolve from the initial state (4) to the ground-state solution state ∣w⟩|w\rangle which satisfies all clauses, we have to switch on the remaining m2m_2 clauses. The idea is to stay in the ground-state manifold of H^1EC3\hat{H}_1^{\mathrm{EC3}} (i.e., its kernel) such that we may keep H^1EC3\hat{H}^{\mathrm{EC3}}_1 switched on. Then, to eliminate all states in this ground-state manifold which violate any of the remaining m2m_2 clauses, we slowly switch on H^2EC3\hat{H}^{\mathrm{EC3}}_2 and reduce the impact of H^mix\hat{H}^{\mathrm{mix}} accordingly, e.g., with f(t)∈[0,1]f(t) \in[0,1]

H^(t)=H^1EC3+[1−f(t)]H^mix+f(t)H^2EC3.(6)\hat{H}(t)=\hat{H}^{\mathrm{EC3}}_1+[1-f(t)]\hat{H}^{\mathrm{mix}}+f(t)\hat{H}^{\mathrm{EC3}}_2. \tag*{(6)}

According to the adiabatic theorem, the corresponding quantum evolution stays close to the (instantaneous) ground state provided that it is slow enough, where the allowed interpolation speed df/dtdf/dt is set by the minimum gap ΔE\Delta E between the (instantaneous) ground and first excited state(s).

To a much stronger extent than in the traditional scheme (see also [20] and Figure 1), we have an avoided level crossing between the (instantaneous) ground and first excited state at some point of the evolution, where ΔE\Delta E becomes very small. To estimate the minimum gap ΔE\Delta E, we focus on this avoided level crossing and neglect all higher lying states, such that we may approximate it as a Landau-Zener problem. Since the major change of the ground state occurs in the vicinity of this avoided level crossing, we neglect the quantum evolution before and after, such that we may focus to the effective Landau-Zener sub-space spanned by the initial and final ground states ∣s~⟩|\tilde{s}\rangle and ∣w⟩|w\rangle or, more precisely ∣s~⊥⟩∝∣s~⟩−∣w⟩⟨w∣s~⟩|\tilde{s}_{\perp}\rangle\propto|\tilde{s}\rangle-|w\rangle\langle w|\tilde{s}\rangle and ∣w⟩|w\rangle. In this Landau-Zener sub-space, the effective Hamiltonian can be represented as

H^→(⟨w∣H^∣w⟩⟨w∣H^∣s~⊥⟩⟨s~⊥∣H^∣w⟩⟨s~⊥∣H^∣s~⊥⟩),(7)\hat{H}\to\begin{pmatrix} \langle w|\hat{H}|w\rangle& \langle w|\hat{H}|\tilde{s}_{\perp}\rangle\\ \langle\tilde{s}_{\perp}|\hat{H}|w\rangle& \langle\tilde{s}_{\perp}|\hat{H}|\tilde{s}_{\perp}\rangle \end{pmatrix}, \tag*{(7)}

where the avoided level crossing occurs when the diagonal terms coincide ⟨w∣H^∣w⟩=⟨s~⊥∣H^∣s~⊥⟩\langle w|\hat{H}|w\rangle=\langle\tilde{s}_{\perp}|\hat{H}|\tilde{s}_{\perp}\rangle. Since the solution ∣w⟩|w\rangle is annihilated by both H^1EC3\hat{H}^{\mathrm{EC3}}_1 and H^2EC3\hat{H}^{\mathrm{EC3}}_2 while changing any of the qubits with H^mix\hat{H}^{\mathrm{mix}} is typically not a solution anymore, we have ⟨w∣H^∣w⟩=0\langle w|\hat{H}|w\rangle=0 for all f(t)f(t). Similarly, ∣s~⊥⟩|\tilde{s}_{\perp}\rangle is annihilated by H^1EC3\hat{H}^{\mathrm{EC3}}_1 such that the value of f(t)f(t) at the avoided level crossing is determined by a balance of ⟨s~⊥∣H^mix∣s~⊥⟩\langle\tilde{s}_{\perp}|\hat{H}^{\mathrm{mix}}|\tilde{s}_{\perp}\rangle and ⟨s~⊥∣H^2EC3∣s~⊥⟩\langle\tilde{s}_{\perp}|\hat{H}^{\mathrm{EC3}}_2|\tilde{s}_{\perp}\rangle which depends on m1m_1 and m2m_2 etc.

The minimum energy gap ΔEmin⁡\Delta E_{\min} at the avoided level crossing is then set by the off-diagonal terms ⟨w∣H^∣s~⊥⟩\langle w|\hat{H}|\tilde{s}_{\perp}\rangle. Again, as ∣w⟩|w\rangle is annihilated by both H^1EC3\hat{H}^{\mathrm{EC3}}_1 and H^2EC3\hat{H}^{\mathrm{EC3}}_2, the off-diagonal terms are generated by the scrambling Hamiltonian (5) via ⟨w∣H^mix∣s~⊥⟩\langle w|\hat{H}^{\mathrm{mix}}|\tilde{s}_{\perp}\rangle. Quite intuitively, such a mixing is required for the transition from a wrong solution contained in ∣s~⊥⟩|\tilde{s}_{\perp}\rangle to the correct solution ∣w⟩|w\rangle. When acting on the solution ∣w⟩|w\rangle, the terms in H^mix\hat{H}^{\mathrm{mix}} may swap a pair of qubits involved in any of the first m1m_1 clauses or flip one of the remaining qubits. Therefore, unless the swapping operation acts on two bits in the solution ww which both happen to be zero (they cannot both be one since they are involved in a clause), the resulting state will be different from ∣w⟩|w\rangle, but it will be contained in the reduced superposition state ∣s~⊥⟩|\tilde{s}_{\perp}\rangle. Consequently, the off-diagonal terms scale (at least) as ⟨w∣H^∣s~⊥⟩=O(1/N1)\langle w|\hat{H}|\tilde{s}_{\perp}\rangle=\mathcal{O}(1/\sqrt{N_1}) and thus the minimum energy gap ΔEmin⁡\Delta E_{\min} also scales as ΔEmin⁡=O(1/N1)\Delta E_{\min}=\mathcal{O}(1/\sqrt{N_1}), see Figure 1. This, in turn, sets the required adiabatic run-time which scales as O(N1)\mathcal{O}(\sqrt{N_1}) and thus may be much faster than the Grover run-time O(N)\mathcal{O}(\sqrt{N}) yielding a quadratic speed-up. An alternative justification for the O(N1)\mathcal{O}(\sqrt{N_1}) scaling is provided in the Appendix.

Quantum run-time scaling The achievable quantum run-time depends on N1N_1, i.e., on the number m1m_1 of clauses to be switched on in the first step. For a lower bound on this number, let us consider the following scheme: First, we pick a clause at random and assign it to the set of these m1m_1 clauses. Then we take those clauses (typically three) which share one qubit with this first clause, i.e., overlap with it, and assign them to the set of m2m_2 clauses to be switched on in the second step. Since the remaining set of m−4m-4 clauses is non-overlapping with the first one, we can repeat the same sequence. Actually, as in subsequent steps some clauses may already have been sorted to the m2m_2 set, the ratio of m2m_2 to m1m_1 clauses may be smaller than three, such that we eventually have at least m1≥m/4m_1\ge m/4 non-overlapping clauses for initial state preparation and less than m2≤3m/4m_2\le3m/4 for the adiabatic algorithm (6). For each of these m1m_1 clauses, the number of allowed solutions is reduced by a factor of 3/83/8, i.e., the three involved qubits are effectively reduced to “one and a half” qubits. Thus N1=(3/8)m1N≲(3/8)m/4NN_1=(3/8)^{m_1}N\lesssim(3/8)^{m/4}N and inserting m≈2n/3m\approx2n/3 (as discussed above), we find a reduction of N1≈(3/8)n/6N≈(0.85)nN=(1.7)nN_1\approx(3/8)^{n/6}N\approx(0.85)^nN=(1.7)^n instead of N=2nN=2^n. Since the run-time scales with N1\sqrt{N_1}, this amounts to an almost third root run-time N→N1/3N\to N^{1/3}.

An even faster run-time can be reached if m1m_1 is larger. Depending on the connectivity of the graph describing all bits and clauses, one could find more non-overlapping clauses, up to the maximum number m1≤m1max⁡=n/3m_1\le m_1^{\max}=n/3 (that one would obtain when the m1m_1 clauses cover all qubits). For this upper bound, an analogous calculation yields an approximately fourth root run-time N→N1/4N\to N^{1/4}.

Clusters of clauses Even shorter run-times can be reached if we allow for finite clusters of clauses in the set of m1m_1 clauses to be switched on first. As the simplest example, let us consider two clauses which share one qubit. Then the W state (3) has to be adapted accordingly to a superposition state of the five allowed solutions for the five involved qubits. As a result, the factor of 3/83/8 for a single clause is now reduced to 5/325/32 for these two connected clauses. In analogy to the scheme described above, we may place this pair of clauses into the first set m1m_1 and the clauses (typically four) overlapping with this pair into the second set m2m_2. In this way, the ratio between clauses put in m1m_1 and m2m_2, respectively, is also improved from 1/31/3 to 1/21/2. Thus, the effective reduction factor per qubit of 0.850.85 found above is now improved to 0.660.66. How far one can push this scheme (e.g., with larger clusters) again depends on the connectivity of the graph describing all bits and clauses.

Conclusions We propose an adiabatic quantum algorithm for the NP complete problem class Exact Cover 3. In contrast to the usual scheme, we do not switch on all clauses simultaneously, but proceed in two steps. In the first step, a sub-set of m1m_1 clauses is implemented, while the remaining m2m_2 clauses are switched on adiabatically in the second step. In this way, we achieve a run-time which is significantly faster than the standard square-root run-time N→N1/2N \to N^{1/2} of the Grover algorithm, such as N→N1/3N \to N^{1/3} or N→N1/4N \to N^{1/4}, possibly even faster.

Our analytical estimate of the minimum energy gap and thus run-time evades major shortcomings of numerical approaches. On the one hand, they are limited to finite system sizes, which makes it hard to obtain the correct scaling in the large-NN limit. On the other hand, they cannot consider all possible instances for large NN and the study of random instances may also not include the hard cases which are required for NP completeness.

Apart from the run-time, the space (e.g., number of required bits or qubits at a given time) of an algorithm is also an important criterion. For the adiabatic quantum algorithm proposed here, the space scales linearly in nn. An example for a classical algorithm with such a linear scaling is the brute-force search, but this requires a very long run-time O(N)\mathcal{O}(N). One could also restrict the search space classically, but this would still require a run-time of order N1N_1 and is thus inferior to the quantum algorithm proposed here. Classical algorithms with shorter run-times O(Nξ)\mathcal{O}(N^\xi) with ξ<1\xi< 1 such as the “dancing links” [38, 39, 40] are recursive and require far more space than O(n)\mathcal{O}(n).

As a related point, the energy consumption of the computation is also an increasingly important criterion. If we assign a certain energy cost per gate operation to a classical algorithm, the total energy consumption would scale exponentially O(Nξ)\mathcal{O}(N^\xi) with the number nn of bits or qubits. Adiabatic quantum algorithms could facilitate a much better energy efficiency since they can be operated by a slowly varying classical (e.g., magnetic) field such that the total energy cost could scale linearly O(n)\mathcal{O}(n).

It should also be stressed here that we did not incorporate the effects of an environment such as losses and decoherence. Actually, this issue points to another potential advantage of the adiabatic scheme: Already without error correction, adiabatic quantum algorithms are more robust against the impact of an environment than sequential quantum algorithms [41]. Note, however, this does not mean that one can omit the coupling to the environment completely, see, e.g., [42]. In this regard, increasing the energy gap ΔE\Delta E by the two-step procedure proposed here should help to make the quantum algorithm more robust against decoherence.

Acknowledgments

Acknowledgments Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) through the Collaborative Research Center SFB 1242 (Project-ID 278162697). R. S. has benefited from the activities of COST Action CA23115: Relativistic Quantum Information, funded by COST (European Cooperation in Science and Technology).

References

remains the same.

Appendix: Sequential Quantum Algorithm

While suggestive, the arguments in the main text do not constitute a rigorous proof for a faster than square-root run-time. In order to demonstrate that such a reduced run-time is indeed possible for this problem class, let us switch back to the scheme of sequential quantum computing. To this end, we present a generalization of the Grover search algorithm.

As the first step, we construct the unitary transformation U^w=1−2∣w⟩⟨w∣\hat{U}_{w}=1-2|w\rangle\langle w| generating a reflection at the plane perpendicular to the solution state ∣w⟩|w\rangle. One way of doing that is to introduce mm ancilla qubits ∣yi⟩|y_i\rangle, one for each clause ii involving the three qubits zμz_\mu, zνz_\nu and zρz_\rho. Starting in the state ∣yi⟩=∣0⟩|y_i\rangle=|0\rangle, we apply the unitary

∣zμ⟩∣zν⟩∣zρ⟩∣yi⟩→∣zμ⟩∣zν⟩∣zρ⟩∣yi⊕ci(zμ,zν,zρ)⟩(8)|z_\mu\rangle|z_\nu\rangle|z_\rho\rangle|y_i\rangle\to|z_\mu\rangle|z_\nu\rangle|z_\rho\rangle|y_i\oplus c_i(z_\mu,z_\nu,z_\rho)\rangle \tag*{(8)}

where ci(zμ,zν,zρ)=1c_i(z_\mu,z_\nu,z_\rho)=1 if the clause ii is satisfied and zero otherwise. After testing all mm clauses, we apply a phase flip provided that all ancilla qubits are ∣1⟩|1\rangle, e.g., with an additional phase ancilla ∣x⟩|x\rangle and the unitary

∣y1⟩⋯∣ym⟩∣x⟩→∣y1⟩⋯∣ym⟩∣x⊕y1y2⋯ym⟩.(9)|y_1\rangle\cdots|y_m\rangle|x\rangle\to|y_1\rangle\cdots|y_m\rangle|x\oplus y_1y_2\cdots y_m\rangle. \tag*{(9)}

With the initial state (∣0⟩−∣1⟩)/2(|0\rangle-|1\rangle)/\sqrt{2} for this phase ancilla qubit, this unitary (9) introduces a conditional phase flip.

Finally, we repeat the sequence (8) for all mm clauses in order to set all ancilla qubits ∣yi⟩|y_i\rangle back to ∣0⟩|0\rangle. As a result, we obtain a phase flip for the solution state ∣w⟩→−∣w⟩|w\rangle\to-|w\rangle, while all other states are unaffected. This constitutes the first half U^w=1−2∣w⟩⟨w∣\hat{U}_w=1-2|w\rangle\langle w| of the Grover iteration (often referred to as the oracle).

The second half of Grover iteration U^s~=1−2∣s~⟩⟨s~∣\hat{U}_{\tilde{s}}=1-2|\tilde{s}\rangle\langle\tilde{s}| is also a reflection but now on the plane perpendicular to the reduced superposition state (4). This can be implemented with fewer ancilla qubits, one for each of the first m1m_1 clauses in (4). For example, we may apply unitary transformations U^i\hat{U}_i to the three qubits ∣zμ⟩|z_\mu\rangle, ∣zν⟩|z_\nu\rangle and ∣zρ⟩|z_\rho\rangle involved in the clause ii which map the W states (3) to ∣111⟩|111\rangle. Then we may entangle these three qubits to the corresponding ancilla qubit ∣yi⟩|y_i\rangle in analogy to (8)

∣zμ⟩∣zν⟩∣zρ⟩∣yi⟩→∣zμ⟩∣zν⟩∣zρ⟩∣yi⊕zμzνzρ⟩.(10)|z_\mu\rangle|z_\nu\rangle|z_\rho\rangle|y_i\rangle\to|z_\mu\rangle|z_\nu\rangle|z_\rho\rangle|y_i\oplus z_\mu z_\nu z_\rho\rangle. \tag*{(10)}

As a result, the ancilla qubit ∣yi⟩|y_i\rangle is switched to ∣1⟩|1\rangle if these three qubits are in the state ∣111⟩|111\rangle, i.e., if they were in the W state (3) originally. Then we may apply the phase flip in analogy to (9), but this time the mm ancilla qubits ∣y1⟩…∣ym⟩|y_1\rangle\ldots|y_m\rangle for all clauses are replaced by the m1m_1 ancilla qubits for the first m1m_1 clauses and the remaining qubits in the plus states (e.g., after applying Hadamard gates). As before, the final step consists in reversing the applied unitary transformations U^i\hat{U}_i and the Hadamard gates as well as (10) such that the qubits ∣zμ⟩|z_\mu\rangle and the ancilla qubits ∣yi⟩|y_i\rangle are set back to their original states – apart from the phase flip of the state ∣s~⟩|\tilde{s}\rangle, while again all other states remain unaffected. In this way, we may implement the second unitary U^s~=1−2∣s~⟩⟨s~∣\hat{U}_{\tilde{s}}=1-2|\tilde{s}\rangle\langle\tilde{s}| which completes the Grover iteration.

As in the usual Grover algorithm, the consecutive application of the two unitary operations U^s~U^w\hat{U}_{\tilde{s}}\hat{U}_w effectively amounts to a rotation within the sub-space spanned by ∣w⟩|w\rangle and ∣s~⟩|\tilde{s}\rangle. However, due to ⟨w∣s~⟩=1/N1\langle w|\tilde{s}\rangle=1/\sqrt{N_1} instead of 1/N1/\sqrt{N}, the rotation angle for each iteration is much larger than in the usual Grover algorithm. Thus, starting in the ∣s~⟩|\tilde{s}\rangle state (4), we need O(N1)O(\sqrt{N_1}) iterations for reaching the ∣w⟩|w\rangle state, i.e., the solution to our problem.

Note that the Grover algorithm within a reduced search space has already been discussed in the literature [43, 44] though in a different context. Furthermore, instead of the full phase flips in U^w=1−2∣w⟩⟨w∣\hat{U}_w=1-2|w\rangle\langle w| and U^s~=1−2∣s~⟩⟨s~∣\hat{U}_{\tilde{s}}=1-2|\tilde{s}\rangle\langle\tilde{s}|, one could also generate gradual phase rotations such as U^wφ=1−∣w⟩⟨w∣+eiφ∣w⟩⟨w∣\hat{U}_w^\varphi=1-|w\rangle\langle w|+e^{i\varphi}|w\rangle\langle w| and analogously for U^s~φ\hat{U}_{\tilde{s}}^\varphi with some small phase φ≪1\varphi\ll1. In this way, the repeated consecutive application of the two unitary operations U^s~φ1U^wφ2\hat{U}_{\tilde{s}}^{\varphi_1}\hat{U}_w^{\varphi_2} with suitably chosen phases φ1\varphi_1 and φ2\varphi_2 yields the Trotter representation [45] of the effective Hamiltonian (7) which brings us back to the adiabatic scheme. Since the minimum energy gap is quite small, the phases φ1\varphi_1 and φ2\varphi_2 corresponding to the Trotter discretization of time need not be very small.

References

  1. [1]Richard P. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21:467–488, 1982.
  2. [2]Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509, 1997.
  3. [3]Lov K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett., 79:325–328, Jul 1997.DOI
  4. [4]Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, 2000.
  5. [5]Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510–1523, 1997.DOI
  6. [6]Vicky Choi. Different adiabatic quantum optimization algorithms for the NP-complete Exact Cover and 3SAT problems. Quantum Information and Computation, 11:0638–0648, 2011.
  7. [7]Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, Cambridge, 1990.
  8. [8]Tameem Albash and Daniel A. Lidar. Adiabatic quantum computation. Rev. Mod. Phys., 90:015002, Jan 2018.DOI
  9. [9]Jeremie Roland and Nicolas J. Cerf. Adiabatic quantum search algorithm for structured problems. Physical Review A, 68:062312, 2003.DOI
  10. [10]Wenjin Mao. Solving satisfiability problems by the ground-state quantum computer. Phys. Rev. A, 72:052316, Nov 2005.DOI
  11. [11]M. S. Siu. Adiabatic rotation, quantum search, and preparation of superposition states. Physical Review A, 75:062337, 2007.DOI
  12. [12]G. Schaller. Adiabatic preparation without quantum phase transitions. Physical Review A, 78:032328, 2008.DOI
  13. [13]M. B. Hastings. Topology and phases in fermionic systems. Journal of Statistical Mechanics: Theory and Experiment, 2008(01):L01001, jan 2008.DOI
  14. [14]A. T. Rezakhani, W.-J. Kuo, A. Hamma, D. A. Lidar, and P. Zanardi. Quantum adiabatic brachistochrone. Phys. Rev. Lett., 103:080502, Aug 2009.DOI
  15. [15]Jie Sun, Song-Feng Lu, and Samuel L. Braunstein. On models of nonlinear evolution paths in adiabatic quantum algorithms. Communications in Theoretical Physics, 59(1):22, jan 2013.DOI
  16. [16]Michael Hofmann and Gernot Schaller. Probing nonlinear adiabatic paths with a universal integrator. Phys. Rev. A, 89:032308, Mar 2014.DOI
  17. [17]Lishan Zheng, Jun Zhang, and Mohan Sarovar. Schedule path optimization for adiabatic quantum computing and optimization. Journal of Physics A: Mathematical and Theoretical, 49(16):165305, mar 2016.DOI
  18. [18]Felipe Matus, Jan Střeleček, Pavel Stránský, and Pavel Cejnar. Search for optimal driving in finite quantum systems with precursors of criticality. Phys. Rev. A, 107:012216, Jan 2023.DOI
  19. [19]M. Born and V. Fock. Beweis des Adiabatensatzes. Zeitschrift für Physik, 51:165, 1928.DOI
  20. [20]Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda. A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science, 292(5516):472–475, 2001.DOI
  21. [21]W. van Dam, M. Mosca, and U. Vazirani. How powerful is adiabatic quantum computation? In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 279–287, 2001.
  22. [22]Marko Znidaric and Martin Horvat. Exponential complexity of an adiabatic algorithm for an NP-complete problem. Physical Review A, 73:022329, 2006.DOI
  23. [23]A. P. Young, S. Knysh, and V. N. Smelyanskiy. Size dependence of the minimum excitation gap in the quantum adiabatic algorithm. Physical Review Letters, 101:170503, 2008.DOI
  24. [24]Boris Altshuler, Hari Krovi, and Jérémie Roland. Anderson localization makes adiabatic quantum optimization fail. Proceedings of the National Academy of Sciences, 107(28):12446–12450, 2010.DOI
  25. [25]A. P. Young, S. Knysh, and V. N. Smelyanskiy. First-order phase transition in the quantum adiabatic algorithm. Physical Review Letters, 104:020502, 2010.pubmed.ncbi.nlm.nih.gov/20366577
  26. [26]Itay Hen and A. P. Young. Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems. Phys. Rev. E, 84:061152, Dec 2011.pubmed.ncbi.nlm.nih.gov/22304085
  27. [27]Jérémie Roland and Nicolas J. Cerf. Quantum search by local adiabatic evolution. Physical Review A, 65:042308, Mar 2002.DOI
  28. [28]Richard M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, page 85, New York, 1972.
  29. [29]Note that two-bit clauses of the form zμ + zν = 1 impose a direct relation between these two bits zμ = 1 − zν = z̄ν and thus reduce the complexity of the problem. To account for this option, one could also include clauses of the form z̄μ + zν + zρ = 1.
  30. [30]Vamsi Kalapala and Cris Moore. The phase transition in Exact Cover. Chicago Journal of Theoretical Computer Science, 2008(5), October 2008.
  31. [31]Christopher Moore. The phase transition in random regular Exact Cover. Annales de l’Institut Henri Poincaré D, 3(3):349–362, 2016.arxiv.org/abs/1502.07591
  32. [32]Bingzhi Zhang, Akira Sone, and Quntao Zhuang. Quantum computational phase transition in combinatorial problems. npj Quantum Information, 8:87, 2022.DOI
  33. [33]G. Schaller and R. Schützhold. The role of symmetries in adiabatic quantum algorithms. Quantum Information and Computation, 10:0109–0140, 2010.arxiv.org/abs/0708.1882
  34. [34]M. C. Bańuls, R. Orús, J. I. Latorre, A. Pérez, and P. Ruiz-Femenía. Simulation of many-qubit quantum computation with matrix product states. Phys. Rev. A, 73:022344, Feb 2006.DOI
  35. [35]R. Schützhold and G. Schaller. Adiabatic quantum algorithms as quantum phase transitions: First versus second order. Physical Review A, 74:060304(R), 2006.DOI
  36. [36]Other clauses such as z̄μ + zν + z̄ρ = 1 or z̄μzν = 0 could be implemented in analogy via (1 − σzμ + σzρ)² or (1 + σzμ)(1 + σzν), respectively. They would change the explicit values of Tμν and Nμ, but otherwise the structure For a clause z̄μ + zν + zρ = 1 instead of zμ + zν + zρ = 1, we would just flip the first qubit |zμ⟩, i.e. the state (3) would become (|101⟩ + |110⟩ + |000⟩)/√3. For a two-bit clause zμzν = 0, the corresponding superposition state reads (|10⟩ + |01⟩ + |00⟩)/√3.
  37. [38]Donald E. Knuth. Dancing links, pages 187–214. 2000.
  38. [39]Gordon Hoi, Sanjay Jain, and Frank Stephan. A faster exact algorithm to count X3SAT solutions. In Helmut Simonis, editor, Principles and Practice of Constraint Programming, pages 375–391, Cham, 2020. Springer International Publishing.
  39. [40]Junqiang Peng and Mingyu Xiao. Fast exact algorithms for the SAT problem with bounded occurrences of variables. Theoretical Computer Science, 1029:115037, 2025.DOI
  40. [41]Andrew M. Childs, Edward Farhi, and John Preskill. Robustness of adiabatic quantum computation. Phys. Rev. A, 65:012322, Dec 2001.DOI
  41. [42]Naser Ahmadiniaz, Dennis Kraft, Gernot Schaller, and Ralf Schützhold. Quantum Zeno effect versus adiabatic quantum computing and quantum annealing. New Journal of Physics, 28(6):064502, may 2026.
  42. [43]Salvatore Mandrà, Gian Giacomo Guerreschi, and Alán Aspuru-Guzik. Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems. New Journal of Physics, 18(7):073003, jul 2016.DOI
  43. [44]Andris Ambainis, Kaspars Balodis, Jānis Iraids, Martins Kokainis, Krišjānis Prūsis, and Jevgeņijs Vihrovs. Quantum Speedups for Exponential-Time Dynamic Programming Algorithms, pages 1783–1793. 2019.arxiv.org/abs/1807.05209
  44. [45]Masuo Suzuki. Fractal decomposition of exponential operators with applications to many-body theories and Monte Carlo simulations. Physics Letters A, 146(6):319–323, 1990.DOI

Paper details

vlnc:W_bxt3tmty
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents