Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms

Let $𝒫$ be a combinatorial problem and let $I$ be an instance of $𝒫$ of size $n$. The dynamic programming paradigm for algorithm design can often be applied to compute a solution $\mathrm{sol}(I)$ of $I$ for $𝒫$, if $𝒫$ satisfies the optimal substructure property, i.e., an optimal solution for $I$ can be decomposed into (interchangeable) optimal solutions for subinstances of $I$, and the recursive computations of solutions for larger instances require solutions for overlapping subproblems – unlike most divide-and-conquer algorithms, in which the subproblems do not overlap. The underlying idea of (bottom-up) dynamic programming is to create a table $D$, which stores the (values of) optimal solutions for all relevant subinstances of $I$, starting from the smallest ones and then computing optimal solutions for larger and larger subinstances by suitably combining the existing solutions of smaller subinstances. Often, the construction of $\mathrm{sol}(I)$, given $D$, is a simple task¹¹1The solution $\mathrm{sol}(I)$ of the actual instance $I$ is frequently found in the “last” cell of $D$. Such entry is later denoted as $D[i_1^{\ast }][i_2^{\ast }]\mathrm{\dots }[i_k^{\ast }]$.. Therefore, the time and space complexity for solving $𝒫$ are asymptotically bounded by those of constructing and storing $D$, respectively. In particular, the construction time of $D$ can be easily upper bounded by multiplying its size by the time required to recursively compute each table entry. For instance, a table $D$ of size $n^2$ and a linear-time computation for each entry yield a running time of $O(n^3)$.

Quantum dynamic programming algorithms have recently attracted considerable interest in the exponential-time regime (which we review later). Surprisingly, instead, polynomial-time quantum algorithms have not yet received as much attention, despite the potential for significant speedups in practical applications. Khadiev and Safina [45] proposed polynomial-time quantum dynamic programming algorithms for solving problems on directed acyclic graphs (DAGs). Furrow [30] gives a polynomial-time quantum dynamic programming algorithm for the Coin Change problem and for the Maximum Subarray Sum²²2It is worth remarking that, as discussed in [30], the proposed algorithm, albeit based on computing an auxiliary table, is not solved via dynamic programming, but rather by following a greedy approach. problem.

The pioneering work by Ambainis et al. [4] introduced two quantum dynamic programming frameworks that provide a novel approach for speeding up some exponential-time classical dynamic programming algorithms, developed to address NP-complete problems. Both frameworks use classical computation to construct partial dynamic programming tables, stored in QRAM, to be accessed via quantum search subroutines. The first, and simpler, framework addresses a subclass of set problems where the solution for a set $S$ of size $n$ can be determined by considering all partitions of $S$ into two sets of sizes $k$ and $n-k$ (for any positive integer $k$), and by selecting the optimal option. In this setting, a quantum advantage is obtained by suitably selecting the subset of the entries to be classically precomputed so as to balance the time needed to compute the solution (obtained by identifying optimal combinations of subsets) to the problem by performing (bounded-depth) recursive quantum search primitives. For instance, this framework allows to obtain fast exponential-time quantum algorithms for Traveling Salesman [4], for One-Sided Crossing Minimization [13, 14]³³3A quantum algorithm for Two-Sided Crossing Minimization, solely based on Grover’s search, has been presented in [17, 15]., for Graph Coloring [53], and for Dynamic programming across the subset [56]. The second, more complex, framework is based on the ability of efficiently solving a Path in the Hypercube (PHC) problem. Given a subgraph $G$ of the Boolean hypercube, where edges are directed from vertices of lower Hamming weight to vertices of higher Hamming weight, the problem asks to determine if there exists a directed path in $G$ from the vertex $0^n$ to the vertex $1^n$. In this setting, a quantum advantage is reached by combining the access to precomputed partial dynamic programming tables, with recursive applications of the quantum algorithm solving PHC. For instance, this framework allows to obtain fast exponential-time quantum algorithms for Domatic Number [6] and for Treewidth Computation [48]. Furthermore, Glos et al. [36] generalized this framework to a quantum algorithm for finding a path in $n$-dimensional lattice graphs.

