Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams
Seiichiro Tani





The spin-forbidden vacuum-ultraviolet absorption spectrum of ^14N^15N
    W. Ubachs
    December 30, 2023
=====================================================================

empty

An ordered binary decision diagram (OBDD) is 
a directed acyclic graph that represents a Boolean function.
OBDDs are also known as special cases of oblivious read-once branching programs
in the field of complexity theory. Since OBDDs have many nice properties as data structures,
they have been extensively studied for decades in both theoretical and practical fields,
such as VLSI design, formal verification, machine learning, and combinatorial problems.
Arguably, the most crucial problem in using OBDDs is that
they may vary exponentially in size depending on their variable ordering (i.e., 
the order in which the variables are to read) when they represent the same function.
Indeed, it is NP hard to find an optimal variable ordering that minimizes an OBDD
for a given function.
Hence, numerous studies have sought heuristics to find an optimal variable ordering.
From practical as well as theoretical points of view,
it is also important to seek algorithms that output optimal solutions
with lower (exponential) time complexity
than trivial brute-force algorithms do.  
Friedman and Supowit provided a clever deterministic algorithm with time/space complexity
O^∗(3^n), where n is the number of variables of the function,
which is much better than the trivial brute-force bound O^∗(n!2^n).
This paper shows that a further speedup is possible with quantum computers
by demonstrating the existence of
 a quantum algorithm
that produces a minimum OBDD together with the corresponding variable ordering
in O^∗(2.77286^n) time and space 
with an exponentially small error. Moreover, this algorithm can be adapted to
constructing other minimum decision diagrams such as zero-suppressed BDDs,
which provide compact representations of sparse sets and are often used in the field of discrete optimization
and enumeration.





§ INTRODUCTION



 §.§ Background



  
Ordered binary decision diagrams. 
The ordered binary decision diagram (OBDD) <cit.> is one of the data structures
that have been most often used for decades to represent Boolean functions in practical situations,
such as VLSI design, formal verification, optimization of combinatorial problems, and machine learning,
and it has been extensively studied from both theoretical and practical standpoints (see standard textbooks and surveys, e.g., Refs. <cit.>).
Moreover, many variants of OBDDs have been invented to  more efficiently represent  data with properties observed frequently in specific applications (e.g., Refs. <cit.>).
More technically speaking, OBDDs are 
directed acyclic graphs that represent Boolean functions
and also known as  special cases of oblivious read-once branching programs
in the field of complexity theory. 
The reason for OBDDs' popularity lies in their nice properties —
they can be uniquely determined up to the isomorphism for each function
once variable ordering (i.e., the order in which to read the variables) is fixed
and, thanks to this property, 
the equivalence of functions can be checked by just testing the isomorphism between
the OBDDs representing the functions.
In addition, binary operations such as AND and OR between two functions can be performed efficiently 
over the OBDDs representing those functions <cit.>.










Since these properties are essential in many applications, OBDDs have gathered much
attention from various research fields.
To enjoy these nice properties, however, we actually need to address a crucial problem,
which is that
OBDDs may vary exponentially in size depending on their variable ordering.

For instance, a Boolean function 
f(x_1,…, x_2n)=x_1x_2+x_3x_4+…+x_2n-1x_2n
has the a (2n+2)-sized OBDD for the ordering (x_1,…, x_2n)
and a 2^n+1-sized OBDD for the ordering (x_1,x_3,…, x_2n-1,x_2,x_4,…,x_2n) <cit.> (see <ref>
for the case where n=6).
This is not a rare phenomenon; it could happen in many concrete functions that one encounters.
Thus, since the early stages of OBDD research, one of the most central problems  has been how to find an optimal variable ordering, i.e.,
one that minimizes OBDDs.
Since there are n! permutations over n variables, the brute-force search
requires at least n!=2^Ω(nlog n) time to find an optimal variable ordering.
Indeed, finding an optimal variable ordering for a given function is an NP hard problem.

To tackle this high complexity,
many heuristics have been proposed to find an optimal variable ordering or 
a relatively good one.
These heuristics 
work well for Boolean functions appearing
in specific applications
since they are based on very insightful observations,
but they do not guarantee a worst-case time complexity
lower than that achievable with the brute-force search.


The only algorithm with a much lower worst-case time complexity bound, 
O^∗(3^n) time,
[O^∗(·) hides a polynomial factor. This hidden polynomial factor can be improved <cit.>.
]
than the brute-force bound O^∗(n!2^n) for all Boolean functions with n variables was provided
by Friedman and Supowit <cit.>, and that was
almost thirty years ago!

In practice, it is often too costly to construct a minimum OBDD
and the optimal variable ordering may change as the function changes during a procedure,
say, by imposing additional constraints.
Nevertheless, theoretically sound methods for finding an optimal variable ordering
are worth studying for several reasons, such as to judge the optimization
quality of heuristics and to be able to apply such methods at least to parts of the OBDDs
within a heuristics procedure <cit.>.



  
Quantum Speedups of Dynamic Programming
Grover's quantum search algorithm <cit.> and its variants achieve quadratic speedups over
any classical algorithm for the very fundamental problem of exhaustive search.
Thus, one of the merits of the quantum search is its wide applicability.
However, it does not immediately mean quantum speedups for
all problems to which the quantum search is applicable,
since there may exist better classical algorithms than simple exhaustive search.
Indeed, quantum search for an optimal variable ordering of the OBDD from among n! candidates
takes approximately √(n!)≈ 2^1/2nlog n time, while the best classical algorithm
takes only O^∗(3^n)=O^∗(2^(log_2 3)n).
These classical algorithms often employ powerful algorithmic techniques 
such as dynamic programming, divide-and-conquer, and branch-and-bound.
One typical strategy to gain quantum speedups would be
to find exhaustive search (often implicitly) performed within such classical algorithms
and apply the quantum search to that part.
For instance, Dürr et al. <cit.> provided quantum algorithms for some graph problems,
among which the quantum algorithm for the single-source shortest path problem 
achieves a quantum speedup
by applying a variant of Grover's search algorithm to
select the cheapest border edge in Dijkstra's algorithm.
However, applying the quantum search in this way

does not work
when the number of states in a dynamic programming algorithm
is much larger than the number of predecessors of each state.
For instance, the Traveling Salesman Problem (TSP) can be solved
in O^∗(2^n) time by a classical dynamic programming algorithm,
but locally applying the quantum search can attain at most a polynomial-factor improvement.
Recently, Ambainis et al. <cit.> has introduced break-through techniques 
to speed up dynamic programming approaches.
They provide quantum algorithms that solve a variety of vertex ordering problems on graphs
in O^∗(1.817^n) time, graph bandwidth in  O^∗(2.946^n) time, and
TSP and minimum set cover in O^∗(1,728^n) time, where n is the number of vertices in the graphs.






 §.§ Our Results

In this paper, 
we show that quantum speedup is possible for the problem of finding an optimal variable ordering of the OBDD for a given function. 
This is the first quantum speedup for the OBDD-related problems.
Our algorithms assume the quantum random access memory (QRAM) model <cit.>,
which is commonly used in the literature concerned with quantum algorithms.
In the model, one can read contents from or write them into quantum memory in a superposition.

We provide our main result in the following theorem.
 
There exists a quantum algorithm that,
for a function f0,1^n→0,1 given as its truth table,
produces a minimum OBDD representing f
together with the corresponding variable ordering
in O^∗(γ^n) time and space
with an exponentially small error with respect to n, 
where the constant γ is
at most 2.77286.
Moreover, the OBDD produced by our algorithm is always a valid one
for f,
although it is not minimum with an exponentially small probability.


