Too often, quantum computer scientists seek to create new algorithms entirely fresh from new cloth when there are extensive and optimized classical algorithms that can be generalized wholesale. At the same time, one may seek to maintain classical advantages of performance and runtime bounds, while enabling potential quantum improvement. Hybrid quantum algorithms tap into this potential, and here we explore a class of hybrid quantum algorithms called Iterative Quantum Algorithms (IQA) that are closely related to classical greedy or local search algorithms, employing a structure where the quantum computer provides information that leads to a simplified problem for future iterations. Specifically, we extend these algorithms beyond past results that considered primarily quadratic problems to arbitrary k-local Hamiltonians, proposing a general framework that incorporates logical inference in a fundamental way. As an application we develop a hybrid quantum version of the well-known classical Davis-Putnam-Logemann-Loveland (DPLL) algorithm for satisfiability problems, which embeds IQAs within a complete backtracking based tree search framework. Our results also provide a general framework for handling problems with hard constraints in IQAs. We further show limiting cases of the algorithms where they reduce to classical algorithms, and provide evidence for regimes of quantum improvement.
Too often, quantum computer scientists seek to create new algorithms entirely fresh from new cloth when there are extensive and optimized classical algorithms that can be generalized wholesale. At the same time, one may seek to maintain classical advantages of performance and runtime bounds, while enabling potential quantum improvement. Hybrid quantum algorithms tap into this potential, and here we explore a class of hybrid quantum algorithms called Iterative Quantum Algorithms (IQA) that are closely related to classical greedy or local search algorithms, employing a structure where the quantum computer provides information that leads to a simplified problem for future iterations. Specifically, we extend these algorithms beyond past results that considered primarily quadratic problems to arbitrary k-local Hamiltonians, proposing a general framework that incorporates logical inference in a fundamental way. As an application we develop a hybrid quantum version of the well-known classical Davis-Putnam-Logemann-Loveland (DPLL) algorithm for satisfiability problems, which embeds IQAs within a complete backtracking based tree search framework. Our results also provide a general framework for handling problems with hard constraints in IQAs. We further show limiting cases of the algorithms where they reduce to classical algorithms, and provide evidence for regimes of quantum improvement.
Quantum algorithms have been widely studied in the context of combinatorial optimization problems. While this endeavor can often analytically and practically achieve quadratic speedups, theoretical and numeric studies remain limited, especially compared to the study of classical algorithms. We propose and study an alternative class of hybrid approaches to quantum optimization, termed iterative quantum algorithms, which in particular generalizes the recursive quantum approximate optimization algorithm (QAOA). This paradigm can incorporate hard problem constraints, which we demonstrate by considering the maximum independent set (MIS) problem. We show that, for QAOA with p=1 circuit layers, this algorithm performs exactly the same operations and selections as the classical greedy algorithm for MIS. We then turn to deeper p>1 circuits and other ways to modify the quantum algorithm that can no longer be easily mimicked by classical algorithms, and empirically confirm improved performance. Our work demonstrates the practical importance of incorporating proven classical techniques into more effective hybrid quantum-classical algorithms.
One of the challenges of quantum computers in the near- and mid- term is the limited number of qubits we can use for computations. Finding methods that achieve useful quantum improvements under size limitations is thus a key question in the field. In this vein, it was recently shown that a hybrid classical-quantum method can help provide polynomial speed-ups to classical divide-and-conquer algorithms, even when only given access to a quantum computer much smaller than the problem itself. In this work, we study the hybrid divide-and-conquer method in the context of tree search algorithms, and extend it by including quantum backtracking, which allows better results than previous Grover-based methods. Further, we provide general criteria for polynomial speed-ups in the tree search context, and provide a number of examples where polynomial speed ups, using arbitrarily smaller quantum computers, can be obtained. We provide conditions for speedups for the well known algorithm of DPLL, and we prove threshold-free speed-ups for the PPSZ algorithm (the core of the fastest exact Boolean satisfiability solver) for well-behaved classes of formulas. We also provide a simple example where speed-ups can be obtained in an algorithm-independent fashion, under certain well-studied complexity-theoretical assumptions. Finally, we briefly discuss the fundamental limitations of hybrid methods in providing speed-ups for larger problems.
Iterative quantum optimization (IQO) uses quantum-generated information to select a sequence of classical problem reductions. We introduce Bound-Aware Tree-IQO which combines this iterative structure with bounds and reversible search. Feasible measured samples update a shared incumbent, while valid classical bounds prune branches that cannot improve it. Incorporating backtracking yields an anytime method that returns the best feasible solution found when interrupted, or can be run as a complete search to return and certify the optimum. For suitable single-variable or pairwise reductions, an initial IQO path can determine the branching schedule without further quantum calls, though certifying the optimum may take superpolynomial classical time. To motivate our framework, we prove two limitations of irreversible IQO reductions based on the quantum approximate optimization algorithm (QAOA). We show an infinite family of unweighted MaxCut instances on which globally optimized level-1 QAOA makes standard Recursive QAOA strictly prefer a first reduction that excludes every optimal solution, and limits that branch to an approximation ratio of at most 2/3+o(1). In contrast, a single backtrack recovers an optimal solution using the same quantum information. Causal cone arguments give a complementary obstruction at every fixed depth of standard QAOA: a weighted MaxCut instance is shown to contain two edges with identical two-qubit reduced states, even though every optimum requires opposite edge parities. MaxCut experiments show that QAOA-guided ordering is nonrandom in exact-certification tests through n=28, while demonstrating that quantum samples can strengthen the incumbent and enable further pruning. Our results suggest that quantum data could provide useful guidance toward solving hard combinatorial optimization problems more effectively than either quantum or classical algorithms alone.
While the development of quantum computers promises a myriad of advantages over their classical counterparts, care must be taken when designing algorithms that substitute a classical technique with a potentially advantageous quantum method. The probabilistic nature of many quantum algorithms may result in new behavior that could negatively impact the performance of the larger algorithm. The purpose of this work is to preserve the advantages of applying quantum search methods for generalized pattern search algorithms (GPSs) without violating the convergence criteria. It is well known that quantum search methods are able to reduce the expected number of oracle calls needed for finding the solution to a search problem from O(N) to O(N) However, the number of oracle calls needed to determine that no solution exists with certainty is exceedingly high and potentially infinite. In the case of GPS, this is a significant problem since overlooking a solution during an iteration will violate a needed assumption for convergence. Here, we overcome this problem by introducing the quantum improved point search (QIPS), a classical–quantum hybrid variant of the quantum search algorithm QSearch. QIPS retains the O(N) oracle query complexity of QSearch when a solution exists. However, it is able to determine when no solution exists, with certainty, using only O(N) oracle calls.
This thesis presents two main projects focused on hybrid quantum search algorithms. The first, Particle-Guided Grover's Search, applies Bayesian inference to quantum search when the number of solutions is a priori unknown. It begins with a prior distribution that encodes our initial "beliefs" about the true number of solutions in the search space, and recursively updates these beliefs using Bayesian inference. Measurement outcomes of the quantum search that do not yield a solution are interpreted as "evidence", guiding the Bayesian update to determine the optimal number of Grover iterations for subsequent rounds. This approach leverages Particle Filtering -- a Bayesian filtering technique -- to avoid explicitly storing the entire prior distribution at each step. Instead of requiring O(N) memory, the method draws a set of "particles" from the prior and updates their associated weights as quantum search failures accumulate. Particle filtering also offers the advantage of incorporating information from all past failures, rather than only the most recent one. The algorithm's performance is benchmarked against a prior work. The second project, Runtime--Coherence Trade-offs for Hybrid SAT Solvers, is focused on a class of hybrid k-SAT solvers. These solvers are based on a well-known random walk technique called Schoening's algorithm, which uses two sources of randomness to perform a local search over the space of all assignments for a k-SAT problem. In this project, we assume that these sources of randomness are encoded into a long bitstring, allowing the random walk to be interpreted as a deterministic function mapping each bitstring to either 0 or 1, depending on whether the walk successfully finds a satisfying assignment. This functional perspective enables us to pose the question: Given a bound on the coherence time of a quantum computer, which portion of the bitstring should we search coherently, and which portion should be left to classical search? We address this question by introducing a family of hybrid algorithms called "partial Groverizations", which strategically combine quantum and classical resources. We analyze the runtime performance of this family as a function of the available quantum coherence time. The results of this work have been published in IEEE Transactions on Quantum Engineering.
Constraint programming (CP) is a paradigm used to model and solve constraint satisfaction and combinatorial optimization problems. In CP, problems are modeled with constraints that describe acceptable solutions and solved with backtracking tree search augmented with logical inference. In this paper, we show how quantum algorithms can accelerate CP, at both the levels of inference and search. Leveraging existing quantum algorithms, we introduce a quantum-accelerated filtering algorithm for the alldifferent global constraint and discuss its applicability to a broader family of global constraints with similar structure. We propose frameworks for the integration of quantum filtering algorithms within both classical and quantum backtracking search schemes, including a novel hybrid classical-quantum backtracking search method. This work suggests that CP is a promising candidate application for early fault-tolerant quantum computers and beyond.