While exponential-time quantum algorithms aim to tackle problems beyond the reach of classical computation, polynomial-time quantum algorithms can provide substantial efficiency gains for problems already considered tractable. In this work, we focus on polynomial-time quantum algorithms and introduce a framework that systematically extends classical dynamic programming algorithms into accelerated quantum counterparts, by harnessing quantum parallelism and amplitude amplification. Specifically, we developed quantum subroutines that integrate quantum search primitives, such as min, max, find, and findAll, within a dynamic programming context. These subroutines construct a superposition enabling access to the specific subset of previously computed entries, stored in a Quantum Random Access Memory (QRAM), that is needed for computing the currently-considered entry. This, in turn, enables us to harness the full potential of quantum search primitives by restricting the search space to the relevant candidates.

To demonstrate the broad usability of our framework, we apply it to several well-known problems for which the best worst-case classical algorithms rely on dynamic programming; see Table 1. For space reasons, in this paper, we only discuss in detail the application of the framework to the Single-Source Shortest Path and Membership in Context-Free Language problems. The applications to the remaining problems in Table 1 are presented in the full version of the paper [16].

Given two $k$-tuples of integers, $⟨a_1,a_2,\mathrm{\dots },a_k⟩$ and $⟨b_1,b_2,\mathrm{\dots },b_k⟩$, we say that $⟨a_1,a_2,\mathrm{\dots },a_k⟩$ lexicographically precedes $⟨b_1,b_2,\mathrm{\dots },b_k⟩$, denoted by $⟨a_1,a_2,\mathrm{\dots },a_k⟩\prec ⟨b_1,b_2,\mathrm{\dots },b_k⟩$, if there exists an index $j\in \{1,2,\mathrm{\dots },k\}$ such that $a_i=b_i$ for all , and . The relation $\prec$ defines a total order among the $k$-tuples of integers. Given a directed graph $G=(V,E)$, we denote by $\mathrm{deg}(v)$ the degree of a vertex $v$ of $G$, that is, the number of arcs in $E$ having $v$ as their tail or head. Moreover, we denote by ${\mathrm{deg}}_{out}(v)$ the outdegree of a vertex $v$ of $G$, that is, the number of arcs in $E$ having $v$ as their tail. The average degree of $G$ is $\delta =\frac{1}{n}{\sum }_{v\in V(G)}\mathrm{deg}(v)=\frac{2m}{n}$. In order to simplify the notation, we use $[h]$ to denote the set $\{0,\mathrm{\dots },h-1\}$, where $h$ is a positive integer. Also, given positive integers $a$ and $b$, we denote $\lceil \frac{a}{b}\rceil$ as $\frac{a}{b}$ and $\lceil \log a\rceil$ as $\log a$. If $f(n)=O({\log }^{c}n)$ for some constant $c$, we write $f(n)=polylog(n)$. In case $f(n)=O(n^{d}polylog(n))$ for some constant $d$, we use the notation $f(n)=\tilde{O}(n^d)$ (see, e.g., [59]).

A combinatorial search problem $𝒫$ is a triple $⟨\mathrm{\Lambda },S,R⟩$, where:

• $\mathrm{■}$

  $\mathrm{\Lambda }$ is the set of instances of $𝒫$;

• $\mathrm{■}$

  $S$ is the set of solutions of $𝒫$; and

• $\mathrm{■}$

  $R\subseteq \mathrm{\Lambda }\times S$ is a binary relation that associates each instance $I\in \mathrm{\Lambda }$ with a set $SOL(I)=\{s\in S:(I,s)\in R\}$. The elements in $SOL(I)$ are the feasible solutions of $𝒫$ for $I$.

A combinatorial optimization problem $𝒫$ is a quintuple $⟨\mathrm{\Lambda },S,R,f_{𝒫},g⟩$, where:

• $\mathrm{■}$

  $⟨\mathrm{\Lambda },S,R⟩$ is a combinatorial search problem,

• $\mathrm{■}$

  $f_{opt}:S\to Y$ is the optimization function, where $Y$ is a totally ordered set (usually $Y\in \{\mathbb{N},ℝ\}$);

• $\mathrm{■}$

  $g:2^S\to S$ is the comparator function, with $g\in \{\min ,\max \}$.

An optimal solution of $𝒫$ for $I$ is any feasible solution $s^{\ast }$ in $SOL(I)$ such that $s^{\ast }=\arg {\min }_{s\in SOL(I)}{f}_{opt}(s)$, if $g=\min$, and $s^{\ast }=\arg {\max }_{s\in SOL(I)}{f}_{opt}(s)$, if $g=\max$. For ease of notation, in the following, we denote by $\mathrm{sol}(I)$, both a feasible solution of a combinatorial search problem and an optimal solution of a combinatorial optimization problem. Also, we refer to combinatorial search/optimization problems simply as combinatorial problems.