This improves upon the classical best bound 
O^∗(3^n) <cit.> on time/space complexity.
The classical algorithm achieving this bound
is a deterministic one. 
However, there are no randomized algorithms
that compute an optimal variable ordering in asymptotically less time complexity
as far as we know. 



It may seem somewhat restricted to assume that the function f is given as its truth table,
since there are other common representations of Boolean functions
such as DNFs, CNFs, Boolean circuits and OBDDs.
However, this is not the case.
Our algorithm actually works in more general settings
where the input function f is given as any representation
such that the value of f on any specified assignment can be computed
over the representation in polynomial time in n, such as
polynomial-size DNFs/CNFs/circuits and 
OBDDs of any size.
This is because, in such cases, the truth table of f can be prepared
in O^∗(2^n) time and the minimum OBDD is computable from that truth table
with our algorithm. We restate 
<ref>

in a more general form as follows.


Let R(f) be any representation of a Boolean function f with n variables
such that the value of f(x) on any given assignment x∈0,1^n can be computed
on R(f) in polynomial time with respect to n.
Then, there exists a quantum algorithm that,
for a function f0,1^n→0,1 given as R(f),
produces a minimum OBDD representing f
together with the corresponding variable ordering
in O^∗(γ^n) time and space
with an exponentially small error with respect to n, 
where the constant γ is
at most 2.77286. 
Possible representations as R(f) are
polynomial-size DNFs/CNFs/circuits and OBDDs of any size for function f.


