CHAPTER 3

Quantum Search

Computational search and optimization problems are ubiquitous in robotics. Computer vision has the classical challenge of scene segmentation, a search through possible visual interpretations of the world. Robot planning has the fundamental challenge of searching through sequences of plan operators to formulate plans for robot action in an environment. Classically, many planning problems are NP-complete or even PSPACE, which makes general purpose planning difficult. Robot (Machine) Learning often requires searching through feature spaces extracted from data, optimizing parameters of a model, and processing large amounts of data. Controls and manipulation have their own share of search and optimization challenges: searching through possible robot configuration spaces, optimizing kinematic settings for manipulators, and reasoning over environment dynamics.

A fundamental improvement in search algorithms can likely improve intelligence capabilities in a large number of traditional robotic challenges. Many classical robotic algorithms are expected to receive quadratic or exponential speedups from advances in quantum search.

In the quantum literature, Grover’s algorithm and Adiabatic Quantum Optimization are principal mechanisms of speedup for search algorithms. The vanilla version of Grover’s algorithm (previously covered in Section 2.5.3) involves search for elements in an unsorted list and requires quadratically fewer queries in the worst case than classical exhaustive search. Attempts have been made to extend Grover’s algorithm to search over trees and graphs both with and without heuristic information [Tarrataca and Wichert, 2011]. The case where heuristic information is not available is known as “uninformed” search, while the use of heuristic information makes searches “informed.” This chapter will highlight several of these approaches.

Additionally, quantum annealing techniques have been applied to various difficult search, navigation, and planning problems. The methods have been evaluated on current quantum adiabatic hardware [Rieffel et al., 2015, Smelyanskiy et al., 2012].

3.1 UNINFORMED GROVER TREE SEARCH

Grover Tree Search [Tarrataca and Wichert, 2011] extends Grover’s algorithm to search over paths in a tree structure. We first consider the “uniformed” search case, where heuristic information is not available for the tree search.

Imagine one has a tree structure like the one shown in Figure 3.1. In a robot planning context, the nodes in the tree could correspond to possible robot-environment states and the links between nodes correspond to decisions or actions the robot can execute at each state node.

Figure 3.1: Example search tree over sequential actions for robotic planning.

Taking an action A_i at a parent state node S_j takes the robot to a particular child state node S_k in the tree. The aim of a robot planning problem may be to find a path from the start (root) node of the tree to a particular goal state node somewhere else in the tree.

A path from the root node to a child node in the tree can be represented using a bit string specifying the robot’s action sequence. For example, to get from state S₁ to state S₄, the robot must choose action A₀ at S₁ to get to state S₂ and then action A₀ again at state S₂ to transition to state S₄. The bit string “00” can be used to indicate this sequence of actions taken. In similar fashion, the path from state S₁ to state S₆ can be represented by the bit string “10.”

For a path of depth d, the action identifier string is d elements long. For a tree with constant branching factor b, the tree will have b^d paths to depth d. If each element requires n bits to represent, every action identifier string requires nd bits.

Consider the equal weight superposition:

The items in the database are a listing of all possible action identifier strings, each representing a possible path through the tree. The sought element is the action string that specifies a path from the start to a goal node. Grover’s algorithm can be applied to this equal weight superposition to find the element in the database corresponding to the solution path.

Applying Grover’s algorithm for O() iterations returns the solution path with high probability when the quantum system is subsequently measured. Classical tree search, in the worst case, requires a brute force search over all O(b^d) paths. Grover Tree Search thus provides a quadratic speedup (in the worst case) over classical tree search when the branching factor is constant.

Non-constant branching factor can pose a challenge for Grover Tree Search. Grover’s algorithm operates on an exponentially generated database of all possible action bit strings. When the branching factor is not constant, the full superposition database will contain paths that do not actually exist in the tree. Pruning these infeasible paths requires additional book-keeping. In fact, when there are many infeasible paths, Grover Tree Search does not always provide a speedup over a brute force classical tree search. For further details, we recommend reading [Tarrataca and Wichert, 2011], which provides a rigorous complexity analysis for when Grover Trees Search speedups hold in comparison to classical uninformed tree search.

3.2 INFORMED QUANTUM TREE SEARCH

Heuristic information, when available, can provide practical speedups for many search problems on classical computers. In classical Artificial Intelligence, cost functions of the following form are often considered for informed search [Russell and Norvig, 2003]:

Here g(n) represents the search cost incurred to reach a particular node n, and h(n) is a heuristic estimate to reach the goal from node n. This type of cost function forms the principle behind classical A* and other such informed-search algorithms. If h(n) is an admissible heuristic (that is, if it never overestimates the true cost to the goal), then such algorithms will be optimal.

Using Grover’s algorithm, search problem candidate solutions are represented with qubits, and the probability of a particular candidate solution being returned is encoded in the weights of the superposition of qubits. One can incorporate some heuristic information by defining operators that act on quantum states to modify the weights in the superposition [Tarrataca and Wichert, 2011].

A key challenge of incorporating heuristic information into Grover Tree Search (or other search algorithms) is that state evolution in quantum mechanics has to be unitary. Recall that a unitary matrix U must satisfy U^†U = UU^† = I. To implement the state evaluation function f (x) in the quantum world, it must be represented as a unitary operator.

Since the heuristic function h(x) estimates remaining distance to the goal, one can consider states whose f (n) < T (a threshold) and remove others from the search. Using this idea, one can define the unitary operator:

This unitary operator considers an input action bit string that is represented as qubits, |a₁a₂ … a_d up to a particular depth d. The operator sets the value of a flag qubit |b. The phase of |b is maintained if the cost function value is above a threshold, and the phase is flipped otherwise. Heuristic information enters the search process through the setting of the threshold T for different nodes and paths. The choice of T is an important parameter for U, and how to choose it in the general case remains to be explored. In practice, Tarrataca and Wichert [2011] suggest using quantiles or other statistical approaches on known properties of the search space.

The proposed method of encoding heuristic information in quantum search has different optimality properties from classical A*, depending on choice of T. In addition, it does not circumvent the problem of comparing multiple paths. Using this approach for encoding heuristic information into Grover Tree Search, some speedups have been proven analytically for some 8-puzzle problem instances [Tarrataca and Wichert, 2011].

3.3 APPLICATION OF QUANTUM ANNEALING TO STRIPS CLASSICAL PLANNING

Another approach to quantum search is utilization of quantum adiabatic hardware. Quantum annealing approaches have been developed to help address difficult search and classical planning problem frameworks such as STRIPS [Rieffel et al., 2015, Smelyanskiy et al., 2012].

3.3.1 CLASSICAL STRIPS PLANNING

STRIPS [Fikes and Nilsson, 1971] is a classical framework (developed in 1971 at SRI International) for robot planning problems. STRIPS is grounded in propositional logic that allows a robot to reason logically about what actions it can take from a start state to reach an end goal state.

A STRIPS instance consists of an initial specified state for the robot/environment, a set of goal states the planner is trying to reach, and a set of actions a robot may take. The planner plans from the initial state to one or many goal states using the set of actions. Each action consists of a set of binary preconditions specifying the state of the world/robot that must be true before the action can be taken and a set of binary postconditions specifying what is true for the world/robot after the action is taken.

Frameworks such as Planning Domain Definition Language (PDDL) allow specification and solution of STRIPS-encoded planning problems of various sizes [McDermott et al., 1998]. In general, however, deciding whether any plan exists for a STRIPS problem instance is PSPACE-complete [Bylander, 1994].

3.3.2 APPLICATION OF QUANTUM ANNEALING TO STRIPS PLANNING

Quantum adiabatic hardware currently accepts problems that are in Quadratic Unconstrained Binary Optimization (QUBO) form (as discussed in Section 2.5.5). Thus, search and planning problems must be parameterized as QUBOs so that a solution can be achieved with adiabatic hardware. Rieffel et al. [2015] suggests two ways that a STRIPS instance can be mapped onto quantum adiabatic machines: (1) the Time Slice Approach and (2) the Conjunctive Normal Form (CNF) Approach.

Time Slice Approach

In the Time Splice approach, the plan length L must be known in advance. Optimization is performed over possible plans of length L that achieve all goals. An overall cost function is specified as:

Equation (3.4) represents a summation of Hamiltonian terms that form an overall Hamiltonian. The detailed definition of these terms is described in Table 3.1.

Table 3.1: Time slice approach to formulating STRIPS as QUBO

represents one of L binary predicate state variables at a particular time t. is 1 if the robot is in the i-th state at time t and 0 otherwise. represent one of M actions in the planning problem. y_j is 1 if the robot takes action j at time t and 0 otherwise. I ⁽⁺⁾ represents the set of state variables that are 1 (true) in the initial state, and I ⁽⁻⁾ represents the set of those that are 0 (false) in the initial state. G ⁽⁺⁾ is the set of goal state variables with value 1, and G ⁽⁻⁾ is the set of those with value 0. represents the set of preconditions set to 1 for action j, while represents the set of preconditions set to 0 for that action. represents the set of effects set to 1 for action j, while represents the set of effects set to 0 for that action.

The terms in Equation (3.4) serve different purposes. H_initial and H_goal encode the initial and goal states respectively, providing a penalty when the conditions of the initial and goal states are not met. H_precond and H_effects penalize violation of preconditions and inapplicable effects in order to choose coherent action sequences to get from the start to the goal. H_no−op penalizes state variable changes, helping prevent state changes that are not the result of an action to aid stability in the optimization.

The model assumes one action per time step. Additional terms can be added to allow the robot to perform multiple actions at a time step. The equations can also be simplified for specific navigation or scheduling problems. Jointly, Equation (3.4) and Table 3.1 define a QUBO that can be deployed on adiabatic hardware.

Conjunctive Normal Form (CNF) Approach

A Conjunctive Normal Form (CNF) expression is a set of clauses {C_a}. Each clause C_a consists of members from a set of n Boolean variables {z_i} that are logically-ORed together. Different clauses can have different numbers of variables. To solve a CNF expression, all the clauses must be satisfied.

SATPLAN [Kautz and Selman, 2006] is a classical planning approach that converts a STRIPS planning problem to equivalent CNF. SATPLAN also prunes the CNF for various logical inconsistencies.

A CNF produced by SATPLAN defines a Polynomial Unconstrained Binary Optimization (PUBO) instance, a generalization of QUBO where the objective function is a pseudo-Boolean function of arbitrary degree. For each clause in the CNF, there is a term in the PUBO instance. Higher-order degree terms are iteratively replaced with ancillary variables. Variables are iteratively removed until the PUBO is quadratic. The resulting QUBO instance is deployed on quantum adiabatic hardware.

Reported Comparisons

In their experiments, Rieffel et al. [2015] find that the Time Slice and CNF approaches are relatively comparable. The generated QUBO instances are similar in size and their empirical performance on adiabatic hardware is similar, though the Time Slice is more scalable for certain situations. The quantum annealing approach shows promise, though current limitations of quantum hardware make this quantum planning approach not yet competitive with the best classical implementations of STRIPs solvers.

3.4 CHAPTER SUMMARY

Table 3.2: Summary of quantum operating principles in discussed quantum search methods