Let $𝒫$ be a combinatorial problem and let $I$ be an instance of $𝒫$. A (bottom-up) dynamic programming algorithm for $𝒫$ can be implemented by executing the following steps:

Whereas the efficiency of this algorithm design paradigm lies in the fact that solutions of overlapping problems are stored in the table and hence need to be computed only once, its correctness lies in the fact that “difficult” entries can be computed by exploiting the values of previously computed (“easy” and “difficult”) entries (by the optimal substructure property). Clearly, the Table Update is the most interesting and challenging step in the overall approach. Fortunately, many optimization problems $𝒫$, including those considered in this paper, naturally exhibit a simple recursive formulation for the entries of their dynamic programming table $D$. Consider an entry $D[i_1][i_2]\mathrm{\dots }[i_k]$ of $D$. Let $S_{i_1,i_2,\mathrm{\dots },i_k}$ be the dependency set of $D[i_1][i_2]\mathrm{\dots }[i_k]$, composed of the indices of the entries of $D$ on which the computation of the entry $D[i_1][i_2]\mathrm{\dots }[i_k]$ depends. Observe that $S_{i_1,i_2,\mathrm{\dots },i_k}$ is some subset of ${\mathbb{N}}^k$ such that for each entry $⟨j_1,j_2,\mathrm{\dots },j_k⟩$ in $S_{i_1,i_2,\mathrm{\dots },i_k}$ we have that $⟨j_1,j_2,\mathrm{\dots },j_k⟩\prec ⟨i_1,i_2,\mathrm{\dots },i_k⟩$. Then, the recursive formula for $D[i_1][i_2]\mathrm{\dots }[i_k]$ is of the form:

where: (1) $\mathrm{op}\in \{\min ,\max ,\mathrm{find},\mathrm{findAll}\}$; (2) $C_{i_1,i_2,\mathrm{\dots },i_k}$ is a set, called generating set, composed of $h$-element subsets of $S_{i_1,i_2,\mathrm{\dots },i_k}$, where each subset provides the input to construct a particular candidate value for $D[i_1][i_2]\mathrm{\dots }[i_k]$ (where $h$ is an integer constant, called dependency index, determined by $𝒫$, which specifies the number of subinstances into which each instance is divided in the recursive definition); (3) $f_{𝒫}$ is a function specific for problem $𝒫$ that computes a candidate value for $D[i_1][i_2]\mathrm{\dots }[i_k]$, assuming that all entries of $D$ with indices in $S_{i_1,i_2,\mathrm{\dots },i_k}$ have already been computed.

In most problems, the dependency index is a small integer, usually equal to 1 or 2. A textbook example of a problem fitting Equation 1 with $h=1$ is the Coin Change problem [47]. Given a set of positive integer coin denominations and a target sum $T$, the goal is to achieve $T$ using the fewest possible number of coins, assuming an unlimited supply of each denomination, or determine if it is not possible to obtain $T$. Let $D$ be a dynamic programming table of size $T+1$, whose entries $D[i]$ represent the minimum number of coins needed to make up the sum $i$, with $D[i]=\mathrm{\infty }$ if it is not possible. The base case of the dynamic programming approach is $D[0]=0$. For the recursive case, to compute $D[i]$ for $i>0$, we have to consider all possible choices for the first coin. Once the first coin is selected, the remaining amount must be reached optimally. This can be expresses by the recursive formula

Clearly, the recursive case of Equation 2 matches the pattern of Equation 1. In fact, we can set $S_i=\{j:c_j\le i\}$, $C_i=\{\{j\}:c_j\le i\}$, $h=1$, and $f_{𝒫}(i,\{j\})=1+D[i-c_j]$.

A notable example of a problem fitting Equation 1 with $h=2$ is the Matrix Chain Multiplication problem. Given a sequence of $n$ matrices, $A_1,A_2,\mathrm{\dots },A_n$, and their dimensions $p_0,p_1,p_2,\mathrm{\dots },p_n$, where for $i=1,2,\mathrm{\dots },n$, matrix $A_i$ has dimension $p_{i-1}\times p_i$, the problem asks to determine the order of matrix multiplications that minimizes the total number of scalar multiplications needed to obtain $A_1\times A_2\times \mathrm{\cdots }\times A_n$. Note that, in the Matrix Chain Multiplication problem, we are not actually multiplying matrices; instead, the goal is only to determine an order for multiplying matrices that has the lowest cost. Recall that matrix multiplication is associative, therefore we aim at grouping the above multiplications to minimize the total number of scalar multiplications.