There are many variants of OBDDs, among which the zero-suppressed BDDs (ZDDs or ZBDDs) introduced by Minato <cit.>
have been shown to be very powerful in dealing with combinatorial problems (see Knuth's famous textbook <cit.> for how to apply ZDDs to such problems). 
With just two-line modifications, 
our algorithm can construct a minimum ZDD with the same time/space complexity. 
We believe that similar speedups are possible for many other variants of OBDDs
(adapting our algorithm to multiterminal BDDs (MTBDDs) <cit.> is almost trivial).



 §.§ Technical Outline

The first step to take is to somehow adapt the dynamic programming approach
of the classical algorithm <cit.> (called, )
to the framework provided by Ambainis et al. <cit.>.
Consider a Boolean function f over n variables: x_1,…, x_n.
Intuitively,  determines the variable ordering of the minimum OBDD
for f by performing dynamic programming from
the variable to be read last toward that to be read first.
More concretely, let (x_π[1],…, x_π[n]) be the variable ordering 
from the one read last (x_π[1]) to the one read first (x_π[n]),
where π=(π[1],…,π[n]) is a permutation over [n]1,…, n.
For k=1,…, n in this order, and for every subset K⊆ [n]
of cardinality k, the algorithm  
computes a lower bound on OBDD size when π[1],…,π[k]=K
from the lower bounds on OBDD size when 
π[1],…,π[k-1]=K∖h
for all h∈ K.
Thus, by thinking of each node z∈0,1^n of weight k in a Boolean hypercube as the characteristic vector of K, 
the algorithm  can be seen as solving a kind of shortest path problem
on a Boolean hypercube.
Hence, Ambainis et al.'s framework seems applicable.
Their results depend on the property that
a large problem can be divided into the same kind of subproblems or,
in other words, symmetric subproblems
in the sense that they can be solved with the same algorithm.
This property naturally holds in many graph problems.
In our case, firstly, it is unclear whether the problem can be divided into subproblems.
Secondly,
subproblems would be
to optimize the ordering of variable 
starting from the middle variable or even from the opposite end, i.e., from the variable to be read first,

toward the one to be read last.
Such subproblems cannot be solved with the algorithm , and,
in particular,
optimizing in the latter case
essentially
requires the equivalence check of subfunctions of f,
which is very costly. 

Our technical contribution is 
to find, 
by carefully observing the unique properties of OBDDs,
that it is actually possible to even recursively divide the original problem into
asymmetric subproblems,
to generalize the algorithm  so that it can solve the subproblems,
and to use the quantum minimum finding algorithm in order to efficiently select 
the subproblems that essentially contribute to the optimal variable ordering.

More concretely,
we show that, for any k∈ [n],
it is possible to divide the problem into
two collections of subproblems as follows:
for all K⊆ [n] of cardinality k,


  * problems
of finding the ordering  (π[1],…,π[k])
that minimizes the size of the bottom k-layers of the corresponding OBDD, 
assuming that the set π[1],…,π[k] equals K,

  * 
problems

of finding the ordering
(π[k+1],…,π[n])
that minimizes the size of the upper (n-k)-layers of the corresponding OBDD,
assuming that the set
π[k+1],…,π[n] equals [n]∖ K.




Then, taking the minimum of the OBDD size over all K and k
with the quantum minimum finding provides a minimum OBDD and the corresponding variable ordering.
To obtain a better bound, a straightforward strategy is
to consider m  division points (0< k_1< …< k_m<n)
and optimize each of the (m+1) suborderings (π[1],…, π[k_1]), 
(π[k_1+1],…, π[k_2]), …, (π[k_m+1],…, π[n]).
However, this makes subproblems even more asymmetric.
To deal with this asymmetry, we generalize the algorithm 
so that it can cover all the subproblems.
Then, by applying it to each subproblem, we optimize the suborderings 
with the quantum minimum finding so that
the OBDD size is minimized. 
To improve the complexity bound further,
a simple idea would be to replace the generalized  with the quantum 
algorithm we have just obtained.
However, the latter algorithm works only for the original problem.
Thus, we generalize the quantum algorithm so that it can be applied
to the asymmetric subproblems.
By repeating this composition and generalization, we obtain the final algorithm.




 §.§ Related Work


The studies related to minimizing OBDDs are so numerous
that we cannot cover all of them. 
We thus pick up some of purely theoretical work.

Meinel and Slobodová <cit.> proved that it is NP hard to construct an optimal OBDD for a Boolean function given by a logical circuit, a DNF, a CNF, or an OBDD, even if the optimal OBDD is of constant size.
Tani, Hamaguchi and Yajima <cit.> proved
that it is NP hard to 
improve the variable ordering (and thus, to find an optimal variable ordering)
for a given multi-rooted OBDD, where the NP hardness is proved by a reduction from Optimal Linear Arrangement <cit.>.
Bollig and Wegener <cit.> finally proved
the NP hardness for a given single-rooted OBDD.
This is still true if the input function is restricted to monotone functions <cit.>.
Minimizing the width of an OBDD is also NP hard <cit.>.
As for approximation hardness, Sieling <cit.> proved that
if there exists a polynomial-time approximation scheme for
computing the size of the minimum OBDD for a given OBDD,
it then holds that NP=P.

It would be nice if, for every function,
there exists at least one variable ordering
under which the OBDD for the function is of a size bounded by a polynomial.
As one may expect, 
this is not the case.
It can be proved by a counting argument that
there exists a function for which the OBDD size
grows exponentially in the number of variables
under any variable ordering <cit.>.
Examples of such functions include practical ones such as
the multiplication function <cit.>,
a threshold function <cit.>,
and the division function <cit.>.



The sizes of OBDDs for several classes of Boolean functions 
are investigated <cit.>.
The OBDD size is also studied from the viewpoint of 
computational learning and knowledge-bases <cit.>.

In applying OBDDs to graph problems, it is possible to find
variable orderings for which OBDD size is nontrivially upper-bounded
in terms of certain measures characterizing graph structures <cit.>.
A similar concept was discoved for ZDDs <cit.> by Knuth <cit.>.
This concept is now called the frontier method,
and lots of work is based on it.





§ PRELIMINARIES



 §.§ Basic Terminology

Let ,  and  be the sets of natural numbers, integers,  and real numbers, respectively.
For each n∈, let [n] be the set 1,…, n,
and n be the permutation group over [n].
We may denote a singleton set k by k for notational simplicity if it is clear from the context;
for instance, I∖k may be denoted by I∖ k, if we know I is a set.
For any subset I⊆ [n], let
Π_n(I) be the set of π∈n such that the first I members 
π[1],…,π[|I|] constitutes I, i.e., 

    Π_n(I)π∈nπ[1],…,π[|I|]=I⊆n.

For simplicity, we omit the subscript n and  write Π(I).
More generally, for any two disjoint subsets I,J⊆[n], let

    Π_n(I,J)π∈nπ[1],…,π[|I|]=I, π[|I|+1],…,π[|I|+|J|]=J⊆n.

For any disjoint subsets I_1, …,I_m⊆ [n] for m∈ [n], Π_n(I_1,…, I_m) is defined similarly.
For simplicity, we may denote I by I, if it is clear from the context.

We denote the union operation over disjoint sets by ⊔ (instead of ∪)
when we emphasize the disjointness of the sets. For example,
the union of the disjoint sets 1,2 and 5,6 is denoted by 1,2⊔5,6.




For n Boolean variables x_1,…, x_n, any set I⊆ [n],
and any vector =(b_1,…, b_I)∈0,1^I,
_I denotes the ordered set (x_j_1,…, x_j_I),
where 
j_1,…,j_|I|=I 

and j_1<… <j_I,

and _I= denotes x_j_i=b_i for each i=[I].
For any Boolean function f0,1^n →0,1 with variables x_1,…, x_n,
we denote by f|__I= the function 
obtained by restricting f with _I=.

If I is a singleton set, say, I=i, 
we may write _i and f|__i=b to mean x_i and f|__i=b, respectively,  for notational simplicity. We say that g is a subfunction of f if g is equivalent to the function f|__I=
for some I⊆ [n] and ∈0,1^I.

For any function g(n) in n, we use the notation O^∗(g(n)) to hide a polynomial factor in n.
For instance, n^32^n and 2^n are both in O^∗(2^n).
We further denote X=O^∗(Y) by  X⪅ Y.

We use the following  upper bound many times in this paper.

For n∈ and k∈ [n] ∪0,
it holds that
nk≤ 2^n k/n,
where · represents the binary entropy function δ -δlog_2 δ -(1-δ) log_2 (1-δ).




 §.§ Ordered Binary Decision Diagrams

This subsection briefly introduces ordered binary decision diagrams (OBDDs).
For interested readers, see standard textbooks and survey papers 
(e.g., Refs. <cit.>).

OBDDs are a special case of read-once oblivious branching programs in complexity-theoretic terms
that is, branching programs that satisfy the following conditions:
each variable is read at most once
on each directed path from the root to a terminal node, and
the orderings of variables to be read on all such paths are consistent with a certain fixed ordering.

In the following, we formally define OBDDs in graph-theoretic terms and provide several notations.
For any Boolean function f0,1^n →0,1 over variables x_1,…, x_n and any permutation π∈n (called a variable ordering),
an OBDD fπ is a directed acyclic graph G(V,E) defined as follows:




  * The node set V is the union of two disjoint sets N and T of 
non-terminal nodes with out-degree two and terminal nodes with out-degree zero, respectively, where T contains exactly two nodes:
T=,.
The set N contains a unique source node , called the root.


  * fπ is a leveled graph with n+1 levels.
Namely, the node set can be partitioned into n subsets:
V V_0⊔ V_1⊔…⊔ V_n,
where V_n=𝗋 and 

V_0=T=𝗍,𝖿,
such that
each directed edge (u,v)∈ E

is in V_i× V_j
for a pair (i,j)∈ [n]× (0⊔ [n-1])
with i>j.
For each i∈[n], subset V_i
(called the level i)
is
associated with the variable x_π[i],
or alternatively, each node in V_i is labeled with x_π[i].
[In the standard definition, V_i is associated with the variable  x_π[n-i].
Our definition
follows the one given in <cit.>
to avoid complicated subscripts of variables.]
For convenience, we define a map N → [n]
such that if v∈ V_i then =π[i].




  * The two edges emanating from every non-terminal node v are called the 0-edge and the 1-edge, which are labeled with 0 and 1, respectively. 
 For every u∈ N, let u0 and u1 be the destinations of the 0-edge and 1-edge of u, respectively. 






  * Let (f) be the set of all subfunctions of f.
Define a bijective map F V→(f) as follows:



(a) 
F()=f for ∈ V_n;
(b) F()= and F()= for ,∈ V_0;

(c) For every u∈ N and b∈0,1, F(u_b) is the subfunction obtained from F(u) by substituting x_(u) with b, i.e.,
F(u_b)=F(u)|_x_(u)=b. 



  * fπ must be minimal in the sense that
the following reduction rules cannot be applied.
In other words, fπ is obtained 
by maximally applying the following rules (<ref>):


  * if there exists a redundant node u∈ N, then remove u and its outgoing edges,
and redirect all the incoming edges of u to u0,
where a node u is redundant 
if u0 is the same node as u1.


  * if there exist equivalent nodes u, v⊂ N, then remove v (i.e., any one of them)
and its outgoing edges, and redirect all incoming edges of v to u, where u and v are equivalent
if (1)  (u) is equal to (v), and

(2) u0 and u1 are the same nodes as v0 and v1, respectively.















For ease of understanding the above notations, let us consider the OBDD 
on the right side
in <ref>.
The root   is the uppermost node labeled with x_6.
The ordering π is (1,3,5,2,4,6). 
Every node in V_i (i=1,…, 6) is represented by a circle labeled with x_π[i].
For instance, V_3 consists of all the four nodes labeled with x_5.
For each node v∈ V_3, it holds that (v)=5.
Let u be the left node labeled with x_3.
Since the path from  to u consists of three edges labeled with
0, 1, and 0 in this order from the root side,
F(u) is represented as F(r)|_x_6=0,x_4=1,x_2=0=f|_x_6=0,x_4=1,x_2=0=x_3.



For each j∈ [n], 
j denotes the width at the level associated with the variable x_j,
namely, the number of nodes in the level π^-1[j] (<ref>).
For I⊆ [n], let π_I be a permutation π in Π(I)
that minimizes the number of nodes in level 1 to level |I|:

    π_Imin∑_j=1^|I|π[j]π∈Π(I).

Note that ∑_j=1^|I|π[j]= ∑_i∈ Ii
for π∈Π(I).






More generally, 
for disjoint subsets I_1,…, I_m⊆ [n],
π_I_1,…, I_m is a permutation in Π(I_1,…, I_m)
that minimizes the number of
the nodes in level 1 to level |I_1|+… +|I_m|
over all π∈Π(I_1,…, I_m):

    π_I_1,…, I_mmin∑_j=1^|I_1|+… +|I_m|π[j]π∈Π(I_1,…, I_m) .

Note that 
min∑_j=1^|I_1|+… +|I_m|π[j]=∑_i∈ I_1⊔…⊔ I_mi
for any π∈Π(I_1,…, I_m).
The following well-known lemma captures the essential property of OBDDs.
It states that
the number of nodes at level i∈ [n] is constant over all π,
provided that the two sets π[1],…, π[i-1] and π[i+1],…, π[n] are fixed.

For any non-empty subset I⊆ [n] and any i∈ I,
there exists a constant c_f such that,
for  each π∈Π(I∖i,i),
π[I]≡i=c_f.





For convenience, we define  shorthand for the minimums of the sums in 

Eqs. (<ref>) and (<ref>).
For I'⊆ I⊆ [n],
I[I'] is defined as
the number of nodes in the levels associated with variables indexed by elements in I'
under permutation  π_I, namely,
I[I']∑_i∈ I'ifπ_I.
More generally, for disjoint subsets I_1,…, I_m⊆ [n] and I'⊆ I_1⊔…⊔ I_m,

    I_1,…, I_m[I']
    
    ∑_i∈ I'ifπ_I_1,…, I_m.

As a special case, we denote I_1,…, I_m[I_1⊔…⊔ I_m] by I_1,…, I_m. We define ∅ as 0.



 §.§ The Algorithm by Friedman and Supowit

This subsection reviews the algorithm by Friedman and Supowit <cit.>.
We will generalize their idea later and heavily use the generalized form in our quantum algorithm.
Hereafter, we call their algorithm .


  §.§.§ Key Lemma and Data Structures

The following lemma is the basis of the dynamic programming approach used in the algorithm.

For any non-empty subset I⊆ [n] and any Boolean function f0,1^n→0,1,
the following holds:
I=min_k∈ II∖ k+kfπ_I∖ k,k
=min_k∈ II∖ k,k.

The proof is given in <ref>.



Before sketching algorithm ,
we provide several definitions.
For any I⊆ [n], 
_I is an array with 2^n-|I| cells each of which stores a non-negative integer.
Intuitively, for ∈0,1^n-|I|,
the cell _I[b]
stores (the pointer to) the unique node of fπ_I associated
via F with function f|_x_[n]∖ I=.
Hence, we may write _I[x_[n]∖ I=b] instead of _I[b]
to clearly indicate the value assigned to each variable x_j for j∈ [n]∖ I.


The purpose of _I is to relate
all subfunctions f|__[n]∖ I=b (∈0,1^n-|I|) 


to the corresponding nodes of fπ_I.
We assume without loss of generality that
the pointers to nodes of fπ_I are non-negative integers
and, in particular,  those to the two terminal nodes corresponding to  and  are 
the integers 0 and 1, respectively.
Thus, _∅ is merely the truth table of f.

Algorithm  computes _I 
together with 
π_I, I,
and another data structure, _I
for all I⊆[n],
starting from _∅ via dynamic programming.
_I is the set of all triples
of (the pointers to) nodes,
(u,u_0,u_1)∈ N× (N⊔ T)× (N⊔ T),
in fπ_I,
where (u)=π_I[I], and  (u,u_0) and (u,u_1) are the 0-edge and 1-edge of u, respectively.
Thus, _I contains the structure of 
the subgraph of fπ_I induced by V_I.


The purpose of the _I  is to prevent the algorithm
from duplicating existing nodes,
i.e., creating nodes associated with 
the same subfunctions
as those with which the existing nodes are associated.










By the definition, _∅ is the empty set. We assume that _I is implemented with an appropriate data structure, such as a balanced tree, so that the time complexity required for membership testing and insertion is the order of logarithm in the number of triples stored in _I.
An example of _I and _I is shown in <ref>.



More generally, for disjoint subset I_1,…, I_m⊆ [n],
_I_1,…, I_m is an array with
2^n-|I_1⊔…⊔ I_m| cells
such that, for b∈0,1^n-|I_1⊔…⊔ I_m|,
_I_1,…, I_m[b]
stores the nodes of fπ_I_1,…, I_m
associated with the function f|_x_[n]∖ I_1⊔…⊔ I_m=b.


_I_1,…, I_m is defined similarly for fπ_I_1,…, I_m.
For simplicity, we hereafter denote by I_1,…, I_m 
the quadruplet (π_I_1,…, I_m, I_1,…, I_m, _I_1,…, I_m, _I_1,…, I_m).



  §.§.§ Sketch of Algorithm  <cit.>

Algorithm  performs the following operations for k=1,…, n in this order.
For each k-element subset I⊆ [n],
compute 
I∖ i,i

from  I∖ i

for each i∈ I in the manner described later 
(note that, since the cardinality of the set I∖ i is k-1, 
I∖ i has already been computed).
Then set 
I⟵I∖ i^*,i^*,
where i^* is the index i∈ I that minimizes I∖ i,i,
implying that π_I is π_I∖ i^*,i^*.
This is justified by <ref>.
A schematic view of the algorithm is shown in <ref>.




To compute 
I∖ i,i
from  I∖ i, do the following.
First set _I∖ i,i←∅ 

and I∖ i,i←I∖ i 
as their initial values.
Then, for each ∈0,1^n-|I|, 
set 

    u_0   ←_I∖ i[x_[n]∖ I=,x_i=0],   
    u_1   ←_I∖ i[x_[n]∖ I=, x_i=1].

If u_0=u_1, then store u_0 in _I∖ i,i[].
Otherwise, test whether (u,u_0,u_1) for some u is a member of _I∖ i.
If it is, store u in the _I∖ i,i[];
otherwise create a new triple (u', u_0,u_1), insert it to _I∖ i,i
and increment I∖ i,i.
Since u' is the pointer to the new node,
u' must be different 
from any pointer already included in _I∖ i,i
and
from any pointer to a node
in V_1⊔…⊔ V_k-1 
in fπ_I∖ i,
where k=I.
Such u' can be easily chosen by setting u' to
two plus the value of I∖ i,i before the increment,
since the I∖ i,i is exactly the number of triples in _I∖ i,i plus V_1⊔…⊔ V_k-1,
and the numbers 0 and 1 are reserved for the terminal nodes.
We call the above procedure table folding with respect to x_i,
because it halves the size of _I∖ i.
We also mean it by “folding _I∖ i with respect to x_i”.

The complexity analysis is fairly simple.
For each k, we need to compute 
I

for nk possible I's with I=k.
For each I, it takes O^*(2^n-k) time 
since the the size of _I∖ i is 2^n-k+1
and each operation to _I∖ i takes a polynomial time in n.
Thus, the total time is 
∑_k=0^n2^n-knk=3^n,
up to a polynomial factor. 
The point is that computing each 
I

takes time linear to the size of _I∖ i up to a polynomial factor.
The space required by Algorithm  during the process for k
is dominated by that for _I, _I∖ i and _I for all I and i∈ I,
which is O^*(2^n-knk). 
The space complexity is thus O^∗(max_k∈0∪[n]2^n-knk)=O^∗(3^n).


	Suppose that the truth table of f0,1^n →0,1 is given as input.
	Algorithm  produces 
	[n]
	
	in O^∗(3^n) time and space.




 §.§ Quantum Computation

We assume that readers have a basic knowledge of quantum computing
(e.g., Refs. <cit.>).
We provide only a lemma used to obtain our results.

The quantum search algorithm discovered by Grover <cit.> has been generalized in many ways.
For instance, Buhrman et al. <cit.> provided a small error version of quantum search,
while Dürr and Høyer <cit.> devised a quantum algorithm that finds the minimum of a function.
By combining these two algorithms,
we obtain the following lemma
(an adaptation of Corollary 2.3 in Ref. <cit.>).

For every ε >0 there exists a quantum algorithm 
that, for a function f [N]→ given as an oracle,
find an element x∈ [N] at which f(x) achieves the minimum,
with error probability at most ε
by making O(√(Nlog (1/ε))) queries.


In this paper, the search space N is exponentially large in n and we are interested in 
exponential complexities, ignoring polynomial factors in them.
We can thus safely assume ε=1/2^p(n) for a polynomial p(n),
so that the overhead is polynomially bounded.
Since our algorithms use <ref> constant times,
their overall error probabilities are exponentially small.
In the following proofs, we thus assume that ε is exponentially small whenever we use 
<ref>, and do not
explicitly analyze the error probability for simplicity.

Our algorithms assume that the quantum random access memory (QRAM) model <cit.>,
which is commonly used in the literature when considering quantum algorithms.
In the model, one can read contents from or write them into quantum memory in a superposition.



§ QUANTUM ALGORITHM WITH DIVIDE-AND-CONQUER

We generalize <ref> and <ref> and use them in our quantum algorithm.

For any disjoint subsets I_1,…,I_m,J⊆ [n] with J≠∅ 
and any Boolean function f0,1^n→0,1,
the following holds:

    I_1,…,I_m,J   =min_k∈ JI_1,…,I_m,J∖k+kfπ_I_1,…,I_m,J∖k,k
       =min_k∈ JI_1,…,I_m,J∖k,k.


The proof of this lemma is very similar to that of <ref> and deferred to <ref>.
Based on <ref>, we generalize <ref> to obtain algorithm 
(its pseudo code is given in <ref>).
Recall that I_1,…, I_m denotes
the quadruplet (π_I_1,…, I_m, I_1,…, I_m, _I_1,…, I_m, _I_1,…, I_m).
A schematic view of  is shown in <ref>.



For disjoint subsets I_1,…, I_m, J⊆ [n]
with J≠∅,
there exists a deterministic algorithm  that


produces 
I_1,…, I_m,J


from I_1,…, I_m for an underlying function f0,1^n →0,1
in O^∗2^n-I_1⊔…⊔ I_m⊔ J· 3^J time and space.
More generally, 
for each k∈ [J],
the algorithm produces
the set I_1,…, I_m,K K⊆ J, K=k
from I_1,…, I_m
in O^*2^n-I_1⊔…⊔ I_m⊔ J∑_j=0^k2^J-jJj time and space.

Note that if I_1⊔…⊔ I_m=∅ and J=[n], then we obtain
 <ref>.


We focuses on the simplest case of m=1,
for which our goal is to show an algorithm
that produces 
I,J

from 
I.

It is straightforward to generalize the proof to the case of m≥ 2.

Starting from I, 
the algorithm first folds _I with respect to each variable in x_j j∈ J 
to obtain I,j for every j∈ J,
then 
fold _I,j_1 with respect to x_j_2 and  _I,j_2 with respect to x_j_1 to
obtain I,j_1,j_2 by taking the minimum of I,j_1,j_2
and I,j_2,j_1
for every j_1,j_2∈ J,
and repeat this to finally
obtain I,J.
This algorithms is justified by 
 <ref>.





The details of <ref>

are shown in <ref>.
For each j∈ [J], K⊆ J with K=j, and h∈ K,
the time complexity of computing
I,K

from 
I,K-h

is linear to the size  of _I,K, i.e.,  2^n-I-j, up to a polynomial factor.
The total time is thus, up to a polynomial factor,

    ∑_j=1^J2^n-I-jJj<
    2^n-I-J∑_j=0^J2^J-jJj
    = 2^n-I⊔ J· 3^J.



If we stop the algorithm at j=k, then the algorithm produces
the set I,K K⊆ J, K=k. 
The time complexity in this case is at most
2^n-I-J∑_j=0^k2^J-jJj,
up to a polynomial factor.

Since the space complexity is trivially upper-bounded by the time complexity,
we complete the proof.



One may think that the actual space complexity could be much less than the time complexity.
However, this is not the case.
The size of _I,K is also the dominant factor determining the space complexity.
When computing _I,K with K=j,
it suffices to keep _I,K and _I,K-h 
for every h∈ K in memory.
The space complexity is thus, up to a polynomial factor,
the maximum of 
2^n-I-jJj
+
2^n-I-(j-1)Jj-1
over all j∈ [J], which is 
the same order as the time complexity.



It is not difficult to see that the algorithm  
works even when the function f has a multivalued function:
f0,1^n→.
The only difference from the Boolean case is that
the truth table maps each Boolean assignment
to a value in .
In this case, the algorithm produces a variant of an OBDD (called
a multi-terminal BDD,  MTBDD) of minimum size.
In addition, our algorithm with two-line modifications 
to the table folding rule
in   
can construct a minimum zero-suppressed BDD (ZDD) <cit.> for a given Boolean function.
The details are described in <ref>.
These modifications are also possible for the quantum algorithms described later,
since they perform table folding by running  as a subroutine.


The following theorem is the basis of our quantum algorithms.

For any disjoint subsets 
I_1,…, I_m, J⊆ [n] with J≠∅
and any k∈ [J],
it holds that

    I_1,…, I_m,J[J]=
    min_K K⊆ J, K=kI_1,…, I_m,K[K]
    +I_1,…, I_m,K,J∖ K[J∖ K]
    .

In particular, when I_1⊔…⊔ I_m=∅ and J=[n],
it holds that

    [n]=
    min_K⊆ [n], K=kK
    +K,[n]∖ K[[n]∖ K]
    .





 We first prove the special case of I_1⊔…⊔ I_m=∅ and J=[n].
 By the definition, we have 

    [n]   = ∑_j=1^n π[j]= ∑_j=1^k π[j] + ∑_j=k+1^n π[j],

for the optimal permutation π=π_[n].
Let K=π[1],…,π[k].
By <ref>, the first sum is independent of how π maps 
k+1,…, n to [n]∖ K. 
Thus, it is equal to the minimum 
of ∑_j=1^k π_1[j]
over all π_1∈Π(K), i.e., K.
Similarly, the second sum is independent of how π maps [k] to K.
Thus, it is equal to the minimum of ∑_j=k+1^n π_2[j]
over all π_2∈Π(K,[n]∖ K), i.e., K,[n]∖ K[[n]∖ K].
This completes the proof of <ref>.

We can generalize this in a straightforward manner. 
Let π = π_I_1,…, I_m,J
and ℓ=I_1⊔…⊔ I_m.
Then, we have

    I_1,…, I_m,J [J]
       = ∑_j=1^k π[ℓ+j] + ∑_j=k+1^Jπ[ℓ+j].

By defining
Kπ[ℓ+1 ],…,π[ℓ+k],
the same argument as the special case of ℓ=0
implies that
the first and second sums are
I_1,…, I_m,K[K] and
I_1,…, I_m,K,J∖ K[J∖ K],
respectively. This completes the proof of <ref>.


A schematic view of the above lemma is shown in <ref>.





 §.§ Simple Case

We provide simple quantum algorithms on the basis of <ref>.
The lemma states that, for any k∈ [n],
[n] is the minimum of 
K
+K,[n]∖ K[[n]∖ K]
over all K⊆ [n] with K=k.
To find K 
from among nk possibilities
that minimizes this amount,
we use the quantum minimum finding (<ref>).
To compute K
+K,[n]∖ K[[n]∖ K]=K,[n]∖ K, 
it suffices to first compute K (including K), 
and then K,[n]∖ K
(including K,[n]∖ K) from K.


The time complexity for computing K from ∅
is O^∗(2^n-k3^k) by  <ref>
with I_1⊔…⊔ I_m=∅ and J=K,
while that for computing K,[n]∖ K
from K
is O^∗(3^n-k) by  <ref>
with m=1, I_1=K, and J=[n]∖ K.
Thus, the time complexity for computing
K,[n]∖ K from ∅

is O^∗(2^n-k3^k+ 3^n-k).


Thus, for k=α n with α∈ (0,1) fixed later,
the total time complexity up to a polynomial factor is

    T(n)=√(nα n)2^(1-α)n3^α n+3^(1-α)n≤ 2^1/2αn
    2^(1-α)+αlog_2 3n
    +
    2^(1-α)log_2 3n.

To balance the both terms, we set
(1-α)+αlog_2 3=(1-α)log_2 3
and obtain 
α=α^∗, 
where
α^∗=log_23-1/2log_23-1≈ 0.269577.

We have
min_α∈ [0,1]T(n)=O2^1/2α^∗n+(1-α^∗)n+α^∗ (log_2 3)n=O(γ_0^n),
where γ_0=2.98581…. This slightly improves the classical best bound O^∗(3^n)
on the time complexity.
To improve the bound further, we introduce a preprocess
that classically computes 
K for every K with K=α n  (α∈ (0,1))
by using <ref>.


By <ref>,
the preprocessing time is then

    ∑_j=1^α  n 2^n-j·nj   ≤α  n ·max_j∈ [α n] 2^n-jnj⪅{[ 2^(1-α )n+αn    (α < 1/3);  2^2/3n+1/3n    (α≥ 1/3), ].

since 2^n-jnj increases when j<n/3
and decreases otherwise.
Note that once this preprocess is completed,
we can use K for free
and assume that the cost for accessing K is polynomially bounded
for all K⊆ [n] with K=α n.

Then, assuming that α<1/3, the total time complexity up to a polynomial factor
is

    T(n)=∑_j=1^α n 2^n-j·nj+√(nα n)
    n^O(1)
    +3^(1-α)n⪅
    2^(1-α)+αn+2^1/2α+(1-α)log_2 3n.

To balance the both terms, we set
(1-α)+α=1/2α+(1-α)log_2 3 and obtain the solution α = α^∗, where α^∗ 0.274863…,
which is less than 1/3 as we assumed.
At α=α^∗, we have
T(n)⪅ 
2^(1-α^∗)+α^∗n=O^∗(γ_1^n),
where γ_1 is at most 2.97625 (<γ_0).
Thus,  introducing the preprocess improves the complexity bound.
A schematic view of the above algorithm is shown in <ref>.

<ref> shows that,
by using <ref> twice,
we have a better complexity bound 
O^∗(γ_2^n), where
γ_2 is at most 2.8569  (< γ_1).






 §.§ General Case


We can improve this bound further by applying <ref> k times.
We denote the resulting algorithm with parameters k and α⃗ (α_1,…,α_k) by 
k,α⃗


where 0<α_1<… <α_k<1.
Its pseudo code is given in <ref>.
In addition, we assume α_1<1/3 and α_k+1=1 in the following complexity analysis.

To simplify notations, define two function as follows:
for x,y∈ such that 0<x<y<1,

    f(x,y)   1/2y·x/y  +g(x,y),   
    g(x,y)    (1-y)+(y-x) log_2(3).

The time required for the preprocess
is ∑_ℓ=1^α_1 n 2^n-ℓ·nℓ
up to a polynomial factor.
Thus, the total time complexity can be described as the following recurrence:

    T(n)   =∑_ℓ=1^α_1 n 2^n-ℓ·nℓ+L_k+1(n),
    
    L_j+1(n)   =√(α_j+1nα_jn)L_j(n)+2^(1-α_j+1)n 3^(α_j+1-α_j)n
    = √(α_j+1nα_jn)L_j(n)+2^g(α_j, α_j+1)n,
    
    L_1(n)   =O^∗(1),

for each j∈ [k].
Intuitively, L_j(n) is the time required for 
producing K_1,K_2∖ K_1, …, K_j∖ K_j-1
such that K_1,K_2∖ K_1, …, K_j∖ K_j-1
is minimum over all K_1, …, K_j-1
satisfying K_ℓ=α_ℓ n for every ℓ∈ [k+1]
and K_ℓ⊂ K_ℓ+1 for every ℓ∈ [k].

Since L_1(n)=O^∗(1), we have
L_2(n)⪅√(α_2 nα_1 n)· 2^g(α_1, α_2)n⪅ 2^f(α_1,α_2)n.
By setting f(α_1,α_2)=g(α_2,α_3), we have

    L_3(n)
    =√(α_3 nα_2 n)· (L_2(n)+2^g(α_2, α_3)n) 
    ⪅√(α_3 nα_2 n)· 2^g(α_2, α_3)n⪅ 2^f(α_2,α_3)n.

In general, for j=2,…,k,
setting f(α_j-1,α_j)=g(α_j,α_j+1)  yields
L_j+1(n)⪅ 2^f(α_j,α_j+1)n.
Therefore, the total complexity [<ref>] is

    T(n)⪅∑_ℓ=1^α_1 n 2^n-ℓ·nℓ+2^f(α_k,α_k+1)n⪅2^(1-α_1)n+α_1n+2^f(α_k,1)n,

where we use 
α_1<1/3, α_k+1=1, and 
Eq. (<ref>).
To optimize the right-hand side, we set parameters so that 1-α_1+α_1=f(α_k,1).

In summary, we need to find the values of parameters α_1,…, α_k that satisfy the following system of equations and α_1<1/3:

    1-α_1+α_1   =f(α_k,1),
    
    f(α_j-1,α_j)   =g(α_j,α_j+1)    (j=2,…, k).


By numerically solving this system of equations, we obtain T(n)=O(γ_k ^n), where γ_k and
the corresponding α_i's for k=1,…, 6 are shown in <ref> in <ref>
(α_1<1/3 is satisfied as we assumed). 
The value of γ_k becomes smaller as k increases. However, incrementing k beyond 6 provides only negligible improvement of γ_k. The value of γ_6 is  at most 2.83728.
Since the space complexity is trivially upper-bounded
by the time complexity, we have the following theorem.
Note that the values of α_i's are not symmetric with respect to 1/2. 
This reflects the fact that optimizing cost is not symmetric  with respect to 1/2,
contrasting with many other combinatorial problems.


There exists a quantum algorithm that,
for the truth table of f0,1^n→0,1 given as input,


produces [n] 
with probability 1-exp (-Ω(n))
in O^∗(γ^n) time and space, where the constant γ is
at most 2.83728, which is achieved by 
k,α⃗
with k=6 and 

    α⃗=( 0.183791, 0.183802, 0.183974, 0.186131, 0.206480, 0.343573).












§ QUANTUM ALGORITHM WITH COMPOSITION



 §.§ Quantum Composition Lemma

Recall that the classical composition lemma (<ref>)
states that algorithm  can be generalized to
compute 
I_1,…, I_m,J
from
I_1,…, I_m.
By generalizing
the quantum algorithm given in <ref>,
we now provide a quantum version of <ref>,
called the quantum composition lemma.


For any disjoint subsets I_1,…, I_m, J⊆ [n],
there exists a quantum algorithm
that, with probability 1-exp(-Ω(n)),






produces 
I_1,…, I_m,J


from I_1,…, I_m for an underlying function f0,1^n →0,1
in O^∗2^n-I_1⊔…⊔ I_m⊔ J·γ^J time
and space,
where γ is the constant defined in <ref>.


A pseudo code of the algorithm provided in <ref>
is shown as Γk,α⃗
in <ref>, where 
the subscript Γ, which represents the subroutine 
appearing in <ref>,
will be set to the deterministic algorithm ,
and
k and α⃗ will be set to the values specified 
in <ref>.


Since the space complexity is trivially upper-bounded by the time complexity,
we analyze the time complexity in the following.
For simplicity, we assume m=1 and write just I instead of I_1.
It is straightforward to generalize to the case of m≥ 2.

We now provide the algorithm Γk,α⃗ that produces 
I,J
from I,
where the subroutine Γ used in <ref> is set to algorithm .
As parameters, the algorithm has an integer k∈ and a vector α⃗ (α_1,…,α_k)∈^k
such that 0<α_1<…<α_k<1. Set k and α⃗ to the same values assumed in
the algorithm in <ref>.
In addition, we assume α_k+1=1 in the following.

Let n'=J. 
In the preprocess, the algorithm 
computes 
the collection I,K K⊆ J, K=α_1n' 
based on <ref>
for given I with
the time complexity
2^n-I-n'∑_ℓ=1^α_1 n' 2^n'-ℓn'ℓ
up to a polynomial factor.
Thus, the total time complexity is expressed as

    T'(n,n')   =2^n-I-n'∑_ℓ=1^α_1 n' 2^n'-ℓn'ℓ+L'_k+1(n,n'),

where L'_k+1(n,n') is the time taken to perform all but the preprocess.

Based on <ref>,
the algorithm proceeds in a way similar to the one given in <ref>,
which corresponds to the special case of I=∅ and J=[n].
The complexity L'_k+1(n,n') is then  expressed by the following recurrence:


    L'_j+1(n,n')   =√(α_j+1n'α_jn')L'_j(n,n')+2^n-I-α_j+1n' 3^(α_j+1-α_j)n'     [j∈ [k]],
    
    L'_1(n,n')   =O^∗(1).












