Department of Computer Science, IIIT-Delhi, New Delhi, India. and Center for
Quantum Technologies, IIIT-Delhi, New Delhi<EMAIL_ADDRESS>of Computer Science, IIIT-Delhi, New Delhi<EMAIL_ADDRESS>Debajyoti Bera and Tharrmashastha SAPV <ccs2012> <concept>
<concept_id>10003752.10003753.10003758</concept_id> <concept_desc>Theory of
computation Quantum computation theory</concept_desc>
<concept_significance>500</concept_significance> </concept> <concept>
<concept_id>10003752.10003753.10003758.10010625</concept_id>
<concept_desc>Theory of computation Quantum query complexity</concept_desc>
<concept_significance>500</concept_significance> </concept> <concept>
<concept_id>10003752.10003777.10003784</concept_id> <concept_desc>Theory of
computation Quantum complexity theory</concept_desc>
<concept_significance>500</concept_significance> </concept> </ccs2012>
[500]Theory of computation Quantum computation theory [500]Theory of
computation Quantum query complexity [500]Theory of computation Quantum
complexity theory John Q. Open and Joan R. Access 2 42nd Conference on Very
Important Topics (CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016 Little
Whinging, United Kingdom 42 23

# Quantum Query-Space Lower Bounds Using Branching Programs

Debajyoti Bera  Tharrmashastha SAPV111Corresponding Author

###### Abstract

Branching programs are quite popular for studying time-space lower bounds.
Bera et al. recently introduced the model of generalized quantum branching
program aka. GQBP that generalized two earlier models of quantum branching
programs. In this work we study a restricted version of GQBP with the
motivation of proving bounds on the query-space requirement of quantum-query
circuits.

We show the first explicit query-space lower bound for our restricted version.
We prove that the well-studied ORn decision problem, given a promise that at
most one position of an $n$-sized Boolean array is a 1, satisfies the bound
$Q^{2}s=\Omega(n^{2})$, where $Q$ denotes the number of queries and $s$
denotes the width of the GQBP.

We then generalize the problem to show that the same bound holds for deciding
between two strings with a constant Hamming distance; this gives us query-
space lower bounds on problems such as Parity and Majority. Our results
produce an alternative proof of the $\Omega(\sqrt{n})$-lower bound on the
query complexity of any non-constant symmetric Boolean function.

###### keywords:

Branching Program, Time-Space Tradeoff, Quantum Computing, Quantum Complexity

###### category:

##  1 Introduction

Can a quantum algorithm make fewer queries by cleverly using lots and lots of
ancillæ? Could it be that a speedup in the number of queries in comparison to
classical algorithms (this is often quadratic) vanishes if only a few qubits
are available? This is the essence of the query-space tradeoff that motivated
this work.

These questions are central to understanding the resource requirements of
computational problems and, more importantly, the relationship between them.
These have been studied in the form of time-space tradeoffs for classical
algorithms. One of the favoured lines of attack for doing so is via analysis
of branching programs.

A (classical) branching program is a generalization of a decision tree;
structurally, a branching program looks like a dag in which the nodes are
labelled using input variables. On any input, a branching program starts at
the root node and evolves by querying the variable corresponding to the
current node and then following the edge corresponding to the value of that
variable. The input is accepted or rejected if the final node reached is
marked accept or reject. This model is attractive since it nicely
characterizes the space and time required by a Turing machine. The length (of
the longest path in the dag corresponding to an input) can be related to the
number of steps in a Turing machine taken on that input. The width, which is
the largest number of nodes in any level of the dag, can also be related to
the space complexity of a computation. Thus, branching programs are
traditionally used to prove lower bounds on space and the space-time tradeoffs
of various problems.

The study of space-time tradeoffs in the classical setting has been a long-
standing one. Despite numerous works on classical time-space trade-off
complexity in various settings ([1, 14, 25, 24, 22, 21, 19, 17]), Borodin et
al., were the first to study time-space lower bounds using branching programs,
but one that allowed only comparison-based queries ([13]). They showed that
any classical algorithm for sorting $N$ inputs using comparison queries
requires the time-space product $TS=\Omega(N^{2})$ where $T$ and $S$ are the
time and space complexities of the branching program, respectively. Later in
[11], Boroding et al. showed that any $R$-way branching program for sorting
$N$ integers with $R=N^{2}$ should satisfy $TS=\Omega(N^{2}/\log N)$. This was
followed by several time-space lower-bound results ([27, 3]) that used
branching programs for various matrix problems. Finally, Beame [7] showed that
any $R$-way BP for sorting with inputs in the range $[1,R]$ and $R\geq N$
requires $TS=\Omega(N^{2})$, which is optimal up to logarithmic factors.

The first result concerning classical query-space trade-off lower bounds for a
decision problem was proved in [12] for the element distinctness problem. They
showed that any $T$-query $S$-space deterministic comparison branching program
that decides element distinctness should satisfy $TS=\Omega(n^{3/2}\sqrt{\log
n})$. Yao, in [26], improved this to
$TS=\Omega(n^{2-\varepsilon(n)}),\varepsilon(n)=O(1/(\log n)^{1/2})$. While
showing any non-trivial time-space tradeoff lower bound for a natural problem
in general branching programs was hard, Beame et al. ([9]) constructed an
explicit function to obtain the first non-trivial time-space trade-off lower
bound in general branching programs. They also showed a non-trivial time-space
trade-off lower bound on the R-way branching program for another class of
explicitly constructed functions. This was followed by the work of Ajtai ([4])
in which, along with other results, they give lower bounds for non-
probabilistic algorithms for the element distinctness problem. They prove that
any two-sided error BP of subexponential size must have length
$T=\Omega\bigg{(}n\bigg{(}\frac{\log\log n}{\log\log\log n}\bigg{)}\bigg{)}.$
Using techniques that were essentially extensions of that in [4] and [9],
Beame et al. ([8]) proved that any algorithm for the randomized computation of
the element distinctness problem using space $S$ should satisfy
$T=\Omega\bigg{(}n\sqrt{\log(n/S)/\log\log(S)}\bigg{)}.$

In the quantum domain, some works prove time-space lower bounds for problems
like sorting([16]), Boolean matrix-vector multiplication([16]), matrix-matrix
multiplication([16]), solving a system of inequalities([5]) and $k$-disjoint
collisions problems([15]). However, to the best of our knowledge, no non-
trivial time-space lower bound is known for any decision problem in any
quantum model.

A quantum branching program would be a natural tool to derive space and space-
time lower bounds. There are three types of quantum branching programs to the
best of our knowledge. All the models maintain a global state (which could be
a superposition of well-defined states) that changes upon querying some input
bit. Nakanishi et al. [20] used their model (that we refer to as NQBP
following the nomenclature used by Bera et al. [10]) to separate ordered
bounded-width NQBP and ordered bounded-width probabilistic branching programs
(observe that a quantum branching program is by nature probabilistic). Ablayev
et al. [2] defined another model (that we refer to as AQBP), which they used
to prove that $NC^{1}$ (the class of $O(\log n)$-depth and polynomial-size
Boolean circuits) is contained in width-2 AQBPs. Very recently, Bera et al.
[10] designed another model (that we refer to as GQBP) that generalized both
the earlier models. They proved that problems in $NC^{1}$ can be solved by
width-2 GQBPs, and further, any symmetric Boolean function can be computed by
width-2 length-$O(n^{2})$ GQBP.

Since the GQBP generalizes the two other models, we chose that model to derive
our lower bounds.

##  2 Overview of Results

We summarise our contributions in this section.

1\. r-GQBP: Our motivation was to derive time-space lower bounds of well-
studied computational problems using the length and width dependencies of
GQBPs. However, the general nature of the structure and the transition
function of a GQBP made it challenging to bound.

Hence, we first define a restricted form of GQBP that we call r-GQBP.
Intuitively, the paths (in superposition) followed for every input are
identical, the only difference being the weights, rather the amplitudes, on
the edges. Despite the rigid structure, we could prove that r-GQBPs can
simulate any quantum query circuit and vice versa as efficiently as
(unrestricted) GQBPs.

2\. Lower-bound for OR: The OR problem is one of the typical problems when it
comes to proving a lower bound; given an $n$-bit Boolean array, the problem is
to determine if there is any 1 in the array. We prove a trade-off between the
length and the width of any r-GQBP, solving a promise version of the OR
problem in which the array has either one 1 or no ones.

######  Theorem 2.1.

Any r-GQBP of length $L$ and width $s$ that solves the Promise-OR problem has
to satisfy $L=\Omega\bigg{(}\frac{n}{\sqrt{s}}\bigg{)}$.

3\. Lower-bound for Parity and Majority: The OR problem is a special case of
the $(k,k+\delta)$-Hamming decision problem, which is about deciding whether a
binary string has $k$ ones or $k+\delta$ ones, given the promise that one of
them must hold. Next, we prove an identical length-width lower bound on the
Hamming decision problem, too. This gives us identical bounds for functions
such as Parity, AND, Majority, etc.

######  Theorem 2.2.

Any r-GQBP of length $L$ and width $s$ that solves the ($k,k+\delta$) Hamming
Decision problem has to satisfy
$L=\Omega\bigg{(}\frac{n}{\delta\sqrt{s}}\bigg{)}$.

4\. Lower-bound for non-constant symmetric function: Using the above results
and an observation about non-constant symmetric functions, we are able to
prove the following trade-off.

######  Theorem 2.3.

Any ($s,L$)-r-GQBP that computes a non-constant symmetric function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ has to satisfy
$L=\Omega\bigg{(}\frac{n}{\sqrt{s}}\bigg{)}$.

Beals et al. [6] introduced the polynomial method for quantum lower bounds;
they showed that the number of queries, denoted $Q(f)$, to compute any non-
constant symmetric function $n$-bit function $f$ is $\Omega(\sqrt{n})$
222Technically, their bound is a bit stronger. But their bound collapses to
this one for functions that flip their value on inputs with constant Hamming
weights or Hamming weights close to $n$., and this is without any restriction
on the number of qubits. Using the above theorem and our quantum circuit to
GQBP conversion, we could prove the same lower bound with a restriction on
space usage.

######  Theorem 2.4.

Any quantum query circuit that computes a non-constant symmetric function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ with $O(\log n)$ qubits has to satisfy
$Q(f)=\Omega(\sqrt{n})$.

##  3 Background: Generalized Quantum Branching Programs

There are a few different models of quantum branching programs all of which
try to bring some quantum feature to the classical model. The first model was
introduced by Nakanishi et al. that allows the state transitions to follow
multiple paths (in superposition) [20]; however, to decide acceptance and
rejection, a measurement is performed after every transition. They were able
to show that there exists an ordered bounded-width NQBP that computes the
“Half Hamming” weight function — a function that indicates if the Hamming
weight of the input is $n/2$, but no ordered bounded-width probabilistic
branching program can compute the same.

Later, Ablayev et al. introduced another quantum branching program model [2].
They showed that while any ordered binary decision diagram has to be of a
width at least $p_{n}$ to compute the $Mod_{p_{n}}$ function, which indicates
if the Hamming weight of the input is divisible by the prime $p_{n}$, there is
an $O(\log(p_{n}))$ width AQBP that computes the $Mod_{p_{n}}$ function with
one-sided error. In addition, they showed that any language in the $NC1$
complexity class is exactly decidable by width-2 AQBPs of polynomial length.

Sauerhoff et al. presented a few interesting results concerning a restricted
version of NQBPs [23]. Recently, Maslov et al showed that any symmetric
Boolean function can be computed by some AQBP of width $2$ and length
$O(n^{2})$ [18].

Generalized quantum branching programs were recently introduced by Bera et. al
[10].

######  Definition 3.1 (Generalized quantum branching program (GQBP)).

A quantum branching program is a tuple $(Q,E,\ket{v_{0}},L,\delta,F)$ where

  * •

$Q=\bigcup_{i=0}^{l}Q_{i}$ is a set of nodes where $Q_{i}$ is the set of nodes
at level $i$.

  * •

$E$ is a set of edges between the nodes in $Q$ such that $(Q,E)$ is a levelled
directed acyclic multi-graph.

  * •

$\ket{v_{0}}$ is the initial state which is a superposition of the nodes in
$Q_{0}$.

  * •

$\delta:Q\times\\{0,1\\}\times Q\xrightarrow{}\mathbb{C}$ is a quantumly well-
behaved transition function.

  * •

$L:Q\xrightarrow{}\\{1,2\cdots,n\\}$ is a function that assigns a variable to
each node in $Q\setminus F$.

  * •

$F\subseteq Q$ is the set of terminal nodes.

Let’s understand the evolution of GQBP since our results are in this model.
Let $x$ denote the input string. Consider any node $v$ at some level; $v$ is
labelled with some input variable, say $x_{i}$, that can be derived as
$i=L(v)$. There are two sets of outgoing transitions from $v$, one
corresponding to $x_{i}=0$ and another corresponding to $x_{i}=1$, and each of
them is to one or more nodes in the next level. Furthermore, each transition,
say $v\begin{subarray}{c}0\\\ \mapsto\end{subarray}w$ is associated with a
complex $\delta(v,0,w)$; the intuition being that, if $x_{i}=0$, the state
will be changed to a superposition of all the target nodes of transitions
corresponding to 0, and the amplitudes of the superpositions will be specified
by the corresponding $\delta$ values. The notion of “quantum well-behavedness”
essentially ensures that the superposition is a quantum state. We can state
the process more formally as follows.

  1. 1.

Given access to an input $x$ using oracle $O_{x}$, define
$U^{O_{x}}_{i}:\mathcal{H}(d)\xrightarrow{}\mathcal{H}(d)$ for
$i\in\\{1,2,\cdots,l\\}$ that has query access to $O_{x}$ as

$U^{O_{x}}_{i}\ket{v}=\sum_{v^{\prime}\in
Q_{i}}\delta(v,O_{x}(L(v)),v^{\prime})\ket{v^{\prime}}$

for any $\ket{v}\in Q_{i-1}$ where $\mathcal{H}(d)$ is the Hilbert space on
$d$ dimensions with $d$ as the width of the QBP.

  2. 2.

Start at $\ket{v_{0}}$.

  3. 3.

For $i=1$ to $l$, perform $\ket{\psi_{i}}=U^{O_{x}}_{i}\ket{\psi_{i-1}}$ where
$\ket{\psi_{0}}=\ket{v_{0}}$.

  4. 4.

Measure $\ket{\psi_{l}}$ in the standard basis. If the observe node is in $F$
then the input is accepted, else rejected.

We say that a QBP $\mathcal{G}$ exactly computes a function $f$ if for all
inputs $x$, $\mathcal{G}$ accepts $x$ if $f(x)=1$ and rejects $x$ if $f(x)=0$,
both with probability $1$. Similarly, a QBP $\mathcal{G}$ is said to bounded-
error compute a $f$ if for all inputs $x$, $\mathcal{G}$ accepts $x$ if
$f(x)=1$ and rejects $x$ if $f(x)=0$, both with probability at least $2/3$. We
stick to the latter in this work; wherever we talk about a GQBP solving some
function, we mean that in the bounded-error sense.

There are two primary complexity measures of a GQBP. The length of a GQBP is
the length of the longest path from the root node to any single node. The
width of a GQBP is the maximum number of nodes on any level of the GQBP. A
GQBP $P$ is said to be a ($w,l$)-GQBP if $P$ is a $w$ width $l$ length GQBP.

In addition to introducing the GQBP model, Bera et al. demonstrated that the
GQBP model generalizes the NQBP and the AQBP models. More specifically, they
showed that any ($w,l$)-AQBP is also a ($w,l$)-GQBP and that any $s$-sized
$l$-length NQBP can be simulated exactly by a ($s,l$)-GQBP. However, neither
GQBP nor the other models have been used to prove length or width lower bounds
on any explicit function.

##  4 Restricted-GQBP

In this section, we introduce a restricted version of the GQBP model called
the restricted-GQBP (or, r-GQBP) and show some results concerning them. More
importantly, we show that the r-GQBP model is equivalent to the quantum query
circuit model. This equivalence motivates the investigation of query-space
lower bounds on the r-GQBPs, which could be translated to query-space lower
bounds on quantum query circuits.

######  Definition 4.1.

A GQBP is called a restricted-GQBP (or r-GQBP) if, for any node $m$ on any
level, its transition vectors $v^{0}_{m}$ and $v^{1}_{m}$, corresponding to
the $0$ and $1$ transitions, differ only by a phase, i.e., there exists some
$\theta$ such that $v^{1}_{m}=e^{i\theta}v^{0}_{m}$.

$\ldots$$\ldots$$x_{2}$$x_{3}$$x_{0}$$x_{1}$

$x_{n\text{-}2}$

$x_{n\text{-}1}$

$0$$1$$\frac{1}{\sqrt{2}}$$\frac{1}{\sqrt{2}}$1-11-11-11-11-11-1+$-$+$-$+$-$$-$+

Figure 1: The GQBP presented in [10] for the $Parity_{n}$ problem (reproduced
here with the authors’ kind permission) was found to be an r-GQBP. $+$ denotes
$\tfrac{1}{\sqrt{2}}$ and $-$ denotes $-\tfrac{1}{\sqrt{2}}$. The green
(dotted) and the red (dashed) lines correspond to the $0$ and the $1$
transitions.

This restriction on the transition vectors of each node presents a nice
structure to the r-GQBP model, providing the following lemma as a consequence.
Later, we exploit this structure to prove query-space lower bounds on r-GQBP
and even for quantum query circuits. See Figure 2 for an illustration of the
next lemma.

$x_{i}$$x_{j}$$x_{i}^{\prime}$$x_{j}^{\prime}$$\alpha_{0}$$\alpha_{1}$$a$$\gamma_{0}a$$b$$\gamma_{0}b$$c$$\gamma_{1}c$$d$$\gamma_{1}d$

Initial edge$0$-edge$1$-edge$0/1$-edge

(a) A two-layered r-GQBP $R$.

$x_{i}$$x_{j}$$x_{0}$$x_{0}$$x_{i^{\prime}}$$x_{j^{\prime}}$$\alpha_{0}$$\alpha_{1}$$1$$\gamma_{0}$$1$$\gamma_{1}$$a$$b$$c$$d$

(b) An equivalent three-layered r-GQBP $R^{\prime}$.

Figure 2: Figure (a) shows a two-layered one-transition r-GQBP $R$. Figure (b)
is a three-layered two-transition r-GQBP $R^{\prime}$ that is equivalent to
$R$. Note that the first transition of $R^{\prime}$ is query-dependent,
whereas the second transition of $R^{\prime}$ is query-independent.

######  Lemma 4.2.

The transition between any two levels of an r-GQBP can be split into two
transitions between three levels such that the transition between the first
and the second levels is query-dependent, and the transition between the
second and the third levels is query-independent.

######  Proof 4.3.

For simplicity consider a two leveled r-GQBP $P=(Q,E,\ket{v_{0}},L,\delta,F)$
of width $s$. Let $M_{1}=\\{m_{1,1},\cdots,m_{1,s}\\}$ and
$M_{2}=\\{m_{2,1},\cdots,m_{2,s}\\}$ be the nodes in the first and the second
levels of $P$ respectively. In addition, let $v_{k}^{0}$ and $v_{k}^{1}$ be
the transition vectors corresponding to the $0$ and $1$ transitions of the
node $m_{1,k}$. More formally, let the transition function $\delta$ be defined
as $\delta(m_{1,k},a,m_{2,k^{\prime}})=v_{k}^{a}[k^{\prime}]$. Recall that at
any node $m_{1,k}$, the transition vectors $v_{k}^{0}$ and $v_{k}^{1}$ are
related as $v_{k}^{1}=e^{i\theta_{k}}v_{k}^{0}$ for all $k$. Now, introduce a
new set of $s$ nodes $\hat{M}=\\{\hat{m}_{1,1},\cdots,\hat{m}_{1,s}\\}$.
Define a transition function $\delta^{\prime}$ as
$\delta^{\prime}(\hat{m}_{1,k},a,m_{2,k^{\prime}})=v_{k}^{0}[k^{\prime}]$ and

$\delta^{\prime}(m_{1,k},a,\hat{m}_{1,k^{\prime}})=\begin{cases}e^{i\theta_{k}},&\text{if
}k=k^{\prime}\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\ a=1\\\
1,&\text{if }k=k^{\prime}\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\
a=0\\\ 0,&\text{else}.\end{cases}$

Notice that for any node $\hat{m}_{1,k}$ in level two, the transition vector
corresponding to that node is $v^{0}_{k}$ and is independent of the value $a$
of the query index.

Let $Q^{\prime}=M_{1}\cup\hat{M_{1}}\cup M_{2}$ and
$E^{\prime}=\\{(v,v^{\prime}):v\in M_{1},v^{\prime}\in\hat{M_{1}},\text{ or
}v\in\hat{M_{1}},v;\in M_{2}\\}$. Finally, define a variable assignment
function $L^{\prime}:Q^{\prime}\rightarrow\\{1,2,\cdots,n\\}$ as
$L^{\prime}(v)=L(v)$ if $v\in Q$ and $L^{\prime}(v)=1$ if $v\notin Q$. Using
these definitions, construct a new r-GQBP
$R=(Q^{\prime},E^{\prime},\ket{v_{0}},L^{\prime},\delta^{\prime},F)$. To prove
the theorem, it suffices to show that for any input $X\in\\{0,1\\}^{n}$ and an
arbitrary initial state $\ket{v_{0}}$, the final states of $P$ and $R$ are
identical.

Let $\ket{v_{0}}=\sum_{k\in[s]}\alpha_{s}\ket{m_{1,k}}$ and let
$X\in\\{0,1\\}^{n}$ be any arbitrary input. Then, the state of $P$ obtained
after evolving $\ket{v_{0}}$ with $\delta$ will be

$\displaystyle\ket{\phi_{P}}$
$\displaystyle=U^{O_{X}}_{1}\ket{v_{0}}=\sum_{k\in[s]}\alpha_{k}U^{O_{X}}_{P}\ket{m_{1,k}}=\sum_{k\in[s]}\alpha_{k}\sum_{k^{\prime}\in[s]}\delta(m_{1,k},X_{L(m_{1,k})},m_{2,k^{\prime}})\ket{m_{2,k^{\prime}}}$
$\displaystyle=\sum_{k\in[s]}\alpha_{k}\sum_{k^{\prime}\in[s]}v_{k}^{X_{\tau_{k}}}[k^{\prime}]\leavevmode\nobreak\
\ket{m_{2,k^{\prime}}}=\sum_{k^{\prime}\in[s]}\bigg{[}\sum_{k\in[s]}\alpha_{k}v_{k}^{X_{\tau_{k}}}[k^{\prime}]\bigg{]}\ket{m_{2,k^{\prime}}}.$

where $\tau_{k}=L(m_{1,k})$, for $k\in[s]$, is the query index corresponding
to the node $m_{1,k}$.

In the r-GQBP $R$, the state obtained after the first transition is

$\displaystyle\ket{\psi}$ $\displaystyle=U^{\prime
O_{X}}_{1}\ket{v_{0}}=\sum_{k\in[s]}\alpha_{k}U^{\prime
O_{X}}_{R}\ket{m_{1,k}}=\sum_{k\in[s]}\alpha_{k}\sum_{k^{\prime}\in[s]}\delta^{\prime}(m_{1,k},X_{L(m_{1,k})},\hat{m}_{1,k^{\prime}})\ket{\hat{m}_{1,k^{\prime}}}$
$\displaystyle=\sum_{k\in[s]}\alpha_{k}e^{i\theta_{k}\cdot
X_{\tau_{k}}}\ket{\hat{m}_{1,k}}$

Then, the final state after the second transition can be given as

$\displaystyle\ket{\phi_{R}}$ $\displaystyle=U^{\prime
O_{X}}_{2}\ket{\psi}=\sum_{k\in[s]}\alpha_{k}e^{i\theta_{k}\cdot
X_{\tau_{k}}}U^{\prime
O_{X}}_{2}\ket{\hat{m}_{1,k}}=\sum_{k\in[s]}\alpha_{k}e^{i\theta_{k}\cdot
X_{\tau_{k}}}\sum_{k^{\prime}\in[s]}\delta^{\prime}(\hat{m}_{1,k},L(\hat{m}_{1,k}),m_{2,k^{\prime}})\ket{m_{2,k^{\prime}}}$
$\displaystyle=\sum_{k^{\prime}\in[s]}\bigg{[}\sum_{k\in[s]}\alpha_{k}e^{i\theta_{k}\cdot
X_{\tau_{k}}}\delta^{\prime}(\hat{m}_{1,k},X_{1},m_{2,k^{\prime}})\bigg{]}\ket{m_{2,k^{\prime}}}=\sum_{k^{\prime}\in[s]}\bigg{[}\sum_{k\in[s]}\alpha_{k}e^{i\theta_{k}\cdot
X_{\tau_{k}}}v^{0}_{k}[k^{\prime}]\bigg{]}\ket{m_{2,k^{\prime}}}$

Note that if $X_{\tau_{k}}=0$, then
$e^{i\theta_{k}X_{\tau_{k}}}v^{0}_{k}[k^{\prime}]=v^{0}_{k}[k^{\prime}]$.
Whereas if $X_{\tau_{k}}=1$, then
$e^{i\theta_{k}X_{\tau_{k}}}v^{0}_{k}[k^{\prime}]=e^{i\theta_{k}}v^{0}_{k}[k^{\prime}]=v^{1}_{k}[k^{\prime}]$.
So, we have
$e^{i\theta_{k}X_{\tau_{k}}}v^{0}_{k}[k^{\prime}]=v^{X_{\tau_{k}}}_{k}[k^{\prime}]$.
This gives us

$\displaystyle\ket{\phi_{R}}$
$\displaystyle=\sum_{k^{\prime}\in[s]}\bigg{[}\sum_{k\in[s]}\alpha_{k}e^{i\theta_{k}\cdot
X_{\tau_{k}}}v^{0}_{k}[k^{\prime}]\bigg{]}\ket{m_{2,k^{\prime}}}=\sum_{k^{\prime}\in[s]}\bigg{[}\sum_{k\in[s]}\alpha_{k}v^{X_{\tau_{k}}}_{k}[k^{\prime}]\bigg{]}\ket{m_{2,k^{\prime}}}=\ket{\phi_{P}}.$

This shows that any transition between two levels of an r-GQBP can be split
into a query-dependent transition followed by a query-independent transition.

While Lemma 4.2 deals with splitting one transition between two layers, it can
be seen that this can be easily extended to an r-GQBP of any length. Thus, we
obtain the following corollary.

######  Corollary 4.4.

For any r-GQBP $P$ of length $l$ and width $s$, there exists an r-GQBP $Q$ of
length $2l$ and width $s$ such that

  1. 1.

The levels of $Q$ alternate between a query-dependent level and a query-
independent level, with the first level being query-dependent.

  2. 2.

$Q$ is equivalent to $P$, i.e, $Q$ exactly simulates $P$ and $P$ exactly
simulates $Q$.

######  Proof 4.5.

Let $P$ be an r-GQBP of length $l$ and width $s$. We can obtain a new r-GQBP
$Q$ by using Lemma 4.2 and replacing each transition in $P$ with two
transitions, one query-dependent, followed by a query-independent transition
in $Q$. Since the number of transitions in the original r-GQBP $P$ is $l$, the
number of transitions in $Q$ obtained as a result of replacing the transitions
is $2l$. So, the length of $Q$ is $2l$. The width, however, remains the same
as that of $P$. The equivalence of $P$ and $Q$ is a direct consequence of
Lemma 4.2.

### Equivalence of r-GQBPs and quantum query circuits:

We now show the equivalence between r-GQBPs and quantum query circuits.

######  Theorem 4.6.

Any $q$-qubit $t$-query quantum query circuit $C$ can be exactly simulated by
a $2^{q}$-width $t$-length r-GQBP.

We first explain the reduction at an intuitive level before proceeding with
the formal proof. Let $C$ be a query circuit that makes $t$ queries and uses
$q$ qubits. Then $C$ can be decomposed into input-independent unitary gates
that act on $q$ qubits and input-dependant oracle gates that, w.l.o.g. act on
the first $\log n$ qubits, as $C=U_{t}(O_{x}\otimes\mathbb{I}^{\otimes{q-\log
n}})U_{t-1}\cdots U_{1}(O_{x}\otimes\mathbb{I}^{\otimes{q-\log n}})U_{0}$. To
understand the reduction better, consider an encoding between the set of basis
states $\\{\ket{0},\ket{1},\cdots,\ket{2^{q}-1}\\}$ and the set of states of
the branching program
$\\{\ket{v_{i,0}},\ket{v_{i,1}},\cdots,\ket{v_{i,2^{q}-1}}\\}$ for each level
$i$.

Now, the idea is to define the start state $\ket{v_{0}}$, the labelling
function $L$ and the transition function such that if the state of the circuit
after the unitary $U_{i}$ is
$\ket{\psi_{C}}=\sum_{j\in[2^{q}]}\alpha_{i,j}\ket{j}$, then the state of the
r-GQBP should be $\ket{\psi_{R}}=\sum_{j\in[2^{q}]}\alpha_{i,j}\ket{v_{i,j}}$.
To do this, we set the initial state of $R$ as the encoded state corresponding
to the circuit state $U_{0}\ket{0^{q}}$ and define a labelling function and a
transition function that mimics the operation
$U_{i}(O_{x}\otimes\mathbb{I}^{\otimes q-\log n})$ at the $i^{th}$ transition.
Finally, if the query circuit accepts the input on observing a state $\ket{j}$
after measuring the final state in the computational basis, then we include
the node $v_{l,j}$ to the accept set $F$ of the r-GQBP $R$. We present the
formal proof below.

######  Proof 4.7.

Let $C$ be a $q$-qubit $t$-query quantum query circuit with access to a
standard phase oracle $O_{x}$ that acts as $O_{x}\ket{i}=(-1)^{X_{i}}\ket{i}$.
Wlog. the action of $O_{x}$ can be restricted to the first $\log n$ qubits of
$C$. It is standard to represent such a query circuit as
$C=\tilde{U}_{t}(O_{x}\otimes\mathbb{I}^{\otimes q-\log
n})\tilde{U}_{t-1}\cdots\tilde{U}_{1}(O_{x}\otimes\mathbb{I}^{\otimes q-\log
n})\tilde{U_{0}}$. Let $F_{C}$ be the set of the basis states, which, when
obtained post the final measurement, the circuit accepts the input.

Now, construct a r-GQBP $R=(Q,E,\ket{v_{0}},L,\delta,F)$ as follows. Set
$Q=\\{v_{i,j}:i\in\\{0,1,\cdots,t\\},j\in\\{0,1,\cdots,2^{q}-1\\}\\}$ and
$E=\\{(v_{i,j},v_{i+1,j^{\prime}}):i\in\\{0,1,\cdots,t-1\\},j,j^{\prime}\in\\{0,1,\cdots,2^{q}-1\\}\\}$.
For each level $i$, consider the encoding $\mathcal{E}_{i}$ that encodes a
state in a circuit to a superposition of nodes in an r-GQBP as
$\mathcal{E}_{i}\big{(}\sum_{j\in[2^{q}]}\alpha_{j}\ket{j}\big{)}=\sum_{j\in[2^{q}]}\alpha_{j}\ket{v_{i,j}}$
for any
$(\alpha_{0},\alpha_{1},\cdots,\alpha_{2^{q}-1})\in\mathbb{C}^{2^{q}}$. Note
that this encoding is a bijection; we denote its inverse as
$\mathcal{E}^{-1}_{i}$. Let $\ket{v_{0}}=\mathcal{E}_{0}(U_{0}\ket{0^{q}})$.
Set $F$ such that $F$ contain nodes of the final level corresponding to the
basis states in $F_{C}$, i,e, $F=\\{\mathcal{E}_{t}(j):\ket{j}\in
F_{C}\\}=\\{v_{t,j}:\ket{j}\in F_{C}\\}$. Now, define the transition function
$\delta$ as follows:

$\delta(v_{i,j},a,v_{p,q})=\begin{cases}\tilde{U}_{i}[q,j],&\text{if $a=0$ and
$p=i+1$}\\\ -\tilde{U}_{i}[q,j],&\text{if $a=1$ and $p=i+1$}\\\
0,&\text{else}\end{cases}$

Finally, set the variable assignment function $L$ as $L(v_{i,j})=j_{\lvert\log
n}$ where $j_{\lvert\log n}$ denotes the first $\log n$ bits of the bitwise
representation of $j$. Notice that for any node $v_{i,j}$, the transition
vector corresponding to the $0$ transition is
$w^{0}_{v_{i,j}}=[\tilde{U}_{i}[0,j],\tilde{U}_{i}[1,j],\cdots,\tilde{U}_{i}[2^{q}-1,j]]$
and that corresponding to the $1$ transition is
$w^{1}_{v_{i,j}}=[-\tilde{U}_{i}[0,j],-\tilde{U}_{i}[1,j],\cdots,-\tilde{U}_{i}[2^{q}-1,j]]$.
Clearly, with $w^{1}_{v_{i,j}}=-w^{0}_{v_{i,j}}$, one of the primary
conditions of an r-GQBP is satisfied.

Due to how we have defined the set of accept states $F$, it now suffices to
show that the state of the r-GQBP $R$ after the final transition is analogous
to the final state of the circuit $C$. Mathematically, we need to show that
$\ket{\psi_{f}}=\mathcal{E}_{t}(\ket{\phi_{f}})$ where $\ket{\psi_{f}}$ and
$\ket{\phi_{f}}$ are the final states of the r-GQBP and the circuit,
respectively. At any point in a r-GQBP, $i+1^{th}$ transition will be
performed at the level $i$ of the r-GQBP, i.e., when the state of the r-GQBP
is a superposition of the nodes in level $i$. For instance, $1^{st}$
transition is performed at level $0$, $2^{nd}$ transition at level $1$ and so
on. At any level $i$, the unitary corresponding to the $i+1^{th}$ transition
for an input $X$ can be given as
$U^{O_{X}}_{i+1}=\big{[}(w_{v_{i,0}}^{\gamma_{i,0}})^{T}(w_{v_{i,1}}^{\gamma_{i,1}})^{T}\cdots(w_{v_{i,2^{q}-1}}^{\gamma_{i,1}})^{T}\big{]}_{2^{q}\times
2^{q}}$ where $\gamma_{i,j}=X_{L(v_{i,j})}$ is the value obtained on querying
the index corresponding to the node $v_{i,j}$ and $(w_{v_{i,j}}^{a})^{T}$
denotes the column vector corresponding to the $a$-transition at the node
$v_{i,j}$. Since, $R$ is a r-GQBP, we have,
$U^{O_{X}}_{i+1}=\big{[}(-1)^{\gamma_{i,0}}(w_{v_{i,0}}^{0})^{T}\leavevmode\nobreak\
\leavevmode\nobreak\
(-1)^{\gamma_{i,1}}(w_{v_{i,1}}^{0})^{T}\cdots(-1)^{\gamma_{i,2^{q}-1}}(w_{v_{i,2^{q}-1}}^{0})^{T}\big{]}=\big{[}(w_{v_{i,0}}^{0})^{T}\leavevmode\nobreak\
\leavevmode\nobreak\
(w_{v_{i,1}}^{0})^{T}\cdots(w_{v_{i,2^{q}-1}}^{0})^{T}\big{]}\cdot
diag\big{(}(-1)^{\gamma_{i,1}},(-1)^{\gamma_{i,1}},\cdots,(-1)^{\gamma_{i,2^{q}-1}}\big{)}$
where $diag(\cdots)$ denotes the diagonal matrix. However, notice that the
matrix $\big{[}(w_{v_{i,0}}^{0})^{T}\leavevmode\nobreak\ \leavevmode\nobreak\
(w_{v_{i,1}}^{0})^{T}\cdots(w_{v_{i,2^{q}-1}}^{0})^{T}\big{]}$ is exactly
$\tilde{U}_{i+1}$. Moreover, since
$(-1)^{\gamma_{i,j}}=(-1)^{X_{L(v_{i,j})}}=(-1)^{X_{\hat{j}}}$ where
$\hat{j}=j_{\lvert\log n}$ for any basis state $\ket{j}$ the matrix given by
$diag\big{(}(-1)^{\gamma_{i,1}},(-1)^{\gamma_{i,1}},\cdots,(-1)^{\gamma_{i,2^{q}-1}}\big{)}=D\text{
(say)}$ can be given as
$D=diag\big{(}(-1)^{X_{\hat{0}}},(-1)^{X_{\hat{1}}},\cdots,(-1)^{X_{\hat{j}}}\big{)}$.
So, in a very loose sense, the operator $D$ adds a phase to $\ket{v_{i,j}}$
depending only on the first $\log n$ bits of $j$ that serve as the index
address. Clearly, $D$ mimics the operator $O_{X}\otimes\mathbb{I}^{\otimes
q-\log n}$. Now, if we can show that $U_{i+1}^{O_{x}}$ indeed mimics the
action of $\tilde{U}_{i+1}(O_{X}\otimes\mathbb{I}^{\otimes q-\log n})$, i.e.,
$\mathcal{E}_{i+1}\big{(}\tilde{U}_{i+1}(O_{X}\otimes\mathbb{I}^{\otimes
q-\log n})\ket{\phi_{i}}\big{)}=U_{i+1}^{O_{x}}\ket{\psi_{i}}$, then we are
done. Let $\ket{\phi_{i}}=\sum_{j\in[2^{q}]}\alpha_{i,j}\ket{j}$ be the state
of the circuit after the $i^{th}$ and let
$\ket{\psi_{i}}=\mathcal{E}_{i}(\ket{\phi_{i}})=\sum_{j\in[2^{q}]}\alpha_{i,j}\ket{v_{i,j}}$
be the state of the r-GQBP at level $i$. We have established that
$\ket{\psi_{0}}=\ket{v_{0}}=\mathcal{E}_{0}(U_{0}\ket{0^{q}})=\mathcal{E}_{0}(\ket{\phi_{0}})$.

Now, the action of $\tilde{U}_{i+1}$ and $O_{x}$ on the state $\ket{\phi_{i}}$
can be given as

$\displaystyle\tilde{U}_{i+1}(O_{X}\otimes\mathbb{I}^{\otimes q-\log
n})\ket{\phi_{i}}$
$\displaystyle=\tilde{U}_{i+1}(O_{X}\otimes\mathbb{I}^{\otimes q-\log
n})\sum_{j\in[2^{q}]}\alpha_{i,j}\ket{j}$
$\displaystyle=\tilde{U}_{i+1}\sum_{j\in[2^{q}]}(-1)^{X_{\hat{j}}}\alpha_{i,j}\ket{j}$
$\displaystyle=\sum_{j\in[2^{q}]}(-1)^{X_{\hat{j}}}\alpha_{i,j}\sum_{k\in[2^{q}]}w_{v_{i},j}^{0}[k]\ket{k}$
$\displaystyle=\sum_{k\in[2^{q}]}\Bigg{[}\sum_{j\in[2^{q}]}(-1)^{X_{\hat{j}}}\alpha_{i,j}w_{v_{i},j}^{0}[k]\Bigg{]}\ket{k}$

So, we get

$\displaystyle\mathcal{E}_{i+1}\big{(}\tilde{U}_{i+1}(O_{X}\otimes\mathbb{I}^{\otimes
q-\log n})\ket{\phi_{i}}\big{)}$
$\displaystyle=\mathcal{E}_{i+1}\Bigg{(}\sum_{k\in[2^{q}]}\Bigg{[}\sum_{j\in[2^{q}]}(-1)^{X_{\hat{j}}}\alpha_{i,j}w_{v_{i},j}^{0}[k]\Bigg{]}\ket{k}\Bigg{)}$
$\displaystyle=\sum_{k\in[2^{q}]}\Bigg{[}\sum_{j\in[2^{q}]}(-1)^{X_{\hat{j}}}\alpha_{i,j}w_{v_{i},j}^{0}[k]\Bigg{]}\ket{v_{i+1,k}}$

Next, the action of the transition defined by the unitary $U_{i+1}^{O_{x}}$ on
the state $\ket{\psi_{i}}$ of the r-GQBP $R$ is

$\displaystyle U_{i+1}^{O_{x}}\ket{\psi_{i}}$
$\displaystyle=U_{i+1}^{O_{x}}\sum_{j\in[2^{q}]}\alpha_{i,j}\ket{v_{i,j}}=\sum_{j\in[2^{q}]}\alpha_{i,j}U_{i+1}^{O_{x}}\ket{v_{i,j}}$
$\displaystyle=\sum_{j\in[2^{q}]}\alpha_{i,j}\sum_{k\in[2^{q}]}(-1)^{\gamma_{i,j}}w_{v_{i,j}}^{0}[k]\ket{v_{i+1,k}}$
$\displaystyle=\sum_{k\in[2^{q}]}\Bigg{[}\sum_{j\in[2^{q}]}(-1)^{\gamma_{i,j}}\alpha_{i,j}w_{v_{i,j}}^{0}[k]\Bigg{]}\ket{v_{i+1,k}}$

Here, $(-1)^{\gamma_{i,j}}=(-1)^{X_{L(v_{i,j})}}$. But we have defined $L$
such that $L(v_{i,j})=j_{\lvert\log n}=\hat{j}$. So, we have
$(-1)^{\gamma_{i,j}}=(-1)^{X_{\hat{j}}}$. This gives

$\displaystyle U_{i+1}^{O_{x}}\ket{\psi_{i}}$
$\displaystyle=\sum_{k\in[2^{q}]}\Bigg{[}\sum_{j\in[2^{q}]}(-1)^{X_{\hat{j}}}\alpha_{i,j}w_{v_{i,j}}^{0}[k]\Bigg{]}\ket{v_{i+1,k}}=\mathcal{E}_{i+1}\big{(}\tilde{U}_{i+1}(O_{X}\otimes\mathbb{I}^{\otimes
q-\log n})\ket{\phi_{i}}\big{)}.$

Since this is true for all levels $i$, we have
$\ket{\psi_{t}}=\mathcal{E}_{t}(\ket{\phi_{t}})$. This shows that the r-GQBP
$R$ exactly computes the quantum circuit $C$.

In addition to the reduction from a quantum query circuit to an r-GQBP, we
also found a reduction from an r-GQBP to a quantum circuit. The reduction is
presented as Theorem 4.8.

######  Theorem 4.8.

Any $w$-width $l$-length r-GQBP $R$ can be exactly simulated by a
$\log(w)+\log(n)+1$-qubit $2l$-query quantum query circuit.

######  Proof 4.9.

Let $R=(Q,E,\ket{v_{0}},L,\delta,F)$ be an ($w,l$)-r-GQBP that we would like
to simulate. For the mechanics of the proof, we define three families of
unitaries - one each corresponding to the query-independent transitions,
labelling function and phase inclusion.

  * •

First, define a family of $\log(w)$-qubit unitaries
$\\{\hat{U}_{p}\\}_{p\in\\{1,\cdots,l\\}}$ where $U_{p}$ is defined as
$\hat{U}_{p}\ket{q}=\sum_{q^{\prime}\in[w]}\delta(v_{p,q},0,v_{p+1,q^{\prime}})\ket{q^{\prime}}$,
for any $q\in[w]$. Now, let
$\ket{v_{0}}=\sum_{q\in[w]}\alpha_{0,q}\ket{v_{0,q}}$ be the initial state of
the r-GQBP $R^{\prime}$. Then, define $\hat{U}_{0}$ such that
$\hat{U}_{0}\ket{0}=\sum_{q^{\prime}\in[w]}\alpha_{0,q^{\prime}}\ket{q^{\prime}}$.
The unitary nature of $\hat{U}_{p}$ results from the fact that the transition
function $\delta$ is quantumly well-behaved.

  * •

Secondly, define a family of $\log w+\log n$-qubit labelling unitaries
$\\{\hat{LU}_{p}\\}_{p\in\\{1,\cdots,l\\}}$ where the unitaries are defined as
$\hat{LU}_{p}\ket{q}\ket{0^{\otimes\log n}}=\ket{q}\ket{L(v_{p,q})}$ where $L$
is the labelling function of the r-GQBP $R^{\prime}$.

  * •

Finally, define a family of $\log w+\log n+1$-qubit phase inclusion unitaries
$\\{\hat{PU}_{p}\\}_{p\in\\{1,2,\cdots,l\\}}$ that act as
$\hat{PU}_{p}\ket{q}\ket{k}\ket{a}=e^{ia\theta_{p,q}}\ket{q}\ket{k}\ket{a}$.

Now, let $\mathcal{E}_{p}$ be the encoding defined in the proof of Theorem 4.8
that encodes a state of a circuit to a state of an r-GQBP as
$\mathcal{E}_{p}\big{(}\sum_{q\in[w]}\alpha_{q}\ket{q}\big{)}=\sum_{q\in[w]}\alpha_{q}\ket{v_{p,q}}$
for any $(\alpha_{0},\alpha_{1},\cdots,\alpha_{s-1})\in\mathbb{C}^{w}$ for any
$p$. Define a set $F_{C}$ of accept states as
$F_{C}=\\{\ket{q}:\mathcal{E}_{t}(\ket{q})\in F\\}$. With these families of
unitaries and the set of accept states $F_{C}$, we can simulate r-GQBP
$R^{\prime}$ using circuit $C$ as in Algorithm 1. We now show the correctness
of the simulation algorithm.

Algorithm 1 Simulating r-GQBP $R^{\prime}$ in circuit $C$

1:Oracle $O_{x}$, unitaries $\\{\hat{U}_{p}\\}_{p},\\{\hat{LU}_{p}\\}_{p}$ and
$\\{\hat{PU}_{p}\\}_{p}$, and the set of accept states $F_{C}$.

2:Registers $R_{1}$, $R_{2}$ and $R_{3}$ of size $\log w,\log n$ and $1$ all
set to $\ket{0}$.

3:Apply $\hat{U}_{0}$ on $R_{1}$.

4:for $p$ from $1$ to $l$ do

5: Apply $\hat{LU}_{p}$ on $R_{1}$ and $R_{2}$.

6: Apply $O_{x}$ on $R_{2}$ and $R_{3}$.

7: Apply $\hat{PU}_{p}$ on $R_{1},R_{2}$ and $R_{3}$.

8: Apply $O_{x}$ on $R_{2}$ and $R_{3}$.

9: Apply $\hat{LU}_{p}^{\dagger}$ on $R_{1}$ and $R_{2}$.

10: Apply $\hat{U}_{p}$ on $R_{1}$.

11:end for

12:Measure $R_{1}$ in the computational basis. If the outcome belongs in
$F_{C}$, then accept. Else, reject.

Let $C$ be a circuit with $\log w+\log n+1$ qubits. Let $\ket{\phi_{p}}$ be
the state of the circuit before the $p+1^{th}$ iteration in Algorithm 1.
Before the first iteration, we have

$\ket{\phi_{0}}=\hat{U}_{0}\ket{0}\ket{0}\ket{0}=\sum_{q\in[w]}\alpha_{0,q}\ket{q}\ket{0}\ket{0}$

Clearly, $\mathcal{E}_{0}(\ket{\phi_{0}})=\ket{v_{0}}$. Now, consider the
$p+1^{th}$ iteration. Let the state of the circuit $C$ before the $p+1^{th}$
iteration be $\ket{\phi_{p}}=\sum_{q\in[w]}\alpha_{p,q}\ket{q}\ket{0}\ket{0}$.
Then, the evolution of the circuit during the $p+1^{th}$ iteration can be
given as follows:

$\displaystyle\ket{\phi_{p}}$
$\displaystyle\xrightarrow{\hat{LU}_{p}}\sum_{q\in[w]}\alpha_{p,q}\ket{q}\ket{L(v_{p,q})}\ket{0}\xrightarrow{O_{x}}\sum_{q\in[w]}\alpha_{p,q}\ket{q}\ket{L(v_{p,q})}\ket{\gamma_{p,q}}$
$\displaystyle\xrightarrow{\hat{PU}_{p}}\sum_{q\in[w]}e^{i\gamma_{p,q}\theta_{p,q}}\alpha_{p,q}\ket{q}\ket{L(v_{p,q})}\ket{\gamma_{p,q}}\xrightarrow{O_{x}}\sum_{q\in[w]}e^{i\gamma_{p,q}\theta_{p,q}}\alpha_{p,q}\ket{q}\ket{L(v_{p,q})}\ket{0}$
$\displaystyle\xrightarrow{\hat{LU}_{p}^{\dagger}}\sum_{q\in[w]}e^{i\gamma_{p,q}\theta_{p,q}}\alpha_{p,q}\ket{q}\ket{0}\ket{0}$
$\displaystyle\xrightarrow{\hat{U}_{p}}\sum_{q\in[w]}e^{i\gamma_{p,q}\theta_{p,q}}\alpha_{p,q}\hat{U}_{p}\ket{q}\ket{0}\ket{0}$
$\displaystyle=\sum_{q\in[w]}e^{i\gamma_{p,q}\theta_{p,q}}\alpha_{p,q}\sum_{q^{\prime}\in[w]}\delta(v_{p,q},0,v_{p+1,q^{\prime}})\ket{q^{\prime}}\ket{0}\ket{0}$
$\displaystyle=\sum_{q^{\prime}\in[w]}\Bigg{[}\sum_{q\in[w]}e^{i\gamma_{p,q}\theta_{p,q}}\alpha_{p,q}\delta(v_{p,q},0,v_{p+1,q^{\prime}})\Bigg{]}\ket{q^{\prime}}\ket{0}\ket{0}$

But since $R$ is an r-GQBP, we know that
$\delta(v_{p,q},1,v_{p+1,q^{\prime}})=e^{i\theta_{p,q}}\delta(v_{p,q},1,v_{p+1,q^{\prime}})$
from the definition of r-GQBP. This gives that
$e^{i\gamma_{p,q}\theta_{p,q}}\delta(v_{p,q},0,v_{p+1,q^{\prime}})=\delta(v_{p,q},\gamma_{p,q},v_{p+1,q^{\prime}})$.
So, we have,

$\displaystyle\ket{\phi_{p+1}}$
$\displaystyle=\sum_{q^{\prime}\in[w]}\Bigg{[}\sum_{q\in[w]}e^{i\gamma_{p,q}\theta_{p,q}}\alpha_{p,q}\delta(v_{p,q},0,v_{p+1,q^{\prime}})\Bigg{]}\ket{q^{\prime}}\ket{0}\ket{0}$
$\displaystyle=\sum_{q^{\prime}\in[w]}\Bigg{[}\sum_{q\in[w]}\alpha_{p,q}\delta(v_{p,q},\gamma_{p,q},v_{p+1,q^{\prime}})\Bigg{]}\ket{q^{\prime}}\ket{0}\ket{0}$
(1)

Now, consider the $p+1^{th}$ transition in r-GQBP $R^{\prime}$. Let
$\ket{\psi_{p}}=\sum_{q\in[w]}\alpha_{p,q}\ket{v_{p,q}}$ be the state of $R$
just before the $p+1^{th}$ transition. Then, the state of $R$ after the
$p+1^{th}$ transition can be given as

$\displaystyle U^{O_{x}}_{p+1}\ket{\psi_{p}}$
$\displaystyle=U^{O_{x}}_{p+1}\sum_{q\in[w]}\alpha_{p,q}\ket{v_{p,q}}=\sum_{q\in[w]}\alpha_{p,q}\leavevmode\nobreak\
U^{O_{x}}_{p+1}\ket{v_{p,q}}$
$\displaystyle=\sum_{q\in[w]}\alpha_{p,q}\sum_{q^{\prime}\in[w]}\delta(v_{p,q},\gamma_{p,q},v_{p+1,q^{\prime}})\ket{v_{p+1,q}}$
$\displaystyle=\sum_{q^{\prime}\in[w]}\Bigg{[}\sum_{q\in[w]}\alpha_{p,q}\leavevmode\nobreak\
\delta(v_{p,q},\gamma_{p,q},v_{p+1,q^{\prime}})\Bigg{]}\ket{v_{p+1,q}}=\ket{\psi_{p+1}}$
(2)

where $\gamma_{p,q}=X_{L(v_{p,q})}$ is the value obtained on querying the
index corresponding to the node $v_{p,q}$. If we call the state of the first
register of Equation 1 as $\ket{\phi^{\prime}_{p+1}}$, then comparing it with
Equation 2, we can see that

$\mathcal{E}_{p+1}\big{(}\ket{\phi^{\prime}_{p+1}}\big{)}=\ket{\psi_{p+1}}.$

This is true for any $p\in\\{0,1,\cdots,l-1\\}$. So, we have
$\mathcal{E}_{l}\big{(}\ket{\phi^{\prime}_{l}}\big{)}=\ket{\psi_{l}}$.
Finally, on measuring $\ket{\phi^{\prime}_{l}}$, the circuit accepts the input
if and only if the measurement outcome, say $\ket{m}\in F_{C}$. This implies
that the circuit accepts the input if and only if
$\mathcal{E}_{l}(\ket{m})=\ket{v_{l,m}}\in F$. Hence, the circuit $C$ accepts
an input if and only if the r-GQBP $R$ accepts the input. Moreover, since the
amplitude of $\ket{m}$ in the circuit $C$ is the same as the amplitude of
$\mathcal{E}_{l}(\ket{m})=\ket{v_{l,m}}$, $C$ accepts with the same
probability as that of $R$, and this simulates $R$ exactly.

##  5 Query-Space Lower Bound for Unordered Search

The unordered search problem was one of the earliest problems for which a
query lower bound was proved and one of the first problems to admit a quantum
speedup. We follow suit and present a query-space lower bound for the
unordered search in the r-GQBP mode by showing a lower bound on a related
problem, which we call the Promise-OR problem. We define the Promise-OR
problem below.

######  Problem 5.1 (Promise-OR Problem).

Given access to an $n$-bit Boolean string $X$ with a promise that at most one
of the $n$ positions has a $1$, decide if $X$ has a $1$.

Figure 3: The state transitions using the hybrid argument.

See 2.1

######  Proof 5.2.

To prove this theorem, we follow the lines of the well-known hybrid argument
technique for lower bounds. Let $R$ be an ($s,L$)-r-GQBP that solves the
Promise-OR problem, and let $R^{\prime}$ be the equivalent ($s,2L$)-r-GQBP
obtained using Corollary 4.4. We will analyse two evolutions of $R^{\prime}$.
The first is on the input $0^{n}$. The second will be a hybrid evolution,
where some initial transitions will be using $0^{n}$ as the input string, and
the rest of the transitions will be using $0^{p-1}10^{n-p}$, denoted $1_{p}$,
as the input string. The intuition would be to show that the corresponding
states after each transition in these two evolutions have a bounded
difference, and unless there are lots of transitions, the final states would
not be sufficiently distinguishable for input strings $0^{n}$ and $1_{p}$. We
require a few notations to handle the technicalities.

Let $U_{t}$ denote the unitary corresponding to the $t^{th}$ query-independent
transition and $V_{t}^{X}$ denote the unitary corresponding to the $t^{th}$
query-dependent transition of $R^{\prime}$ when then input is $X$. Let
$\ket{\psi_{t}}_{1/2}$ and $\ket{\psi_{t}}$ be the states of the branching
program after the $t^{th}$ query-independent and $t^{th}$ query-independent
transitions, respectively, when querying the input $0^{n}$. Similarly, let
$\ket{\psi_{t,p}^{(k)}}_{1/2}$ and $\ket{\psi_{t,p}^{(k)}}$ be the states of
the branching program after the $t^{th}$ query-dependent and $t^{th}$ query-
independent transitions, respectively, when the first $t-k$ queries are made
to $0^{n}$ and the last $k$ queries are made to $0^{p-1}10^{n-p}$, denoted
$1_{p}$; these denote the states in a hybrid run of $R^{\prime}$. Note that
unitary $U_{t}$ corresponding to the $t^{th}$ query-independent transition is
such that $\ket{\psi_{t}}=U_{t}\ket{\psi_{t}}_{1/2}$ and
$\ket{\psi_{t,p}^{(k)}}=U_{t}\ket{\psi_{t,p}^{(k)}}_{1/2}$.

The objective is to bound the difference between the states $\ket{\psi_{L}}$
(final state of the non-hybrid evolution, on input $0^{n}$) and
$\ket{\psi_{L,p}^{(L)}}$ (final state of the hybrid evolution, but all queries
are to input $1_{p}$).

Suppose we represent $\ket{\psi_{t}}_{1/2}$ as
$\displaystyle\ket{\psi_{t}}_{1/2}=\sum_{j\in[s]}\alpha_{j,t}\ket{j}$. Let
$Q_{p,t}$ be the set of nodes that query the index $p$ after the $t^{th}$
query-dependent transition. Then we can write

$\ket{\psi_{t,p}^{(1)}}_{1/2}=\sum_{j\in[s]:j\notin
Q_{p,t}}\alpha_{j,t}\ket{j}+\sum_{j\in
Q_{p,t}}e^{i\theta_{j,t}}\alpha_{j,t}\ket{j}.$

This allows us to compare two evolutions in which only the $t$-th query was
made to different strings, $0^{n}$ and $1_{p}$, and all the earlier ones being
made to $0^{n}$ for both.

$\displaystyle\norm{\ket{\psi_{t}}-\ket{\psi_{t,p}^{(1)}}}$
$\displaystyle=\norm{U_{t}\ket{\psi_{t}}_{1/2}-U_{t}\ket{\psi_{t,p}^{(1)}}_{1/2}}=\norm{\ket{\psi_{t}}_{1/2}-\ket{\psi_{t,p}^{(1)}}_{1/2}}$
$\displaystyle=\norm{\Bigg{[}\sum_{j\in[s]}\alpha_{j,t}\ket{j}\Bigg{]}-\Bigg{[}\sum_{j\in[s]:j\notin
Q_{p,t}}\alpha_{j,t}\ket{j}+\sum_{j\in
Q_{p,t}}e^{i\theta_{j,t}}\alpha_{j,t}\ket{j}\Bigg{]}}$
$\displaystyle=\norm{\sum_{j\in
Q_{p,t}}(1-e^{i\theta_{j,t}})\alpha_{j,t}\ket{j}}\leq 2\norm{\sum_{j\in
Q_{p,t}}\alpha_{j,t}\ket{j}}.$

Now we compare the final states of the evolutions in which only the final two
queries differ.

$\displaystyle\ket{\psi_{L}}-\ket{\psi_{L,p}^{(2)}}$
$\displaystyle=\ket{\psi_{L}}-U_{L}V_{L}^{1_{p}}\ket{\psi_{L-1}}+U_{L}V_{L}^{1_{p}}\ket{\psi_{L-1}}-\ket{\psi_{L,p}^{(2)}}$
$\displaystyle=\ket{\psi_{L}}-U_{L}V_{L}^{1_{p}}\ket{\psi_{L-1}}+U_{L}V_{L}^{1_{p}}\ket{\psi_{L-1}}-U_{L}V_{L}^{1_{p}}\ket{\psi_{L-1,p}^{(1)}}$
$\displaystyle=\Big{[}\ket{\psi_{L}}-\ket{\psi_{L,p}^{(1)}}\Big{]}+U_{L}V_{L}^{(1_{p})}\Big{[}\ket{\psi_{L-1}}-\ket{\psi_{L-1,p}}\Big{]}.$

We can extend the above using induction and telescoping to show that

$\displaystyle\ket{\psi_{L}}-\ket{\psi_{L,p}^{(L)}}$
$\displaystyle=\sum_{t=L}^{0}\leavevmode\nobreak\
\Bigg{(}\prod_{l=t+1}^{L}U_{l}V_{l}^{(1_{p})}\Bigg{)}\leavevmode\nobreak\
\Big{[}\ket{\psi_{t}}-\ket{\psi_{t,p}}\Big{]}.$

We can bound their distance as well.

$\displaystyle\norm{\ket{\psi_{L}}-\ket{\psi_{L,p}^{(L)}}}$
$\displaystyle=\norm{\sum_{t=L}^{0}\leavevmode\nobreak\
\Bigg{(}\prod_{l=t+1}^{L}U_{l}V_{l}^{(1_{p})}\Bigg{)}\leavevmode\nobreak\
\Big{[}\ket{\psi_{t}}-\ket{\psi_{t,p}}\Big{]}}$
$\displaystyle\leq\sum_{t=L}^{0}\norm{\Bigg{(}\prod_{l=t+1}^{L}U_{l}V_{l}^{(1_{p})}\Bigg{)}\leavevmode\nobreak\
\Big{[}\ket{\psi_{t}}-\ket{\psi_{t,p}}\Big{]}}$
$\displaystyle=\sum_{t=L}^{0}\norm{\prod_{l=t+1}^{L}U_{l}V_{l}^{(1_{p})}}\leavevmode\nobreak\
\norm{\Big{[}\ket{\psi_{t}}-\ket{\psi_{t,p}}\Big{]}}$
$\displaystyle=\sum_{t=0}^{L}\norm{\Big{[}\ket{\psi_{t}}-\ket{\psi_{t,p}}\Big{]}}\leq\sum_{t=0}^{L}2\norm{\sum_{j\in
Q_{p,t}}\alpha_{j,t}\ket{j}}\leq 2\sum_{t=0}^{L}\sum_{j\in
Q_{p,t}}\absolutevalue{\alpha_{j,t}}$

Then, taking an expectation over a uniform distribution on $p$, we get

$\displaystyle\mathop{\mathbb{E}}_{p}\bigg{[}\norm{\ket{\psi_{L}}-\ket{\psi_{L,p}^{(L)}}}\bigg{]}$
$\displaystyle\leq\mathop{\mathbb{E}}_{p}\bigg{[}2\sum_{t=0}^{L}\sum_{j\in
Q_{p,t}}\absolutevalue{\alpha_{j,t}}\bigg{]}=\frac{2}{n}\sum_{p=1}^{n}\sum_{t=0}^{L}\sum_{j\in
Q_{p,t}}\absolutevalue{\alpha_{j,t}}=\frac{2}{n}\sum_{t=0}^{L}\sum_{p=1}^{n}\sum_{j\in
Q_{p,t}}\absolutevalue{\alpha_{j,t}}.$

Since one node queries exactly one index, each node will belong to $Q_{p,t}$
for some $p$ in each $t$. So, we have $\sum_{p=1}^{n}\sum_{j\in
Q_{p,t}}\norm{\alpha_{j,t}}=\sum_{j\in[s]}\absolutevalue{\alpha_{j,t}}$. This
gives,

$\displaystyle\mathop{\mathbb{E}}_{p}\bigg{[}\norm{\ket{\psi_{L}}-\ket{\psi_{L,p}^{(L)}}}\bigg{]}$
$\displaystyle=\frac{2}{n}\sum_{t=0}^{L}\sum_{j\in[s]}\absolutevalue{\alpha_{j,t}}.$

To maximize the value of $\sum_{j\in[s]}\absolutevalue{\alpha_{j,t}}$ for any
fixed $t$ conditioned on the fact that
$\sum_{j\in[s]}\absolutevalue{\alpha_{j,t}}^{2}=1$, we set
$\absolutevalue{\alpha_{j,t}}=\frac{1}{\sqrt{s}}$ for all $j$. So, we get

$\displaystyle\mathop{\mathbb{E}}_{p}\bigg{[}\norm{\ket{\psi_{L}}-\ket{\psi_{L,p}^{(L)}}}\bigg{]}$
$\displaystyle=\frac{2}{n}\sum_{t=0}^{L}\sum_{j\in[s]}\absolutevalue{\alpha_{j,t}}\leq\frac{2}{n}\sum_{t=0}^{L}\sum_{j\in[s]}\frac{1}{\sqrt{s}}=\frac{2(L+1)\sqrt{s}}{n}.$
(3)

But to be able to successfully distinguish between the inputs $X=0^{n}$ and
$X=1^{p}$ for any $p$, we need that
$\norm{\ket{\psi_{L}}-\ket{\psi_{L,p}^{(L)}}}=\Omega(1)$. Again, taking an
expectation over the uniform distribution of $p$, we get

$\displaystyle\mathop{\mathbb{E}}_{p}\bigg{[}\norm{\ket{\psi_{L}}-\ket{\psi_{L,p}^{(L)}}}\bigg{]}$
$\displaystyle=\Omega(1).$ (4)

Comparing (3) and (4), we get $\tfrac{2(L+1)\sqrt{s}}{n}=\Omega(1)$, or
$L=\Omega\bigg{(}\frac{n}{\sqrt{s}}\bigg{)}$.

##  6 Query-Space Lower Bound for ($k,k+\delta$) Hamming Decision Problem

Following the lower bound obtained for the Promise-OR problem, we extend a
similar query-space lower bound for the ($k,k+1$) Hamming decision problem. We
first formally define the ($k,k+\delta$) Hamming decision problem.

######  Problem 6.1 (($k,k+\delta$) Hamming Decision Problem).

Given access to an $n$-bit Boolean input $X$ with the promise that the Hamming
weight of $X$ is either $k$ or $k+\delta$ for some $\delta<k$, decide if the
Hamming weight of $X$ is $k$ or $k+\delta$.

The ($k,k+\delta$) Hamming decision problem is an interesting problem to
consider. For any symmetric function, there exists some fixed $k$ such that
($k,k+1$) Hamming decision problem can be reduced to that particular symmetric
function. For instance, when $k=n/2$, then ($k,k+1$) Hamming decision problem
can be reduced to problems like Parity and Majority and for any fixed $k$,
($k,k+1$) Hamming decision problem can be reduced to the threshold-$k$
function. So, a lower bound on the ($k,k+\delta$) Hamming decision problem
essentially provides a lower bound for all the symmetric functions.

See 2.2

The proof of Theorem 2.2 follows a pattern similar to the proof of Theorem
2.1. The main difference here is that in the proof of the earlier, query-
dependent transitions did not affect the state of the branching program when
the input is $X=0^{n}$. However, here, the query-dependent layer could
potentially change the state of the branching program irrespective of the
input. The structure of the proof is still the same as that of the earlier. We
first use hybrid arguments to bound the norm of the difference of the states
obtained when input to the r-GQBP is a yes instance and a no instance. Then,
fixing a yes instance, we take the expectation value of this norm over a
uniform distribution on a set of hard no instances. Finally, we note that the
expectation value has to be $\Omega(1)$ in order to differentiate between the
yes instance and the no instance with a constant probability. While the last
step is easy, the first two steps are slightly complicated. We present the
proof of Theorem 2.2 below.

######  Proof 6.2 (Proof of Theorem 2.2).

Let $x$ correspond to an input such that $|x|=k$ and $y$ correspond to an
input such that $|y|=k+1$. Let $R$ be a ($s,L$)-r-GQBP that solves the
($k,k+\delta$) Hamming decision problem and let $R^{\prime}$ be its dual
($s,2L$)-r-GQBP obtained from Corollary 4.4. We introduce a few notations
required for the proof similar to that in the proof of Theorem 2.1. Let
$\ket{\psi_{t,w}}_{1/2}$ and $\ket{\psi_{t,w}}$ be the state of the branching
program after the $t^{th}$ query-dependent and $t^{th}$ query-independent
transitions, respectively, when the input is $w\in\\{x,y\\}$. Let
$\ket{\psi_{t,y}^{(r)}}_{1/2}$ and $\ket{\psi_{t,y}^{(r)}}$ denote the states
of the branching program after the $t^{th}$ query-dependent and $t^{th}$
query-independent transitions, respectively, where the first $t-k$ query-
dependent transitions were made to the input $x$ and the last $k$ query-
dependent transitions were made to the input $y$. Notice that
$\ket{\psi_{t,y}^{(t)}}_{1/2}=\ket{\psi_{t,y}}_{1/2}$ and
$\ket{\psi_{t,y}^{(t)}}=\ket{\psi_{t,y}}$, i.e, in the hybrid run, when the
last $t$ query-dependent transitions out of a total $t$ transitions are made
to the input $y$, then it is the same as evaluating the r-GQBP $R^{\prime}$ on
the input $y$.

Our ultimate objective here is to upper bound the difference between the
states $\ket{\psi_{t,L}}$ and $\ket{\psi_{t,L}}$. Now, let the state just
before the $t^{th}$ query dependent level when the input is $x$ be denoted as

$\ket{\psi_{t-1,x}}=\sum_{j\in[s]}\alpha_{j,t}\ket{j}.$

The state obtained when the next query is made to $y$ is

$\ket{\psi_{t,y}^{(1)}}_{1/2}=\sum_{j\in[s]:j\notin
Q_{y,t}}\alpha_{j,t}\ket{j}+\sum_{j\in[s]:j\in
Q_{y,t}}e^{i\theta_{j,t}}\alpha_{j,t}\ket{j},$

where $Q_{y,t}$ is the set of nodes at the $t^{th}$ query-dependent level that
queries an index $p$ such that $y_{p}=1$. Similarly, the state of the
branching program, when the $t^{th}$ query was made to $x$, will be

$\ket{\psi_{t,x}}_{1/2}=\sum_{j\in[s]:j\notin
Q_{x,t}}\alpha_{j,t}\ket{j}+\sum_{j\in[s]:j\in
Q_{x,t}}e^{i\theta_{j,t}}\alpha_{j,t}\ket{j},$

Using these two expressions, we can bound the difference between these states
as

$\displaystyle\norm{\ket{\psi_{t,x}}-\ket{\psi_{t,y}^{(1)}}}$
$\displaystyle=\norm{U_{t}\ket{\psi_{t,x}}_{1/2}-U_{t}\ket{\psi_{t,y}^{(1)}}_{1/2}}=\norm{U_{t}}\norm{\ket{\psi_{t,x}}_{1/2}-\ket{\psi_{t,y}^{(1)}}_{1/2}}$
$\displaystyle=\norm{\ket{\psi_{t,x}}_{1/2}-\ket{\psi_{t,y}^{(1)}}_{1/2}}$
$\displaystyle=\Bigg{\lvert}\Bigg{\lvert}\Bigg{[}\sum_{j\in[s]:j\notin
Q_{x,t}}\alpha_{j,t}\ket{j}+\sum_{j\in[s]:j\in
Q_{x,t}}e^{i\theta_{j,t}}\alpha_{j,t}\ket{j}\Bigg{]}$ $\displaystyle\hskip
50.00008pt-\Bigg{[}\sum_{j\in[s]:j\notin
Q_{y,t}}\alpha_{j,t}\ket{j}+\sum_{j\in[s]:j\in
Q_{y,t}}e^{i\theta_{j,t}}\alpha_{j,t}\ket{j}\Bigg{]}\Bigg{\rvert}\Bigg{\rvert}$
$\displaystyle=\norm{\sum_{j\in Q_{x,t}\leavevmode\nobreak\
\&\leavevmode\nobreak\ j\notin
Q_{y,t}}(e^{i\theta_{j,t}}-1)\alpha_{j,t}\ket{j}+\sum_{j\notin
Q_{x,t}\leavevmode\nobreak\ \&\leavevmode\nobreak\ j\in
Q_{y,t}}(1-e^{i\theta_{j,t}})\alpha_{j,t}\ket{j}}$
$\displaystyle\leq\sum_{j\in\Delta(x,y,t)}\norm{(1-e^{i\theta_{j,t}})\alpha_{j,t}\ket{j}}$
$\displaystyle\leq
2\sum_{j\in\Delta(x,y,t)}\norm{\alpha_{j,t}\ket{j}}=2\sum_{j\in\Delta(x,y,t)}\absolutevalue{\alpha_{j,t}},$

where $\Delta(x,y,t)$ is the set of all nodes that query an index $p$ such
that $x_{p}\neq y_{p}$ in the $t^{th}$ query-dependent level.

Similar to the proof of Theorem 2.1, it is easy to show that

$\norm{\ket{\psi_{L,x}}-\ket{\psi_{L,y}}}=\norm{\ket{\psi_{L,x}}-\ket{\psi_{L,y}^{(L)}}}\leq
2\sum_{t=0}^{L}\sum_{j\in\Delta(x,y,t)}\absolutevalue{\alpha_{j,t}}.$

We consider two cases — $k\leq n/2$ and $k>n/2$.

Case 1: $k\leq n/2$. Now, fix the input $x$ such that $k=|x|\leq n/2$. Let
$\mathscr{R}$ be a set of inputs $y$ such that $x_{i}=y_{i}$ whenever
$x_{i}=1$ and out of the remaining $n-k$ bit positions where $x_{i}=0$, $y$
differs from $x$ at exactly $\delta$ positions. Then, the number of elements
in $\mathscr{R}$ will be exactly $\binom{n-k}{\delta}$. Taking an expectation
over a uniform distribution of $y$ in $\mathscr{R}$, we get

$\displaystyle\mathop{\mathbb{E}}_{\mathscr{R}}\Big{[}\norm{\ket{\psi_{L,x}}-\ket{\psi_{L,y}}}\Big{]}$
$\displaystyle\leq\mathop{\mathbb{E}}_{\mathscr{R}}\Big{[}2\sum_{t=0}^{L}\sum_{j\in\Delta(x,y,t)}\absolutevalue{\alpha_{j,t}}\Big{]}$
$\displaystyle=\frac{2}{\binom{n-k}{\delta}}\sum_{y\in\mathscr{R}}\sum_{t=0}^{L}\sum_{j\in\Delta(x,y,t)}\absolutevalue{\alpha_{j,t}}=\frac{2}{\binom{n-k}{\delta}}\sum_{t=0}^{L}\sum_{y\in\mathscr{R}}\sum_{j\in\Delta(x,y,t)}\absolutevalue{\alpha_{j,t}}$

Notice the last two summations of the last equation. Take any index $i\in[n]$.
Then, the number of $y\in\mathscr{R}$, such that $x_{i}\neq y_{i}$ is either
$0$ (for $i$ such that $x_{i}=1$) or exactly $\binom{n-k-1}{\delta-1}$. So,
for any $j\in[s]$, the number of $y\in\mathscr{R}$ such that
$j\in\Delta(x,y,t)$ is either $0$ or $\binom{n-k-1}{\delta-1}$. This is
because of the fact that $x$ and $y$ differ exactly at $\delta$ positions, and
these are positions where $x_{i}=0$. So, we get

$\sum_{y\in\mathscr{R}}\sum_{j\in\Delta(x,y,t)}\absolutevalue{\alpha_{j,t}}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \binom{n-k-1}{\delta-1}\sum_{{j\in[s]:\atop
j\in\Delta(x,y,t)}\atop\text{\leavevmode\nobreak\ for some
}y\in\mathscr{R}}\absolutevalue{\alpha_{j,t}}\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\binom{n-k-1}{\delta-1}\sum_{j\in[s]}\absolutevalue{\alpha_{j,t}}$

Using this in the expression of expectation, we get

$\displaystyle\mathop{\mathbb{E}}_{\mathscr{R}}\Big{[}\norm{\ket{\psi_{L,x}}-\ket{\psi_{L,y}}}\Big{]}$
$\displaystyle=\frac{2}{\binom{n-k}{\delta}}\sum_{t=0}^{L}\sum_{y\in\mathscr{R}}\sum_{j\in\Delta(x,y,t)}\absolutevalue{\alpha_{j,t}}$
$\displaystyle\leq\frac{2\binom{n-k-1}{\delta-1}}{\binom{n-k}{\delta}}\sum_{t=0}^{L}\sum_{j\in[s]}\absolutevalue{\alpha_{j,t}}\leavevmode\nobreak\
\leavevmode\nobreak\
\leq\frac{2\delta}{n-k}\sum_{t=0}^{L}\sum_{j\in[s]}\absolutevalue{\alpha_{j,t}}$

Since, $\sum_{j\in[s]}\absolutevalue{\alpha_{j,t}}^{2}=1$, setting
$\absolutevalue{\alpha_{j,t}}=\frac{1}{\sqrt{s}}$ maximizes
$\sum_{j\in[s]}\absolutevalue{\alpha_{j,t}}$. So, we get,

$\mathop{\mathbb{E}}_{\mathscr{R}}\Big{[}\norm{\ket{\psi_{L,x}}-\ket{\psi_{L,y}}}\Big{]}\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\frac{2\delta}{n-k}\sum_{t=0}^{L}\sum_{j\in[s]}\absolutevalue{\alpha_{j,t}}\leq\frac{2\delta}{n-k}\sum_{t=0}^{L}\sqrt{s}=\frac{2(L+1)\delta\sqrt{s}}{n-k}.$
(5)

For any two inputs $x,y$ such that $f(x)\neq f(y)$, we need
$\norm{\ket{\psi_{L,x}}-\ket{\psi_{L,y}}}=\Omega(1)$ to be able to distinguish
them with some constant probability. With a fixed $x$, taking an expectation
over all inputs $y$ in $\mathscr{R}$, we have
$\mathop{\mathbb{E}}_{\mathscr{R}}\Big{[}\norm{\ket{\psi_{L,x}}-\ket{\psi_{L,y}}}\Big{]}=\Omega(1)$.
Comparing this with the expression in Equation 5, we get

$\frac{2(L+1)\delta\sqrt{s}}{n-k}=\Omega(1)\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \text{or, }\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
L=\Omega\Big{(}\frac{n-k}{\delta\sqrt{s}}\Big{)}$

As $k\leq n/2$, we have $n-k=\Omega(n)$ which gives
$L=\Omega\Big{(}\frac{n}{\delta\sqrt{s}}\Big{)}$.

Case 2: $k>n/2$. Fix an input $y$ such that $|y|=k+\delta$. Let $\mathscr{R}$
be the set of inputs $x$ such that $x_{i}=0$ whenever $y_{i}=0$ and $x$
differs from $y$ at exactly $\delta$ position out of the remaining $k+\delta$
positions. It is easy to see that the number of elements in $\mathscr{R}$ is
$\binom{k+\delta}{k}$. Similar to Case 1, by taking an expectation over a
uniform superposition of $x$ in $\mathscr{R}$ and using similar arguments, we
can show that

$\displaystyle\mathop{\mathbb{E}}_{\mathscr{R}}\Big{[}\norm{\ket{\psi_{L,x}}-\ket{\psi_{L,y}}}\Big{]}$
$\displaystyle\leq\frac{2}{\binom{k+\delta}{k}}\sum_{t=0}^{L}\sum_{x\in\mathscr{R}}\sum_{j\in\Delta(x,y,t)}\absolutevalue{\alpha_{j,t}}$

Now, for any index $i\in[n]$, the number of inputs $x\in\mathscr{R}$ such that
$x_{i}\neq y_{i}$ is either $0$ or exactly $\binom{k+\delta-1}{k}$. So, for
any $j\in[s]$, the number of inputs $x\in\mathscr{R}$ such that
$j\in\Delta(x,y,t)$ is either $0$ or $\binom{k+\delta-1}{k}$. This gives us

$\sum_{x\in\mathscr{R}}\sum_{j\in\Delta(x,y,t)}\absolutevalue{\alpha_{j,t}}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \binom{k+\delta-1}{k}\sum_{{j\in[s]:\atop
j\in\Delta(x,y,t)}\atop\text{\leavevmode\nobreak\ for some
}x\in\mathscr{R}}\absolutevalue{\alpha_{j,t}}\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\binom{k+\delta-1}{k}\sum_{j\in[s]}\absolutevalue{\alpha_{j,t}}.$

Using this, we refine the bound on the expectation as

$\displaystyle\mathop{\mathbb{E}}_{\mathscr{R}}\Big{[}\norm{\ket{\psi_{L,x}}-\ket{\psi_{L,y}}}\Big{]}$
$\displaystyle\leq\frac{2\binom{k+\delta-1}{k}}{\binom{k+\delta}{k}}\sum_{t=0}^{L}\sum_{j\in[s]}\absolutevalue{\alpha_{j,t}}\leq\frac{2\delta}{k+\delta}\sum_{t=0}^{L}\sum_{j\in[s]}\absolutevalue{\alpha_{j,t}}$
$\displaystyle\leq\frac{2(L+1)\delta\sqrt{s}}{k}$ (6)

For any two inputs $x,y$ such that $f(x)\neq f(y)$, we need
$\norm{\ket{\psi_{L,x}}-\ket{\psi_{L,y}}}=\Omega(1)$ to be able to distinguish
them with some constant probability. With a fixed $y$, taking an expectation
over all inputs $x$ in $\mathscr{R}$, we have
$\mathop{\mathbb{E}}_{\mathscr{R}}\Big{[}\norm{\ket{\psi_{L,x}}-\ket{\psi_{L,y}}}\Big{]}=\Omega(1)$.
Comparing this with the expression in Equation 6, we get,

$\frac{2(L+1)\delta\sqrt{s}}{k}=\Omega(1)\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \text{or, }\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
L=\Omega\Big{(}\frac{k}{\delta\sqrt{s}}\Big{)}.$

Since, $k>n/2$, we get $L=\Omega\Big{(}\frac{n}{\delta\sqrt{s}}\Big{)}$.

Setting $\delta=O(1)$ gives rise to the following corollary.

######  Corollary 6.3.

Any r-GQBP of length $L$ and width $s$ that solves the ($k,k+1$) Hamming
Decision problem has to satisfy $L=\Omega\Big{(}\frac{n}{\sqrt{s}}\Big{)}$.

From this result, we can obtain a query-space lower bound for the class of all
total symmetric functions.

See 2.3

######  Proof 6.4.

Let $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ be a non-constant symmetric
function. Then, there should exist some $k$ such that for all inputs $x$ of
Hamming weight $k$, $f(x)=a$ for some $a\in\\{0,1\\}$ and all inputs $y$ of
Hamming weight $k+1$, $f(y)=\overline{a}$. Now, there is a direct reduction
from the partial function corresponding to the ($k,k+\delta$) Hamming decision
problem to $f$ that is $g(x)=k\iff f(x)=a$ and $g(x)=k+1\iff
f(x)=\overline{a}$. This reduction ensures that any lower bound for solving
the ($k,k+\delta$) Hamming decision problem also serves as a lower bound for
computing $f$. Hence, we obtain the lower bound for computing $f$ from Theorem
2.2.

We can now apply this result to functions such as AND, Parity, and Majority
and obtain the tradeoff of $L^{2}s=\Omega(n)$. This tradeoff is tight for OR
and Parity since Bera et al. constructed GQBP with the same tradeoff in their
work (see Figure 1) [10].

Since we have tight conversion algorithms between GQBP and the quantum-query
circuit, a bound on one model implies a bound on the other. We apply this idea
on Theorem 2.3 to obtain the following lower bound on quantum query circuits.

See 2.4

It is known that computing any non-constant symmetric Boolean function on
$n$-bit inputs requires $\Omega(\sqrt{n})$ queries to the input [6]; our
result provides an alternative proof of a weaker form of this result where
there is a restriction on the space.

##  7 Conclusions

In this work, we introduced a restricted version of the recently introduced
GQBP model, called r-GQBP. Along with a few properties of r-GQBPs, we showed
that any $q$-qubit $t$-query quantum query circuit can be reduced to a
$2^{q}$-width $t$-length r-GQBP. This reduction serves as a motivation to
investigate the query-space lower bounds in the r-GQBP model since any lower
bound on this model translates to a lower bound on the query circuit model
without any overhead. In addition, we also stated a reduction from the r-GQBP
model to the query circuit model, although with some overhead.

We also present a series of lower bounds starting with a query-space lower
bound of $L^{2}s=\Omega(n^{2})$ for the unordered search in the r-GQBP model.
Moreover, we extend this result to the ($k,k+\delta$) Hamming decision problem
and proved a query-space lower bound of $L^{2}s=\Omega(n^{2}/\delta)$. By a
simple reduction from the ($k,k+1$) Hamming decision problem, we show that any
r-GQBP that approximately computes any non-constant symmetric Boolean function
has to satisfy $L^{2}s=\Omega(n^{2})$. While this lower bound is tight for
functions such as $OR_{n}$, $AND_{n}$ and $Parity_{n}$, the tightness is
unclear for functions like $Majority_{n}$ and $Threshold^{k}_{n}$. With advice
from the known results, we conjecture that any r-GQBP that approximately
computes $Majority_{n}$ has to satisfy $L^{2}s=\Omega(n^{4})$ while the bound
for $Threshold^{k}_{n}$ will be $L^{2}s=\Omega(n^{2}k^{2})$.

All the lower-bound results presented in this paper implicitly assume $s\in
o(n^{2})$; otherwise, we get trivial lower bounds. To obtain non-trivial lower
bounds for query circuits, we need to drop this assumption and, instead,
investigate r-GQBPs of larger width.

## References

  * [1] Harold Abelson.  A note on time-space tradeoffs for computing continuous functions.  Information Processing Letters, 8(4):215–217, 1979.
  * [2] Farid Ablayev, Aida Gainutdinova, and Marek Karpinski.  On computational power of quantum branching programs.  In International Symposium on Fundamentals of Computation Theory, pages 59–70. Springer, 2001.
  * [3] Karl Abrahamson.  Time-space tradeoffs for branching programs contrasted with those for straight-line programs.  In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pages 402–409. IEEE, 1986.
  * [4] Miklós Ajtai.  Determinism versus nondeterminism for linear time rams with memory restrictions.  Journal of Computer and System Sciences, 65(1):2–37, 2002.
  * [5] Andris Ambainis, Robert Špalek, and Ronald de Wolf.  A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs.  In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, pages 618–633, 2006.
  * [6] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald De Wolf.  Quantum lower bounds by polynomials.  Journal of the ACM (JACM), 48(4):778–797, 2001.
  * [7] Paul Beame.  A general sequential time-space tradeoff for finding unique elements.  In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pages 197–203, 1989.
  * [8] Paul Beame, Michael Saks, Xiaodong Sun, and Erik Vee.  Time-space trade-off lower bounds for randomized computation of decision problems.  Journal of the ACM (JACM), 50(2):154–195, 2003.
  * [9] Paul Beame, Michael Saks, and Jayram S Thathachar.  Time-space tradeoffs for branching programs.  In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280), pages 254–263. IEEE, 1998.
  * [10] Debajyoti Bera and SAPV Tharrmashastha.  A generalized quantum branching program.  In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023.
  * [11] Allan Borodin and Stephen Cook.  A time-space tradeoff for sorting on a general sequential model of computation.  In Proceedings of the twelfth annual ACM symposium on Theory of computing, pages 294–301, 1980.
  * [12] Allan Borodin, Faith Fich, F Meyer Auf Der Heide, Eli Upfal, and Avi Wigderson.  A time-space tradeoff for element distinctness.  SIAM Journal on Computing, 16(1):97–99, 1987.
  * [13] Allan Borodin, Michael J Fischer, David G Kirkpatrick, Nancy A Lynch, and Martin Tompa.  A time-space tradeoff for sorting on non-oblivious machines.  In 20th Annual Symposium on Foundations of Computer Science (sfcs 1979), pages 319–327. IEEE, 1979.
  * [14] Dmitrii Yur’evich Grigor’ev.  Application of separability and independence notions for proving lower bounds of circuit complexity.  Zapiski Nauchnykh Seminarov POMI, 60:38–48, 1976.
  * [15] Yassine Hamoudi and Frédéric Magniez.  Quantum time-space tradeoff for finding multiple collision pairs.  arXiv preprint arXiv:2002.08944, 2020.
  * [16] Hartmut Klauck, Robert Špalek, and Ronald De Wolf.  Quantum and classical strong direct product theorems and optimal time-space tradeoffs.  SIAM Journal on Computing, 36(5):1472–1493, 2007.
  * [17] Thomas Lengauer and Robert Endre Tarjan.  Upper and lower bounds on time-space tradeoffs.  In Proceedings of the eleventh annual ACM symposium on Theory of computing, pages 262–277, 1979.
  * [18] Dmitri Maslov, Jin-Sung Kim, Sergey Bravyi, Theodore J Yoder, and Sarah Sheldon.  Quantum advantage for computations with limited space.  Nature Physics, 17(8):894–897, 2021.
  * [19] J Ian Munro and Mike S Paterson.  Selection and sorting with limited storage.  Theoretical computer science, 12(3):315–323, 1980.
  * [20] Masaki Nakanishi, Kiyoharu Hamaguchi, and Toshinobu Kashiwabara.  Ordered quantum branching programs are more powerful than ordered probabilistic branching programs under a bounded-width restriction.  In International Computing and Combinatorics Conference, pages 467–476. Springer, 2000.
  * [21] Nicholas Pippenger.  A time-space trade-off.  Journal of the ACM (JACM), 25(3):509–515, 1978.
  * [22] Rudiger Reischuk.  Improved bounds on the problem of time-space trade-off in the pebble game.  Journal of the ACM (JACM), 27(4):839–849, 1980.
  * [23] Martin Sauerhoff and Detlef Sieling.  Quantum branching programs and space-bounded nonuniform quantum complexity.  Theoretical Computer Science, 334(1-3):177–225, 2005.
  * [24] J Savage and Sowmitri Swamy.  Space-time trade-offs on the fft algorithm.  IEEE Transactions on Information Theory, 24(5):563–568, 1978.
  * [25] Martin Tompa.  Time-space tradeoffs for computing functions, using connectivity properties of their circuits.  In Proceedings of the tenth annual ACM symposium on Theory of computing, pages 196–204, 1978.
  * [26] Andrew Chi-Chih Yao.  Near-optimal time-space tradeoff for element distinctness.  In FOCS, pages 91–97, 1988.
  * [27] Yaacov Yesha.  Time-space tradeoffs for matrix multiplication and the discrete fourier transform on any general sequential random-access computer.  Journal of Computer and System Sciences, 29(2):183–197, 1984.