Let $D$ be a dynamic programming table of size $n\times n$, whose entries $D[i][j]$, with $1\le i\le j\le n$, store the minimum number of scalar multiplications needed to compute the product $A_i\times A_{i+1}\times \mathrm{\cdots }\times A_j$. The base case of the dynamic programming approach is $D[i][i]=0$. For the recursive case, to compute $D[i][j]$ for $j>i$, we have to consider all possible choices to split the product at a matrix $A_k$, with . This can be expressed by the recursive formula:

Clearly, the recursive case of Equation 3 matches the pattern of Equation 1. In fact, we can set , , $h=2$, and $f_{𝒫}(i,j,\{(i,k),(k+1,j)\})=D[i][k]+D[k+1][j]+p_{i-1}{p}_k{p}_j$.

The first subroutine prepares a uniform superposition ${\mathrm{\Psi }}_{i_1,i_2,\mathrm{\dots },i_k}$ of the integers in $[{\lambda }_{i_1,i_2,\mathrm{\dots },i_k}]$; see the pseudocode of Algorithm 1. It assumes the existence of a classical procedure $f_C$ that determines ${\lambda }_{i_1,i_2,\mathrm{\dots },i_k}$ given the values $i_1,i_2,\mathrm{\dots },i_k$. The subroutine starts with the register $|i_1{i}_2\mathrm{\dots }{i}_k⟩$ and with a register storing an $\mathrm{\ell }$-bit zero string $|0^{\mathrm{\ell }}⟩$ (where the value of $\mathrm{\ell }$ will be discussed later). It exploits the quantum gate $U_{\lambda }$ to determine ${\lambda }_{i_1,i_2,\mathrm{\dots },i_k}$ and prepares the state $|i_1{i}_2\mathrm{\dots }{i}_k⟩|{\lambda }_{i_1,i_2,\mathrm{\dots },i_k}⟩$. Then, the subroutine takes in input an additional register storing a $\log ({\lambda }_{i_1,i_2,\mathrm{\dots },i_k})$-bit zero string and applies Hadamard gates to each of the qubits of such a register to prepare the uniform superposition state:

We use the signature StatePrep($i_1,i_2,\mathrm{\dots },i_k$) to denote calls to the subroutine StatePrep.

The second quantum subroutine prepares the state $|E_{i_1{i}_2\mathrm{\dots }{i}_k,u}⟩$ that correlates the integers in $[{\lambda }_{i_1,i_2,\mathrm{\dots },i_k}]$ with the elements of $C_{i_1{i}_2\mathrm{\dots }{i}_k}$; see the pseudocode of Algorithm 2. Our quantum subroutine assumes the existence of a classical injective function $\gamma :{\mathbb{N}}^k\times \mathbb{N}\to C_{i_1{i}_2\mathrm{\dots }{i}_k}$ that maps the pair $⟨⟨i_1{i}_2\mathrm{\dots }{i}_k⟩,u⟩$ to an element of $C_{i_1{i}_2\mathrm{\dots }{i}_k}$. Observe that the elements of $C_{i_1,i_2,\mathrm{\dots },i_k}$ admit a binary representation $bin(𝒳)$ of length $h\cdot \sigma$. The subroutine starts with the register $|i_1{i}_2\mathrm{\dots }{i}_k⟩$, the register $|u⟩$, and with a register storing an $(h\cdot \sigma )$-bit zero string $|0^{h\cdot \sigma }⟩$ and uses $U_{\gamma }$ to prepare the state:

We use the signature TableIndexPrep($i_1,i_2,\mathrm{\dots },i_k,u$) to denote calls to the subroutine TableIndexPrep.

The third quantum subroutine uses either (i) the quantum min/max finding algorithms (QMin and QMax) due to Dürr and Høyer [23], or (ii) the quantum finding algorithm (QFind) due to Grover to search for an item satisfying a condition in an unsorted list [1] or (iii) the quantum finding algorithm (QFindAll) due to Ambainis to search for all items satisfying a condition in an unsorted list [3]. In particular, QMin and QMax allow to determine the element in a ground set of size $N$ that minimizes/maximizes a given function in $\tilde{O}(\sqrt{N})$ time, QFind (resp. QFindAll) allows to determine an element (resp. all the elements) in a ground set of size $N$ that satisfy a certain condition in $\tilde{O}(\sqrt{N})$ time (resp. $\sqrt{NM}$ time, where $M$ is the number of elements satisfying the condition).