In the following, we prove by induction that T'(n,n')⪅ 2^n-I-n'T(n'),
where the function T(·) is defined in <ref>.
Since n'=J and T(n')=O^*(γ^n'), this completes the proof for m=1.

Since L'_1(n,n')=O^∗(1),  we have

    L'_2(n,n')   ⪅ 2^n-I-n'√(α_2 n'α_1 n') 
    2^(1-α_2)n'3^(α_2-α_1)n'=2^n-I-n' L_2(n'),

where the function L_2(·) is defined in <ref> for j=1.
This is the base case of the induction.
Then, assuming that L'_j(n,n')⪅ 2^n-I-n'L_j(n'), we have

    L'_j+1(n,n')   ⪅√(α_j+1n'α_jn')2^n-I-n'L_j(n')+2^n-I-α_j+1n' 3^(α_j+1-α_j)n'
       =2^n-I-n'√(α_j+1n'α_jn')L_j(n')+2^n'-α_j+1n' 3^(α_j+1-α_j)n'=2^n-I-n'L_j+1(n').

Therefore, it holds that L'_k+1(n,n')⪅ 2^n-I-n'L_k+1(n') by induction.
Then, it follows from 
<ref> that


    T'(n,n')   ⪅ 2^n-I-n'∑_ℓ=1^α_1 n' 2^n'-ℓn'ℓ+2^n-I-n'L_k+1(n')
    =2^n-I-n'T(n').

