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 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 to nearly fourth root , 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 entries offers a quadratic speed-up 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 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 .
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 containing the solution to the problem is obtained after applying a sequence of quantum gates to some initial state . In contrast, adiabatic quantum computing is based on the idea of constructing a suitable Hamiltonian such that the sought-after state is its ground state, see, e.g., [8]. To arrive at the desired state , the strategy is to start with an initial Hamiltonian , whose ground state is known and can be prepared easily, and then to slowly transform from to . Usually, a direct interpolation scheme with a switching function is considered
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 between the ground and the first excited state(s), which typically becomes quite small at some point. Estimating this minimum energy gap 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 for large , at least for the conventional scheme (1). For a specific class of Hamiltonians for which the minimum gap 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 , such as or .
Exact Cover 3 The problem class [20, 28] Exact Cover 3 (EC3) can be formulated in the following way: For bits , we seek a sequence (referred to as the solution) such as (where we would have ) which satisfies constraints (referred to as clauses). The arrangement of these triples then defines the specific problem to be solved [29].
Here we assume that the problem has a unique solution (or at least a very small number of solutions) since these are typically the hard problems [20, 30]. Thus, we need at least 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 . 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 between 60 % and 80 % [23, 30, 31, 32]. To be specific, we take 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 . 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 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 and , are involved in two clauses, such as and , then the remaining third bits must be equal , 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 for Exact Cover 3, one option is [34, 35]
where the Pauli spin matrix acts on the qubit at position . Here, and denote the number of clauses involving the pair of bits or the single bit , respectively. As explained above, is either zero or one while 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 to all clauses is its ground state, i.e., the kernel .
Following the usual scheme of adiabatic quantum computing, one could start from a suitable initial Hamiltonian such as and then interpolate from to 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 clauses into two sub-sets of and clauses, respectively, such that and the first clauses are non-overlapping. Here non-overlapping means that none of the first clauses share the same qubit, i.e., no qubit involved in one of the first clauses is involved in any other of these clauses (but typically in one of the other clauses). Thus, these first 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 and first switch on . The ground-state manifold of , i.e., its kernel, contains all computational basis states which satisfy the first clauses, i.e., . Preparing an initial state within this manifold (as specified below) then amounts to implementing the first 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 non-overlapping clauses are arranged on the left-hand side and the remaining clauses to their right. The unique solution 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 as well as the probability overlap between the instantaneous ground state and the initial ground state (yellow curve) and the final ground state (green curve), respectively. In analogy, the bottom panel displays these values for the step-wise algorithm (6), where the initial ground state 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 is chosen such that it coincides with a W state
for each triple of qubits involved in one of the first 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 clauses, we take the plus state . The desired initial state after implementing the first clauses would then be the tensor product of the W states (3) for the triples involved in the first clauses and the plus states for the remaining single qubits. As a result, it is the reduced superposition state
of all the solutions of the first clauses, i.e., those computational basis states obeying . Note that, for a sufficiently large number of first clauses, this number is much smaller than the total number of computational basis states.
In order to stabilize the initial state (4) as the unique ground state of the initial Hamiltonian , we may add a suitable scrambling or mixing Hamiltonian of the form
where the sum over and is restricted to those pairs of qubits which are connected by one of the first clauses. Note that the above form (5) has already been suggested in [35] and encodes SWAP operations on the qubit pairs and . For the remaining single qubits not involved in any of the first clauses, we may add the usual term in order to stabilize their plus states.
Adiabatic Evolution In order to evolve from the initial state (4) to the ground-state solution state which satisfies all clauses, we have to switch on the remaining clauses. The idea is to stay in the ground-state manifold of (i.e., its kernel) such that we may keep switched on. Then, to eliminate all states in this ground-state manifold which violate any of the remaining clauses, we slowly switch on and reduce the impact of accordingly, e.g., with
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 is set by the minimum gap 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 becomes very small. To estimate the minimum gap , 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 and or, more precisely and . In this Landau-Zener sub-space, the effective Hamiltonian can be represented as
where the avoided level crossing occurs when the diagonal terms coincide . Since the solution is annihilated by both and while changing any of the qubits with is typically not a solution anymore, we have for all . Similarly, is annihilated by such that the value of at the avoided level crossing is determined by a balance of and which depends on and etc.
The minimum energy gap at the avoided level crossing is then set by the off-diagonal terms . Again, as is annihilated by both and , the off-diagonal terms are generated by the scrambling Hamiltonian (5) via . Quite intuitively, such a mixing is required for the transition from a wrong solution contained in to the correct solution . When acting on the solution , the terms in may swap a pair of qubits involved in any of the first clauses or flip one of the remaining qubits. Therefore, unless the swapping operation acts on two bits in the solution 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 , but it will be contained in the reduced superposition state . Consequently, the off-diagonal terms scale (at least) as and thus the minimum energy gap also scales as , see Figure 1. This, in turn, sets the required adiabatic run-time which scales as and thus may be much faster than the Grover run-time yielding a quadratic speed-up. An alternative justification for the scaling is provided in the Appendix.
Quantum run-time scaling The achievable quantum run-time depends on , i.e., on the number 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 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 clauses to be switched on in the second step. Since the remaining set of 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 set, the ratio of to clauses may be smaller than three, such that we eventually have at least non-overlapping clauses for initial state preparation and less than for the adiabatic algorithm (6). For each of these clauses, the number of allowed solutions is reduced by a factor of , i.e., the three involved qubits are effectively reduced to “one and a half” qubits. Thus and inserting (as discussed above), we find a reduction of instead of . Since the run-time scales with , this amounts to an almost third root run-time .
An even faster run-time can be reached if 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 (that one would obtain when the clauses cover all qubits). For this upper bound, an analogous calculation yields an approximately fourth root run-time .
Clusters of clauses Even shorter run-times can be reached if we allow for finite clusters of clauses in the set of 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 for a single clause is now reduced to for these two connected clauses. In analogy to the scheme described above, we may place this pair of clauses into the first set and the clauses (typically four) overlapping with this pair into the second set . In this way, the ratio between clauses put in and , respectively, is also improved from to . Thus, the effective reduction factor per qubit of found above is now improved to . 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 clauses is implemented, while the remaining 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 of the Grover algorithm, such as or , 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- limit. On the other hand, they cannot consider all possible instances for large 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 . An example for a classical algorithm with such a linear scaling is the brute-force search, but this requires a very long run-time . One could also restrict the search space classically, but this would still require a run-time of order and is thus inferior to the quantum algorithm proposed here. Classical algorithms with shorter run-times with such as the “dancing links” [38, 39, 40] are recursive and require far more space than .
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 with the number 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 .
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 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 generating a reflection at the plane perpendicular to the solution state . One way of doing that is to introduce ancilla qubits , one for each clause involving the three qubits , and . Starting in the state , we apply the unitary
where if the clause is satisfied and zero otherwise. After testing all clauses, we apply a phase flip provided that all ancilla qubits are , e.g., with an additional phase ancilla and the unitary
With the initial state for this phase ancilla qubit, this unitary (9) introduces a conditional phase flip.
Finally, we repeat the sequence (8) for all clauses in order to set all ancilla qubits back to . As a result, we obtain a phase flip for the solution state , while all other states are unaffected. This constitutes the first half of the Grover iteration (often referred to as the oracle).
The second half of Grover iteration 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 clauses in (4). For example, we may apply unitary transformations to the three qubits , and involved in the clause which map the W states (3) to . Then we may entangle these three qubits to the corresponding ancilla qubit in analogy to (8)
As a result, the ancilla qubit is switched to if these three qubits are in the state , 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 ancilla qubits for all clauses are replaced by the ancilla qubits for the first 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 and the Hadamard gates as well as (10) such that the qubits and the ancilla qubits are set back to their original states – apart from the phase flip of the state , while again all other states remain unaffected. In this way, we may implement the second unitary which completes the Grover iteration.
As in the usual Grover algorithm, the consecutive application of the two unitary operations effectively amounts to a rotation within the sub-space spanned by and . However, due to instead of , the rotation angle for each iteration is much larger than in the usual Grover algorithm. Thus, starting in the state (4), we need iterations for reaching the 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 and , one could also generate gradual phase rotations such as and analogously for with some small phase . In this way, the repeated consecutive application of the two unitary operations with suitably chosen phases and 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 and corresponding to the Trotter discretization of time need not be very small.
References
- [1]Richard P. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21:467–488, 1982.
- [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]Lov K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett., 79:325–328, Jul 1997.DOI
- [4]Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, 2000.
- [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]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]Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, Cambridge, 1990.
- [8]Tameem Albash and Daniel A. Lidar. Adiabatic quantum computation. Rev. Mod. Phys., 90:015002, Jan 2018.DOI
- [9]Jeremie Roland and Nicolas J. Cerf. Adiabatic quantum search algorithm for structured problems. Physical Review A, 68:062312, 2003.DOI
- [10]Wenjin Mao. Solving satisfiability problems by the ground-state quantum computer. Phys. Rev. A, 72:052316, Nov 2005.DOI
- [11]M. S. Siu. Adiabatic rotation, quantum search, and preparation of superposition states. Physical Review A, 75:062337, 2007.DOI
- [12]G. Schaller. Adiabatic preparation without quantum phase transitions. Physical Review A, 78:032328, 2008.DOI
- [13]M. B. Hastings. Topology and phases in fermionic systems. Journal of Statistical Mechanics: Theory and Experiment, 2008(01):L01001, jan 2008.DOI
- [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]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]Michael Hofmann and Gernot Schaller. Probing nonlinear adiabatic paths with a universal integrator. Phys. Rev. A, 89:032308, Mar 2014.DOI
- [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]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]M. Born and V. Fock. Beweis des Adiabatensatzes. Zeitschrift für Physik, 51:165, 1928.DOI
- [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]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]Marko Znidaric and Martin Horvat. Exponential complexity of an adiabatic algorithm for an NP-complete problem. Physical Review A, 73:022329, 2006.DOI
- [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]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]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]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]Jérémie Roland and Nicolas J. Cerf. Quantum search by local adiabatic evolution. Physical Review A, 65:042308, Mar 2002.DOI
- [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]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]Vamsi Kalapala and Cris Moore. The phase transition in Exact Cover. Chicago Journal of Theoretical Computer Science, 2008(5), October 2008.
- [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]Bingzhi Zhang, Akira Sone, and Quntao Zhuang. Quantum computational phase transition in combinatorial problems. npj Quantum Information, 8:87, 2022.DOI
- [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]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]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]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.
- [38]Donald E. Knuth. Dancing links, pages 187–214. 2000.
- [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.
- [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
- [41]Andrew M. Childs, Edward Farhi, and John Preskill. Robustness of adiabatic quantum computation. Phys. Rev. A, 65:012322, Dec 2001.DOI
- [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.
- [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
- [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
- [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