The subroutine (see the pseudocode of Algorithm 3) takes as input at least: (1) the integers $i_1,i_2,\mathrm{\dots },i_k$; (2) the function $f_{𝒫}$; and (3) an operator $\mathrm{op}\in \{\min ,\max ,\mathrm{find},$ $\mathrm{findAll}\}$. Furthermore, if $\mathrm{op}\in \{\min ,\max \}$, it additionally takes as an input a comparator, $⋖$, to maximize (or minimize) over, that defines a total ordering of the values in the codomain of $f_{𝒫}$ (i.e., the values stored in $D$). First, the subroutine invokes StatePrep $(i_1,i_2,\mathrm{\dots },i_k)$ to prepare the superposition state $|{\mathrm{\Psi }}_{i_1,i_2,\mathrm{\dots },i_k}⟩$ and then applies TableIndexPrep, in parallel to each basis state of $|{\mathrm{\Psi }}_{i_1,i_2,\mathrm{\dots },i_k}⟩$, to prepare the superposition state:

Observe that each of the states $|i_1,i_2,\mathrm{\dots },i_k⟩|{\lambda }_{i_1,i_2,\mathrm{\dots },i_k}⟩|u⟩|\gamma (⟨i_1,i_2,\mathrm{\dots },i_k⟩,u)⟩$ composing $|{\mathrm{\Phi }}_{i_1,i_2,\mathrm{\dots },i_k}⟩$ provides the input for computing, using $f_{𝒫}$ and the quantum search subroutines described above, a candidate value for $D[i_1][i_2]\mathrm{\dots }[i_k]$, that is, the registers $|i_1,i_2,\mathrm{\dots },i_k⟩$ and $|\gamma (⟨i_1,i_2,\mathrm{\dots },i_k⟩,u)⟩$. Therefore, the subroutine proceeds by applying the algorithm QMin, QMax, QFind, or QFindAll, depending on whether the chosen operator $\mathrm{op}$ is equal to $\min$ (or $\max$), $\mathrm{find}$, or $\mathrm{findAll}$, respectively, only to the candidate values for $D[i_1][i_2]\mathrm{\dots }[i_k]$ determined by the entries in $C_{i_1,i_2,\mathrm{\dots },i_k}$.

We use the signatures DP($i_1,i_2,\mathrm{\dots },i_k,f_{𝒫},op$) and DP($i_1,i_2,\mathrm{\dots },i_k,f_{𝒫},op,⋖$) to denote calls to the subroutine DP, when $\mathrm{op}\in \{\mathrm{find},\mathrm{findAll}\}$ or $\mathrm{op}\in \{\min ,\max \}$, respectively.

Altogether, we obtain the following main algorithmic theorem.

In the following, we describe the algorithm $Q_{𝒜}$ and prove its space and time complexity. We describe $Q_{𝒜}$ in terms of the three steps that implement the dynamic programming approach provided by $𝒜$.

As in the classical scenario, the algorithm starts by initializing a dynamic programming table $QD$ of size $d_1\times d_2\times \mathrm{\cdots }\times d_k$. Differently from the classical dynamic programming table $D$ used by $𝒜$, however, the table $QD$ is stored in QRAM. Suppose that each of the values of the entries of $D$ (and thus of $QD$) can be represented using $w$ bits. Let $f_{init}$ be the classical function that, provided with the tuple $⟨i_1,i_2,\mathrm{\dots },i_k⟩$ that addresses the entry $D[i_1][i_2]\mathrm{\dots }[i_k]$, computes the initialization value of $D[i_1][i_2]\mathrm{\dots }[i_k]$. To this aim, for each $⟨i_1,i_2,\mathrm{\dots },i_k⟩\in [d_1]\times [d_2]\times \mathrm{\cdots }\times [d_k]$, we provide the gate $U_{init}$ with the address register ${|i_1{i}_2\mathrm{\dots }{i}_k⟩}_a$ and with a data register storing a $w$-bit zero string $|0^w⟩$. The application of $U_{init}$ to these registers results in the state ${|i_1{i}_2\mathrm{\dots }{i}_k⟩}_a{|f_{init}(⟨i_1,i_2,\mathrm{\dots },i_k⟩)⟩}_d$, which forms the input for a QRAM write operation that initializes $QD[i_1][i_2]\mathrm{\dots }[i_k]$.