Since T(n')=T(J)=O^∗(γ^J) by <ref>,
the lemma follows.





Suppose that Γ is a quantum algorithm that,
for any disjoint subsets I_1,…, I_m, J⊆ [n] with J≠∅,
produces 
I_1,…, I_m,J from I_1,…, I_m 
with probability 1-exp(-Ω(n))

in O^∗2^n-I_1⊔…⊔ I_m⊔ J·γ^J time and space
for an underlying function f0,1^n →0,1.
Then, for any possible k∈ and α⃗∈^k and for any disjoint subsets I_1,…, I_m, J⊆ [n] with
J≠∅, 
Γk,α⃗
produces I_1,…, I_m,J from I_1,…, I_m
with probability 1-exp(-Ω(n))

in O^∗2^n-I_1⊔…⊔ I_m⊔ J·β_k^J time and space
for the function f,
where β_k^n upper-bounds, up to a polynomial factor, the time complexity 
required for 
Γk,α to 
compute [n] from ∅,

that is, T(n)=O^∗(β_k^n) for T(n) that satisfies the following recurrence:

    T(n)   =∑_ℓ=1^α_1 n 2^n-ℓnℓ+L_k+1,
    
    L_j+1   =√(α_j+1nα_jn)L_j+2^(1-α_j+1)nγ^(α_j+1-α_j)n
    = √(α_j+1nα_jn)L_j+2^g_γ(α_j, αj+1)    (j∈ [k]),
    
    
    
    
    
    
    
    L_1   =O^∗(1),


where

g_γ (x,y) (1-y)+(y-x) log_2γ.






Recall that 
algorithm 
is used as a subroutine in k,α
provided in <ref>.
Since the input and output of Γ assumed in the statement are the same as
those of algorithm ,
one can use Γ instead of algorithm 
in k,α
(compromising on an exponentially small error probability).
Let _Γ(k,α) be the resulting algorithm.
Then, one can see that the time complexity T(n) of 
_Γ(k,α)
satisfies the recurrence:
Eqs. (<ref>)-(<ref>),
which are obtained by just replacing g(x,y) with g_γ(x,y)
in 

Eqs. (<ref>)-(<ref>).
Suppose that T(n)=O^∗(β_k^n) follows from the recurrence.

Next, we generalize _Γ(k,α)
so that it produces I_1,…, I_m,J from I_1,…, I_m
for any disjoint subsets I_1,…, I_m, J⊆ [n] with J≠∅.
The proof is very similar to that of <ref>.
The only difference is that
the time complexity of Γ is 
O^∗2^n-I_1⊔…⊔ I_m⊔ J·γ^J, instead of 
O^∗2^n-I_1⊔…⊔ I_m⊔ J· 3^J.
Namely, when m=1 and n'=J, the time complexity of Γk,α
satisfies the following recurrence: for each j∈ [n],

    T'(n,n')   =2^n-I-n'∑_ℓ=1^α_1 n' 2^n'-ℓn'ℓ+L'_k+1(n,n'),
    
    L'_j+1(n,n')   =√(α_j+1n'α_jn')L'_j(n,n')+2^n-I-α_j+1n'γ^(α_j+1-α_j)n'     [j∈ [n]],
    
    L'_1(n,n')   =O^∗(1),

from which it follows that
T'(n,n')=2^n-I-n'T(n')=O^∗2^n-I⊔ J·β_k^J.
It is straightforward to generalize to the case of m≥ 2.




 §.§ The Final Algorithm

Lemmas <ref> and <ref>
naturally lead to the following algorithm.
We first define Γ_1 as k^(0),α⃗^(0) for some k^(0)∈ and α⃗^(0)∈^k^(0).
Then, we define Γ_2 as Γ_1k^(1),α⃗^(1) for some k^(1)∈ and α⃗^(1)∈^k^(1).
In this way, we can define Γ_i+1 as Γ_ik^(i),α⃗^(i) for some k^(i)∈ and α⃗^(i)∈^k^(i).

Fix k^(i)=6 for every i.
Note that, in the proof of 
Lemmas <ref> and <ref>,
parameter α⃗^(i)=(α^(i)_1,…, α^(i)_6)∈ [0,1]^6
 is set for each i
so that

it satisfies the system of equations,
a natural generalization of Eqs. (<ref>)(<ref>),

    1-α^(i)_1+α^(i)_1   =f_γ(α^(i)_6,1)
    
    f_γ(α^(i)_j-1,α^(i)_j)   =g_γ(α^(i)_j,α^(i)_j+1) (j=2,…, 6),

where
f_γ(x,y) 1/2y·x/y  +g_γ(x,y) and
g_γ (x,y) (1-y)+(y-x) log_2γ.


By numerically solving this system of equations 
for γ=3, we have β_6<2.83728
as shown in <ref>.
Then, numerically solving the system of equations
with γ=2.83728, we have β_6<2.79364.
In this way, we obtain a certain γ less than 2.77286 at the tenth composition
(see <ref>

in <ref>).

We therefore obtain the following theorem.

There exists 
a quantum algorithm that,
for the truth table of f0,1^n→0,1 given as input,
produces [n] in O^∗(γ^n) time and space
with probability 1-exp(-Ω(n)), where the constant γ is
at most 2.77286.











§ APPENDIX




§ PROOFS OF LEMMAS

<ref>


To show the first equality, assume k=π_I[I]. 
By the definition, we have

    I   =∑_i∈ Iifπ_I
    = ∑_i∈ I∖kifπ_I+kfπ_I.

The first term is equal to I∖ k, since otherwise
there exists π'∈Π(I) with  π'[I]=k and
π'[j]≠π_I[j] for some j∈ [I-1]
such that 

    ∑_i∈ Iifπ'   =
    ∑_i∈  I∖kifπ'+kfπ'
       < ∑_i∈  I∖kifπ_I+kfπ_I
    =I,

which contradicts the definition of I,
where we use kfπ'=kfπ_I by <ref>.

The remaining term kfπ_I is equal to
kfπ_I∖ k,k by <ref>. 
Thus, the first equality in the statement of the lemma holds.
Since I∖ k=∑_i∈ I∖ kifπ_I∖ k
by the definition, and <ref> implies that ifπ_I∖ k=ifπ_I∖ k,k for every i∈ I∖ k,
it holds that I∖ k=∑_i∈ I∖ kifπ_I∖ k,k.
Therefore, I∖ k+kfπ_I∖ k,k=∑_i∈ Iifπ_I∖ k,k. This implies that the second equality in the lemma.




<ref>
We focus on the simplest case of m=1 and write just I instead of I_1, since
it is straightforward to generalize the proof to the case of m≥ 2.




To show the first equality, assume k=π_I,J[I⊔ J]. 
By the definition, we have

    I,J   =∑_i∈ I⊔ Jifπ_I,J
    = ∑_i∈ I⊔ J∖kifπ_I,J+kfπ_I,J.

The first term is equal to I,J∖k, since otherwise
there exists π'∈Π(I,J) with 
π'[I⊔ J]=k and
π'[j]≠π_I,J[j] for some j∈ [I⊔ J-1]
such that 

    ∑_i∈ I⊔ Jifπ'   =
    ∑_i∈  I⊔ J∖kifπ'+kfπ'
       < ∑_i∈  I⊔ J∖kifπ_I,J+kfπ_I,J
    =I,J,

which contradicts the definition of I,J,
where we use kfπ'=kfπ_I,J by <ref>.
The remaining term kfπ_I,J is equal to
kfπ_I, J-k,k by <ref>. 
Thus, the first equality in the statement of the lemma holds.
Since I,J∖ k=∑_i∈ I⊔ J∖ kifπ_I,J∖ k by the definition, and <ref> implies that ifπ_I,J∖ k=ifπ_I,J∖ k,k for every i∈ I⊔ J∖ k,
it holds that I,J∖ k=∑_i∈ I⊔ J∖ kifπ_I,J∖ k,k.
Therefore, I,J∖ k+kfπ_I,J∖ k,k=∑_i∈ I⊔ Jifπ_I,J∖ k,k. This implies that the second equality in the lemma.










§ TWO-PARAMETER CASE

To improve the complexity bound further,
we use <ref> recursively.
Let k_1 and k_2 be  parameters fixed later 
such that 0<k_1<k_2<n.
By applying the lemma once, we have

    [n]=
    min_K_2⊂ [n], K'=k_2K_2
    +K_2,[n]∖ K_2[[n]∖ K_2]
    .


Then, we apply the lemma again to 
K' to obtain

    K_2=
    min_K_1⊂ K_2K_1=k_1K_1
    +K_1,K_2∖ K_1[K_2∖ K_1]
    .



To find the optimal K_1  from among k_2k_1 possibilities
and the optimal K_2 from among nk_2, we use the quantum minimum finding (<ref>).
As in the previous case, we perform the classical preprocess
that computes
K_1 for all K_1⊆ [n] with K_1= k_1.





If we set k_1=α_1 n and k_2=α_2n,
assuming that α_1<1/3, 
the total time complexity (up to a polynomial factor)
is

    T(n)   =∑_ℓ=1^α_1 n 2^n-ℓ·nℓ+L_3(n)
    ⪅  2^(1-α_1 )n+α_1 n+L_3(n),

where

    L_3(n)   =√(nα_2 n)L_2(n)+3^(1-α_2)n⪅ 2^1/2α_2n(L_2(n)+2^(1-α_2)(log_2 3)n),
    
    L_2(n)   =√(α_2 nα_1 n)L_1(n)+2^(1-α_2)n3^(α_2-α_1)n⪅
    2^1/2α_1/α_2α_2n(L_1(n)+2^(1-α_2)n+(α_2-α_1)(log_2 3)n),
    
    L_1(n)   =O^∗(1).

Intuitively, L_2(n) represents the time 
required for producing
K_1,K_2∖ K_1
for fixed K_2
such that
K_1,K_2
is minimum over all K_1  (⊂ K_2)
for the given collection of K_1 for all K_1.
Note that,
by <ref>,
the time required for computing K_1,K_2∖ K_1,[n]∖ K_2 from K_1,K_2∖ K_1 is O^∗(3^(1-α_2)n),
and the time required for computing
K_1,K_2∖ K_1 from K_1
is
O^∗(2^(1-α_2)n3^(α_2-α_1)n).

Since we are not interested in polynomial factors in T(n),
we ignore them in the following analysis of this system.

From Eqs. (<ref>) and (<ref>),
L_2(n) is at most
2^1/2α_1/α_2α_2n· 2^(1-α_2)n+(α_2-α_1)(log_2 3)n.
Suppose that L_2(n) equals this upper bound, since our goal is to upper-bound the complexity.
To balance the two terms on the right-hand side of <ref>, we set
L_2(n)=2^(1-α_2)(log_2 3)n,
which implies

    1/2α_2  α_1/α_2+
    (1-α_2) + (α_2-α_1)log_23
    =(1-α_2)log_2 3.

On the condition that this holds, L_3(n) is at most 
2^1/2α_2n2^(1-α_2)(log_2 3)n.
Suppose again that L_3(n) equals this upper bound.
To balance the two terms on the right-hand side in <ref>, we have L_3(n)=2^(1-α_1 )n+α_1 n, implying that

    (1-α_1)+α_1=1/2α_2+(1-α_2)log_2 3.


By numerically solving Eqs. (<ref>) and (<ref>), we have
α_1^∗=0.192755 and α_2^∗=0.334571.
Note that α_1^∗ is less than 1/3, as we assumed.
For α_1=α_1^∗ and α_2=α_2^∗,

    T(n)⪅2^(1-α_1^∗)+α_1^∗n =O^∗(γ_2),

where γ_2=2.8569< γ_1.



§ NUMERICAL OPTIMIZATION DATA







§ PSEUDO CODES OF ALGORITHMS








 §.§ Adaptation to ZDD


To adapt  to ZDD, it suffices to modify 
lines <ref> and <ref> in <ref> follows:



if u_1=0 then

_I, K-k,k[x_[n]∖ (I⊔ K)=]← u_0


















alpha