We process the tuples $⟨i_1,i_2,\mathrm{\dots },i_k⟩\in [d_1]\times [d_2]\times \mathrm{\cdots }\times [d_k]$ in lexicographic order. For each tuple $⟨i_1,i_2,\mathrm{\dots },i_k⟩$, the algorithm invokes either the quantum subroutine DP($i_1,i_2,\mathrm{\dots },i_k,f_{𝒫},op$) or DP($i_1,i_2,\mathrm{\dots },i_k,f_{𝒫},op,⋖$), based on whether $\mathrm{op}\in \{\mathrm{find},\mathrm{findAll}\}$ or $\mathrm{op}\in \{\min ,\max \}$, respectively. This allows us to compute ${\mathrm{op}}_{𝒳\in {𝒞}_{i_1,i_2,\mathrm{\dots },i_k}}{f}_{𝒫}(i_1,i_2,\mathrm{\dots },i_k,𝒳)$, which is stored in an output register ${|d_{i_1,i_2,\mathrm{\dots },i_k}⟩}_o$ correlated with the address register ${|i_1{i}_2\mathrm{\dots }{i}_k⟩}_a$. Finally, the state ${|i_1{i}_2\mathrm{\dots }{i}_k⟩}_a{|d_{i_1,i_2,\mathrm{\dots },i_k}⟩}_o$ forms the input for a QRAM write operation that updates $QD[i_1][i_2]\mathrm{\dots }[i_k]$.

Let $⟨i_1^{\ast },i_2^{\ast },\mathrm{\dots },i_k^{\ast }⟩$ be the entry of $D$ whose value determines the solution to $𝒫$. Then, a solution for $𝒫$ can be obtained by reading the entry $QD[i_1^{\ast }][i_2^{\ast }]\mathrm{\dots }[i_k^{\ast }]$.

Next, we analyze the space complexity of $Q_{𝒜}$. As in its classic counterpart, the space complexity of $Q_{𝒜}$ is asymptotically bounded by the storage requirement of the dynamic programming table, which can be upper bounded by multiplying the number of entries of $QD$, the number $w$ of bits to represent each of the values of the entries of $QD$ (i.e., the solutions to the subproblems of $𝒫$), and the maximum number $M$ of solutions of any subproblem of $𝒫$ for $I$. Also, recall that the entries of $QD$ are in one-to-one correspondence with the nodes of $G_{𝒫}(I)$. Therefore, the space complexity of $Q_{𝒜}$ is in $O(w(|V(G_{𝒫}(I))|)$, if $\mathrm{op}=\{\mathrm{find},\min ,\max \}$, and in $O\left((w\cdot M)|V(G_{𝒫}(I))|\right)$, if $\mathrm{op}=\mathrm{findAll}$.

Finally, we analyze the time complexity of $Q_{𝒜}$. Obviously, the time needed to compute function $f_{init}$ is in $O(T_{𝒫})$. Therefore, the time complexity $\mathrm{Time}(I)$ of $Q_{𝒜}$ on input $I$ is asymptotically bounded by the time required to execute the Table Update step. We now give the corresponding bound. For simplicity, we assume first that $\mathrm{op}\in \{\mathrm{find},\min ,\max \}$. Let $n=|V(G_{𝒫}(I))|$ and recall that $\delta$ denotes the average degree of $G_{𝒫}(I)$. In order to upper bound $\mathrm{Time}(I)$, we proceed as follows. For $i=1,\mathrm{\dots },\log \log n$, let $V_i$ be the subset of $V(G_{𝒫}(I))$ whose degree is between $2^{2^{i-1}}\delta$ and $2^{2^i}\delta$, and let $V_0$ be the subset of $V(G_{𝒫}(I))$ whose degree is less than $2\delta$. Recall that, by Theorem 3, the quantum subroutine DP determines a value of $f_{𝒫}$ for an entry $D[i_1][i_2]\mathrm{\dots }[i_k]$ in $\tilde{O}(T_{i_1,i_2,\mathrm{\dots },i_k}^{\prime }+T_{𝒫}\sqrt{{\lambda }_{i_1,i_2,\mathrm{\dots },i_k}})$ time, that $T_{i_1,i_2,\mathrm{\dots },i_k}^{\prime }\le T^{\prime }$, and that, for each node $n_{i_1,i_2,\mathrm{\dots },i_k}$ of $G_{𝒫}(I)$, it holds that ${\lambda }_{i_1,i_2,\mathrm{\dots },i_k}\le {\mathrm{deg}}_{out}(n_{i_1,i_2,\mathrm{\dots },i_k})$ since $𝒫$ is simple. Therefore, we have: