11institutetext: Kazan Federal University, Kazan, Russia, 22institutetext:
Kazan E. K. Zavoisky Physical-Technical Institute, Kazan, Russia
33institutetext: Center for Quantum Computer Science, Faculty of Computing,
University of Latvia, Riga, Latvia
33email<EMAIL_ADDRESS><EMAIL_ADDRESS>
# Quantum algorithm for Dyck Language with Multiple Types of Brackets

Kamil Khadiev 1122 Dmitry Kravchenko 33

###### Abstract

We consider the recognition problem of the Dyck Language generalized for
multiple types of brackets. We provide an algorithm with quantum query
complexity $O(\sqrt{n}(\log n)^{0.5k})$, where $n$ is the length of input and
$k$ is the maximal nesting depth of brackets. Additionally, we show the lower
bound for this problem which is $O(\sqrt{n}c^{k})$ for some constant $c$.

Interestingly, classical algorithms solving the Dyck Language for multiple
types of brackets substantially differ form the algorithm solving the original
Dyck language. At the same time, quantum algorithms for solving both kinds of
the Dyck language are of similar nature and requirements.

Keywords: Dyck language, regular language, strings, quantum algorithms, query
complexity

##  1 Introduction

_Quantum computing_ [17, 3, 2] is one of the hot topics in computer science of
the last decades. There are many problems where quantum algorithms outperform
the best known classical ones [12], and one of the most important performance
metrics in this regard is _query complexity_. We refer to [3] for a nice
survey on the quantum query complexity, and to [14, 13, 16, 15, 9] for the
more recent progress.

Among other problems, quantum technologies can reduce the query complexity of
recognizing many formal languages . In this paper we consider a problem of
recognizing whether an $n$-bit string belongs to one important _regular
language_. Although this problem may seem too specific, we believe our
approach to model a variety of computational tasks that can be described by
regular languages.

Aaronson, Grier and Schaeffer [1] have recently shown that any regular
language $L$ may have one of three possible quantum query complexities on
inputs of length $n$: $\Theta(1)$ if the language can be decided by looking at
$O(1)$ first or last symbols of a word; $\tilde{\Theta}(\sqrt{n})$ if the best
way to decide $L$ is Grover’s search (for example, for the language consisting
of all words containing at least one letter $a$); $\Theta(n)$ for languages in
which one can embed counting modulo some number $p$ which has quantum query
complexity $\Theta(n)$ (for example, the binary $XOR$ function).

As shown in [1], a regular language being of complexity $\tilde{O}(\sqrt{n})$
(which includes the first two cases of the list above) is equivalent to it
being _star-free_. Star-free languages are defined as the languages which have
regular expressions not containing the Kleene star (if it is allowed to use
the complement operation). Star-free languages are one of the most commonly
studied subclasses of regular languages and there are many equivalent
characterizations of them.

One class of the star-free languages mentioned in [1] is the Dyck languages
(with one type of brackets and with constant height $k$). To introduce a brief
intuition about these languages, we may mention that words “[ ]” and “[ [ ] [
] ]” belong to a Dyck language, while words “] [” and “[ ] ] [ [ ]” do not.
Formally, Dyck language with height $k$ consists of all words with balanced
number of brackets such that in no prefix the number of opening brackets
exceeds the number of closing brackets by more than $k$; we denote the problem
of determining if an input of length $n$ belongs to this language by
$\operatorname{\textsc{Dyck}}_{k,n}$. We note that such language of unbounded
height (i.e. $k=\frac{n}{2}$) is a fundamental example of a context-free
language that is not regular.

For this problem, Ambainis et al. [4] show that an exponential dependence of
the complexity on $k$ is unavoidable. Namely, for the balanced brackets
language (i) there exists $c>1$ such that, for all $k\leq\log n$, the quantum
query complexity is $\Omega(c^{k}\sqrt{n})$; (ii) if $k=c\log n$ for an
appropriate constant $c$, then the quantum query complexity is
$\Omega(n^{1-\epsilon})$.

Thus, the exponential dependence on $k$ is unavoidable and distinguishing
sequences of balanced brackets of length $n$ and depth $\log n$ is almost as
hard as distinguishing sequences of length $n$ and arbitrary depth. Similar
lower bounds have recently been independently proven by Buhrman et al. [7].
Additionally, Ambainis et al. [4] describe an explicit algorithm for the
decision problem $\operatorname{\textsc{Dyck}}_{k,n}$ with
$O\left(\sqrt{n}(\log{n})^{0.5k}\right)$ quantum queries. The algorithm also
works for arbitrary $k$, and outperforms the trivial upper bound of $n$ when
$k=o\left(\frac{\log n}{\log\log n}\right)$.

This work generalizes $\operatorname{\textsc{Dyck}}_{k,n}$ to the case of
multiple types of brackets. For example, such languages contain words like “[
( ) ]” and do not contain words like “[ ( ] )” (here square and round brackets
are the two different types of brackets). We denote the problem of determining
if an input of length $n$ belongs to the Dyck language of height $k$ and at
most $t$ types of brackets by $\operatorname{\textsc{Dyck}}_{k,n,t}$.
Obviously,
$\operatorname{\textsc{Dyck}}_{k,n,1}=\operatorname{\textsc{Dyck}}_{k,n}$.

We note that $\operatorname{\textsc{Dyck}}_{k,n}$ and
$\operatorname{\textsc{Dyck}}_{k,n,t}$ for $t>1$ are two substantially
different problems regarding classical (deterministic or randomized)
calculations. The former problem allows using a counter to keep the number of
currently open brackets and thus be content with the memory size of $O(\log
k)$. In contrast, the latter problem requires keeping all the sequence of
currently open brackets in a stack, which may take up to $O(k)$ memory. While
both problems are solvable in linear time, there is an exponential gap in the
memory usage.

In this paper we provide a quantum algorithm for
$\operatorname{\textsc{Dyck}}_{k,n,t}$ with quantum query complexity
$O(\sqrt{n}(\log n)^{0.5k})$. We apply the known technique of solving
$\operatorname{\textsc{Dyck}}_{k,n}$, and then perform a more complex but
slightly faster procedure to check the type-matching of the brackets.

The structure of the paper is the following. Section 2 describes some
conventional notions for quantum computation. Section 3 provides the main
algorithm and the proofs. The final subsection 3.3 contains the discussion on
the complexity of the algorithm and on the lower bounds.

##  2 Preliminaries

###  2.1 Definitions

We use the following formalism throughout the paper. We assume an input string
to consist of brackets of $t$ _types_ for some positive integer $t$; each type
is represented by a pair of brackets – an opening and a closing one. Further,
we assume the brackets to be encoded by integers from $1$ to $2t$, where the
opening and the closing brackets of $i$-th type correspond to the numbers
$2i-1$ and $2i$ respectively.

We define two functions:

  * •

Function $Type:\\{1,\dots,2t\\}\to\\{1,\dots,t\\}$ returns the type of a
bracket.
$Type(x)=\lceil x/2\rceil$.

  * •

Function $Open:\\{1,\dots,2t\\}\to\\{0,1\\}$ returns $1$ if the argument is an
opening bracket, or $0$ if it is a closing bracket.
$Open(x)=x\mod 2$.

For example, string “[ ( ) ]” could be encoded as “$1,3,4,2$”. Then

$Type(1)=Type(4)=1$ stand for the square brackets;

$Type(2)=Type(3)=2$ – for the parentheses;

$Open(1)=Open(2)=1$ – for the opening brackets; and

$Open(3)=Open(4)=0$ – for the closing brackets.

We call a string $S=(s_{1},\dots,s_{m})$ a _well-balanced_ sequence of
brackets if one of the following holds:

  1. 1.

$S$ is empty;

  2. 2.

$S$ consists of two well-balanced subsequent substrings, i.e. $S[1,i]$ and
$S[i+1,m]$ are both well-balanced for some $i$ (hereafter we denote by
$S[i,j]$ a substring $(s_{i},\dots,s_{j})$ of a string
$S=(s_{1},\dots,s_{m})$);

  3. 3.

$S$ is a correctly bracketed well-balanced sequence, i.e.

     * •

$S[2,m-1]$ is a well-balanced sequence,

     * •

$Type(s_{1})=Type(s_{m})$,

     * •

$Open(s_{1})=1$ and $Open(s_{m})=0$.

Obviously, the set of all well-balanced sequences of brackets defines the
$\operatorname{\textsc{Dyck}}$ language.

We also introduce a metric for the balancedness of a substring. Let $f$ be a
function which returns the difference between the numbers of opening and
closing brackets: $f(S[l,r])=\\#_{1}(S[l,r])-\\#_{0}(S[l,r]).$ (Here
$\\#_{x}(S[l,r])$ denotes the number of symbols $s_{j}$, for $l\leq j\leq r$,
such that $Open(s_{j})=x$). We define a $+k$-substring (resp. $-k$-substring)
as a substring whose balance is equal to $k$ (resp. equal to $-k$). A $\pm
k-$substring is a substring whose balance is equal to $k$ in absolute value.

We call a nonempty substring $S[l,r]$ _minimal_ if it does not contain a
nonempty substring $S[l^{\prime},r^{\prime}]$ such that
$(l,r)\neq(l^{\prime},r^{\prime})$ and
$f(S[l^{\prime},r^{\prime}])=f(S[l,r])$. We call a nonempty substring $S[l,r]$
_prefix-minimal_ if it does not start with $S[l,r^{\prime}]$ such that
$r^{\prime}<r$ and $f(S[l,r^{\prime}])=f(S[l,r])$. We define the _height_ of a
substring $S[l,r]$ as $h(S[l,r])=\max_{i\in\\{l,\ldots,r\\}}f(S[l,i])$.

For example, string $S=``\texttt{[~{}]~{}(~{})}^{\prime\prime}$ is well-
balanced, because it consists of two well-balanced substrings “[ ]” and “( )”,
which in turn both are correctly embraced empty strings. Its substring
$S[1,2]=``\texttt{[~{}]}^{\prime\prime}$ is both minimal and prefix-minimal,
whereas its substring $S[2,4]=``\texttt{]~{}(~{})}^{\prime\prime}$ is neither
minimal nor prefix-minimal (since $f(S[2,2])=f(S[2,4])=-1$).

Finally, we define the problem $\operatorname{\textsc{Dyck}}_{k,n,t}(S)$.
Function $\operatorname{\textsc{Dyck}}_{k,n,t}$ accepts
$S=(s_{1},\dots,s_{n})$ as an input and

  * •

returns $1$ if $S$ is a well-balanced sequence of brackets with at most $t$
types of brackets and with $h(S)\leq k$;

  * •

returns $0$ otherwise.

###  2.2 Computational Model

To evaluate the complexity of a quantum algorithm, we use the standard form of
the quantum query model. It is a generalization of the decision tree model of
classical computation that is commonly used to lower bound the amount of time
required for a computation.

Let $f:D\rightarrow\\{0,1\\}$, for some $D\subseteq\\{0,1\\}^{n}$, be an
$n$-argument binary function we wish to compute. We have an oracle access to
the input $x$ — it is implemented by a specific unitary transformation usually
defined as $|i\rangle|z\rangle|w\rangle\rightarrow|i\rangle|z\oplus
x_{i}\rangle|w\rangle$, where the $|i\rangle$ register indicates the index of
the variable we are querying, $|z\rangle$ is the output register, and
$|w\rangle$ is some auxiliary work-space. An algorithm in the query model
consists of alternating applications of arbitrary unitaries independent of the
input and the query unitary, and a measurement in the end. The smallest number
of queries for an algorithm that outputs $f(x)$ with probability
$\geq\frac{2}{3}$ on all $x$ is called the quantum query complexity of the
function $f$ and is denoted by $Q(f)$. Throughout this paper, by the running
time of an algorithm we mean a number of queries to oracle.

In particular, in this paper we assume the oracle to process queries $Type$
and $Open$ in constant time.

More information on quantum computation and query model can be found in [17,
3, 2].

To distinguish ordinary deterministic and randomized complexities from the
quantum complexity, they are traditionally called by one term _classical
complexity_.

##  3 Quantum Algorithm

Before introducing the algorithm for solving
$\operatorname{\textsc{Dyck}}_{k,n,t}(S)$, we mention the following result
from [4], which will be used as important subroutine.

######  Lemma 1 ([4], Theorem 3)

There exists a quantum algorithm that solves
$\operatorname{\textsc{Dyck}}_{k,n,1}$ in time $O(\sqrt{n}(\log n)^{0.5k})$.
The algorithm has two-side bounded error probability $\varepsilon<0.5$.

The algorithm for solving $\operatorname{\textsc{Dyck}}_{k,n,t}(S)$ generally
consists of three main steps:

Step 1. Check whether there are at most $t$ types of brackets, and return $0$
if the number of types exceeds $t$. This part is discussed in Section 3.1.

Step 2. Uniformize $S$ to just one type of brackets by considering a string
$Y=(y_{1},\dots,y_{n})$ where $y_{i}=Open(s_{i})$. Check whether
$\operatorname{\textsc{Dyck}}_{k,n,1}(Y)=1$ by using the algorithm from Lemma
1. If this is the case, then $S$ is a well-balanced sequence of brackets with
their types ignored. Otherwise, $S$ obviously is not well-balanced and
$\operatorname{\textsc{Dyck}}_{k,n,t}(S)=0$. This step almost exactly repeats
the algorithm from [4].

Step 3. Check whether for any substring $S[l,r]$ the following condition
holds: If $Y[l,r]$ is a well-balanced sequence of brackets (with their types
ignored) of depth $v$ and $Y[l+1,r-1]$ is a well-balanced sequence of brackets
of depth $v-1$, then (1) $Type(s_{l})=Type(s_{r})$; and (2) $S[l+1,r-1]$ is a
well-balanced sequence of brackets.

Step 3 should be considered as the main contribution of the paper, and we
describe it in detail in Section 3.2. By the definition of the problem, if $S$
passes all three checks, then $\operatorname{\textsc{Dyck}}_{k,n,t}(S)=1$. The
complexity of the problem is evaluated in Section 3.3

###  3.1 The Procedure for Step 1

Recall that by the assumption, all the brackets are encoded by integers from
$1$ to $2t$. Hence it only remains to check whether $S$ contains a bracket
with code $c>2t$. This problem obviously can be solved by Grover’s algorithm
[10, 5] for finding an argument $j$ (if any) such that $g(j)=1$, for an
arbitrary function $g:\\{1,\dots,n\\}\to\\{0,1\\}$ implemented as a quantum
oracle. Grover’s algorithm runs in time $O(\sqrt{n})$ and has error
probability at most $0.5$.

The assumption on encoding of brackets could be relaxed by allowing to use any
distinct integer for each kind of bracket. Then the problem becomes more
complex: determine whether a sequence $s_{1},\ldots,s_{n}$ contains at most
$2t$ distinct integers. The upper bound for its query complexity is
$O(\sqrt{n}t\log{t})$. We refer to Section 4 for more details.

###  3.2 The Procedure for Step 3

Assume that any $0$-substring $S[l^{\prime},r^{\prime}]$ with
$h(S[l^{\prime},r]^{\prime})\leq v-1$ is known to be a well-balanced sequence
of brackets. In this section we present a procedure that checks whether, under
this assumption, any $0$-substring $S[l,r]$ with $h(S[l,r])=v$ is a well-
balanced sequence of brackets.

We wish to implement a function $\textsc{CheckSubstr}(S,v)$ which returns

  * •

True if there exists a “wrong” (not well-balanced) sequence $S[l,r]$ such that
$h(S[l,r])=v$;

  * •

False otherwise.

If we had $\textsc{CheckSubstr}(S,v)$ implemented, then we could invoke it for
each $v\in\\{1,\dots,k\\}$. In case of all-False output, the function should
return False (“no wrong sequences”), otherwise True (“found a wrong sequence
for at least one height $v\in\\{1,\dots,k\\}$”).

We propose the following implementation of $\textsc{CheckSubstr}(S,v)$.

####  3.2.1 The case $v=1$.

We start with considering the case $v=1$. Let a function
$g^{1}:\\{1,\dots,n-1\\}\to\\{0,1\\}$ be such that $g^{1}(j)=1$ iff
$Open(s_{j})=1$, $Open(s_{j+1})=0$, and $Type(s_{j})\neq Type(s_{j+1})$. In
other words, the function indicates sequentially open and close brackets of
different types.

We use Grover’s algorithm to search for an argument $j\in\\{1,\dots,n\\}$ such
that $g^{1}(j)=1$. Hereafter we call this subroutine
$\textsc{Grover}(g^{1},1,n)$, where $g^{1}$ is the function run by a quantum
oracle in constant time, and $1\ldots n$ defines an interval to search in. If
$\textsc{Grover}(g^{1},1,n)$ finds such index $j$, then
$\textsc{CheckSubstr}(S,1)$ returns True, otherwise False.

Note that due to the complexity of Grover’s algorithm, the query complexity of
$\textsc{Grover}(g^{1},1,n)$ is $O(\sqrt{n})$, with the error probability at
most $0.5$.

####  3.2.2 The case $v>1$.

This step allows assuming any $0$-substring $S[l^{\prime},r^{\prime}]$ with
$h(S[l^{\prime},r^{\prime}])=v-1$ to be a well-balanced sequence of brackets.
Under this assumption, we show that the next property holds:

###### Lemma 2

If for an input string $S$, any $0$-substring $S[l^{\prime},r^{\prime}]$ with
$h(S[l^{\prime},r^{\prime}])=v-1$ is a well-balanced sequence of brackets,
then any prefix-minimal $0$-substring $S[l,r]$ with $h(S[l,r])=v$ is such that
$S[l+1,r-1]$ is either empty or a well-balanced sequence of brackets.

###### Proof

According to the definition of a prefix-minimal $0$-substring, we claim that
$S[l,r]$ does not contain any shorter prefix $0$-substring. In particular, it
means that $Open(s_{l})=1$ and $Open(s_{r})=0$. Therefore,
$h(S[l+1,r-1])=v-1$, and $S[l+1,r-1]$ is a $0$-substring. Due to the claim of
the lemma, $S[l+1,r-1]$ is a well-balanced sequence of brackets. $\Box$

Therefore, to complete checking whether the $0$-substring $S[l,r]$ with
$h(S[l,r])=v$ is a well-balanced sequence of brackets, it only remains to
check that $Type(s_{l})=Type(s_{r})$.

Let us present a subroutine that searches for a $0$-substring $S[l,r]$ with
$h(S[l,r])=v$ such that $Type(s_{l})\neq Type(s_{r})$. If this subroutine
finds nothing, it means that any $0$-substring $S[l,r]$ with $h(S[l,r])=v$ is
well-balanced.

We use the following property of prefix-minimal $0$-substrings:

###### Lemma 3

For any prefix-minimal $0$-substring $S[l,r]$ with $h(S[l,r])=v$, there exist
indices $r^{\prime}$ and $l^{\prime}$ such that

  * •

$l\leq r^{\prime}<l^{\prime}\leq r$,

  * •

$S[l,r^{\prime}]$ is a $+v$-substring,

  * •

$S[l^{\prime},r]$ is a $-v$-substring, and

  * •

there are no $\pm v$-substrings contained in $S[r^{\prime}+1,l^{\prime}-1]$.

###### Proof

Assume that there is no such index $r^{\prime}\in\\{l,\dots,r-1\\}$ that
$S[l,r^{\prime}]$ is a $+v$-substring. Then we consider the index
$j=\operatorname{argmax}_{j\in\\{l+1,\dots,r\\}}f(S[l,j])$ and note that
$h(S[l,r])=v$ implies $f(S[l,j])=v$, which contradicts the assumption. We
conclude the that the desired index $r^{\prime}$ exists.

Now assume that there is no such index
$l^{\prime}\in\\{r^{\prime}+1,\dots,r\\}$ that $S[l^{\prime},r]$ is a
$-v$-substring. Recall that by the definition of a $0$-substring,
$f(S[l,r])=0$. At the same time,
$f(S[l,r])=f(S[l,r^{\prime}])+f(S[r^{\prime}+1,r])$ and
$f(S[l,r^{\prime}])=v$. Therefore,
$f(S[r^{\prime}+1,r])=f(S[l,r])-f(S[l,r^{\prime}])=0-v=-v$, which contradicts
the assumption. We conclude that both desired indices $r^{\prime}$ and
$l^{\prime}$ exist.

Finally, assume sequence $S[r^{\prime}+1,l^{\prime}-1]$ to contain a $\pm
v$-substring. Then we consider the leftmost $\pm v$-substring
$S[l^{\prime\prime},r^{\prime\prime}]$, where $r^{\prime}<l^{\prime\prime}\leq
r^{\prime\prime}<l^{\prime}$.

If $S[l^{\prime\prime},r^{\prime\prime}]$ is a $+v$-substring, i.e.
$f(S[l^{\prime\prime},r^{\prime\prime}])=v$, then the minimality of
$l^{\prime\prime}$ implies $f(S[r^{\prime}+1,l^{\prime\prime}-1])>-v$. Then,

$f(S[l,r^{\prime\prime}])=f(S[l,r^{\prime}])+f(S[r^{\prime}+1,l^{\prime\prime}-1])+f(S[l^{\prime\prime},r^{\prime\prime}])\\\
=v+f(S[r^{\prime}+1,l^{\prime\prime}-1])+f(S[l^{\prime}+1,l^{\prime\prime}-1])>v$

contradicts the fact that $h(S[l,r])=\max_{j\in\\{l+1,r\\}}f(S[l,j])=v$.

To finish the proof, it remains only to consider (the impossibility of) the
case where $S[l^{\prime\prime},r^{\prime\prime}]$ is a $-v$-substring, i.e.
$f(S[l^{\prime\prime},r^{\prime\prime}])=-v$. In this case
$f(S[r^{\prime}+1,l^{\prime\prime}-1])$ can be negative, zero, or positive.

  * •

If $f(S[r^{\prime}+1,l^{\prime\prime}-1])<0$, then

$f(S[l,r^{\prime\prime}])=f(S[l,r^{\prime}])+f(S[r^{\prime}+1,l^{\prime\prime}-1])+f(S[l^{\prime\prime},r^{\prime\prime}])\\\
=v+f(S[r^{\prime}+1,l^{\prime\prime}-1])-v=f(S[r^{\prime}+1,l^{\prime\prime}-1])<0.$

Therefore, there exists such index $j$ that $j<r^{\prime\prime}<r$ and
$f(S[l,j])=0$, which contradicts the prefix-minimality of the $0$-substring
$S[l,r]$.

  * •

If $f(S[r^{\prime}+1,l^{\prime\prime}-1])=0$, then

$f(S[l,r^{\prime\prime}])=f(S[l,r^{\prime}])+f(S[r^{\prime}+1,l^{\prime\prime}-1])+f(S[l^{\prime\prime},r^{\prime\prime}])=0.$

Therefore, $f(S[l,r^{\prime\prime}])=0$ where $r^{\prime\prime}<r$, which
contradicts the prefix-minimality of the $0$-substring $S[l,r]$.

  * •

If $f(S[r^{\prime}+1,l^{\prime\prime}-1])>0$, then

$f(S[l,l^{\prime\prime}-1])=f(S[l,r^{\prime}])+f(S[r^{\prime}+1,l^{\prime\prime}-1])=v+f(S[r^{\prime}+1,l^{\prime\prime}-1])>v$

contradicts the fact that $h(S[l,r])=\max_{j\in\\{l+1,r\\}}f(S[l,j])=v$.

$\Box$

These lemmas allow to formulate the algorithm for searching for a not well-
balanced $0$-substring, with its length limited to be at most $d$:

  * Step 1.

Pick index $b$ uniformly at random in $\\{1,\dots,n\\}$.

  * Step 2.

Search for the leftmost $\pm v$-substring with length at most $d$, in
$S[b,\min(n,b+d-1)]$. If such substring $S[i_{r},j_{r}]$ was found, proceed to
Step 3. Otherwise proceed to Step 4.

  * Step 3.

Search for the rightmost $\pm v$-substring with length at most $d$ in
$S[\max(i_{r}-d,1),i_{r}-1]$. If such substring $S[i_{l},j_{l}]$ was found,
proceed to Step 6. Otherwise stop and return False.

  * Step 4.

Search for the rightmost $\pm v$-substring with length at most $d$ in
$S[\max(b-d+1,1),b]$. If such substring $S[i_{l},j_{l}]$ was found, proceed to
Step 5. Otherwise stop and return False.

  * Step 5.

Search for the leftmost $\pm v$-substring with length at most $d$ in
$S[j_{l}+1,\min(n,j_{l}+d)]$. If such substring $S[i_{l},j_{l}]$ was found,
proceed to Step 6. Otherwise stop and return False.

  * Step 6.

If $f(S[i_{l},j_{l}])>0$, $f(S[i_{r},j_{r}])<0$ and $Type(i_{l})\neq
Type(j_{r})$, then return the resulting substring $S[i_{l},j_{r}]$. Otherwise
stop and return False.

To search for the rightmost $\pm v$-substring or for the leftmost $\pm
v$-substring of length at most $d$ in a segment, we use a subroutine from [4]
with the following property:

######  Lemma 4 ([4], Property 2)

There is a quantum algorithm for searching for the leftmost or for the
rightmost $\pm v$-substring of length at most $d$, in a substring $S[l,r]$.
The query complexity of the algorithm is
$O(\sqrt{r-l}(\log(r-l))^{0.5(v-2)})$. It returns $(i,j,\sigma)$ such that
$S[i,j]$ is a $\pm v$-substring and $\operatorname{sign}(f(S[i,j]))=\sigma$.
It returns False if such substring does not exist.

Hereafter we call subroutines for the leftmost and for the rightmost $\pm
v$-substring respectively $\textsc{Leftmost}(S,l,r,v,d)$ and
$\textsc{Rightmost}(S,l,r,v,d)$. They return a triple $(i,j,\sigma)$, such
that $S[i,j]$ is the resulting substring and $\sigma=sign(f(S[i,j]))$. They
return False if there are no such $\pm v$-strings.

We formalize the algorithm in the code listing of Algorithm 1:

Algorithm 1 Search for a not well-balanced $0$-substring $S[l,r]$ with height
$h(S[l,r])=v$ and length $r-l+1\leq d$.

$\\{1,\dots,n\\}\xleftarrow{R}b$$\triangleright$ randomly pick $b$

$u_{r}=(i_{r},j_{r},\sigma_{r})\leftarrow\textsc{Leftmost}(S,b,\min(n,b+d-1),v,d)$

if $u_{l}\neq\textsc{False}$ then

$u_{l}=(i_{l},j_{l},\sigma_{l})\leftarrow\textsc{Rightmost}(S,\max(i_{r}-d,1),i_{r}-1,v,d)$

else

$u_{l}=(i_{l},j_{l},\sigma_{l})\leftarrow\textsc{Rightmost}(S,\max(b-d+1,1),b,v,d)$

if $u_{l}\neq\textsc{False}$ then

$u_{r}=(i_{r},j_{r},\sigma_{r})\leftarrow\textsc{Leftmost}(S,j_{l}+1,(n,j_{l}+d),v,d)$

end if

end if

if $u_{l}\neq\textsc{False}$ and $u_{r}\neq\textsc{False}$ and $\sigma_{l}=1$
and $\sigma_{r}=-1$ and $Type(s_{i_{l}})\neq Type(s_{j_{r}})$ then

return $(i_{l},j_{r})$

else

return False

end if

Assume that some string $S$ contains a not well-balanced $0$-substring
$S[l,r]$ with height $h(S[l,r])=v$ and length $d$. The probability of finding
such substring by this algorithm is equal to the probability of picking an
index inside the substring, and therefore can be estimated by $\Omega(d/n)$.
By applying the Amplitude amplification algorithm [6] for the randomized
Algorithm 1, we obtain an algorithm with query complexity
$O(\sqrt{\frac{n}{d}}\cdot{\sqrt{d}}(\log d)^{0.5(v-2)})=O(\sqrt{n}(\log
d)^{0.5(v-2)})$.

Next, we search for $d$ among the elements of set
$T=\\{2^{0},2^{1},2^{2},\dots,2^{\lceil\log_{2}n\rceil}\\}$. This can be done
also by using Grover’s algorithm. The overall complexity of the algorithm for
finding a $0$-substring $S[l,r]$ with height $h(S[l,r])=v$ and arbitrary
length is $O(\sqrt{n}(\log n)^{0.5(v-1)})$. We note that Grover’s algorithm
relies on an oracle with a two-side bounded error, whereas it is hardly
justified to assume a quantum oracle which directly handles $T$ to markup the
appropriate lengths. To address this issue, we use the modification of the
algorithm presented in [4, 11] and thus obtain the implementation of
$\textsc{CheckSubstr}(S,v)$.

Finally, we implement Step 3 in the code listing of Algorithm 2.

Algorithm 2 $\textsc{Step3}(S)$

$v\leftarrow 1$

while $v\leq k$ do

if $\textsc{CheckSubstr}(S,v)\neq\textsc{False}$ then

return True

end if

$v\leftarrow v+1$

end while

return False

Then the overall algorithm for the problem
$\operatorname{\textsc{Dyck}}_{n,k,t}$ can be formalized as in the code
listing of Algorithm 3.

Algorithm 3 Solving $\operatorname{\textsc{Dyck}}_{n,k,t}$

if $\textsc{Step1}(S)=1$ and $\operatorname{\textsc{Dyck}}_{n,k}(Y)=1$ and
$\textsc{Step3}(S)=\textsc{False}$ then

return $1$

else

return $0$

end if

###  3.3 Query complexity

In this section we estimate the query complexity of
$\operatorname{\textsc{Dyck}}_{k,n,t}$ and discuss properties of Algorithm 3.

###### Theorem 3.1

Algorithm 3 for solving $\operatorname{\textsc{Dyck}}_{k,n,t}$, has query
complexity $O(\sqrt{n}(\log n)^{0.5k})$ and a constant two-side bounded error
probability $\varepsilon<0.5$.

###### Proof

We start with the query complexity of the algorithm.

The complexity of Step 1 is obviously equal to the one of Grover’s algorithm,
i.e. to $O(\sqrt{n})$. Lemma 1 estimates the complexity of Step 2 as
$O(\sqrt{n}(\log n)^{0.5k})$. The complexity of Step 3 can be derived from the
code listing of Algorithm 2:

$O(\sum_{v=1}^{k}\sqrt{n}(\log n)^{0.5(v-1)})=O(\sqrt{n}(\log n)^{0.5(k-1)}).$

The overall complexity of Algorithm 3 is

$O(\sqrt{n})+O(\sqrt{n}(\log n)^{0.5k})+O(\sqrt{n}(\log
n)^{0.5(k-1)})=O(\sqrt{n}(\log n)^{0.5k}).$

We continue the proof by considering the error probability of the algorithm.
Step 1 has error probability at most $0.5$. Step 2 has constant error
probability $\varepsilon_{0}<0.5$. Step 3 has error probability at most
$1-(1-\varepsilon_{1})^{k}$ for some constant $\varepsilon_{1}<0.5$. As each
error probability is constant, we can obtain the desired overall error
probability $\varepsilon$ by exploiting the technique from [4], i.e. by a
series of repetitive calls of the algorithm. $\Box$

We finish our discussion with a couple of lower bounds of the query
complexity.

###### Theorem 3.2

There exists a constant $c_{1}>0$ such that
$Q(\operatorname{\textsc{Dyck}}_{c_{1}\ell,n,t})=\Omega(2^{\frac{\ell}{2}}\sqrt{n}).$

###### Proof

The similar bound holds for $Q(\operatorname{\textsc{Dyck}}_{c_{1}\ell,n,1})$
[4, Theorem 6]. By setting $t=1$ we get that
$\operatorname{\textsc{Dyck}}_{c_{1}\ell,n,t}$ is at least as hard as
$\operatorname{\textsc{Dyck}}_{c_{1}\ell,n,1}$. $\Box$

###### Theorem 3.3

For any $\gamma>0$, there exists a constant $c_{2}>0$ such that

$Q(\operatorname{\textsc{Dyck}}_{c_{2}\log n,n,t})=\Omega(n^{1-\gamma}).$

###### Proof

The similar bound holds for $Q(\operatorname{\textsc{Dyck}}_{c_{2}\log
n,n,1})$ that was presented in [4, Theorem 5]. By setting $t=1$ we get that
$\operatorname{\textsc{Dyck}}_{c_{2}\log n,n,t}$ is at least as hard as
$\operatorname{\textsc{Dyck}}_{c_{2}\log n,n,1}$. $\Box$

##  4 Generalizing Step 1 Algorithm

The restriction for all the brackets to be encoded by positive integers up to
$2t$, is quite significant for the proposed quantum algorithm. In contrast,
formulation of a more natural problem could assume arbitrary encoding of
different kinds of brackets. For example, a string could consist of brackets
like “( )”, “[ ]”, “{ }” in arbitrary encoding like ASCII, UTF-32, etc. Under
these circumstances, one still can distinguish the type of a certain bracket;
and still can determine whether a certain bracket is opening or closing; but
one cannot anymore determine how many different types of brackets occur in the
string.

Formally speaking, the fragment “at most $t$ types of brackets” from our
definition of $\operatorname{\textsc{Dyck}}_{k,n,t}$ means
$\left|\\{Type(s_{i}):1\leq i\leq n\\}\right|\leq t$ rather than
$\max_{i\in\\{1,\ldots,n\\}}Type(s_{i})\leq t$ which was assumed throughout
the paper. Hereafter we refer to such a more general formulation of the
problem as $\operatorname{\textsc{Dyck}}^{\prime}_{k,n,t}$. The implementation
of Step 1 from Section 3.1 is not suitable for solving
$\operatorname{\textsc{Dyck}}^{\prime}_{k,n,t}$, whereas the rest of the
algorithm does not depend on whether the codes of the types of brackets are
consecutive or not.

We note that in many cases this won’t be an issue, as the number of different
types of brackets $t$ typically is a small constant like $2$, $3$ or $4$.
However the following problem could be of certain interest even if not
connected with $\operatorname{\textsc{Dyck}}^{\prime}_{k,n,t}$:

###### Problem 1

Given a string $S$ of length $n$, and a limitation parameter $t$, determine
whether $\left|\left\\{Type\left(s_{i}\right):1\leq i\leq
n\right\\}\right|\leq t$.

Note that Step 1 from Section 3.1 obviously reduces to Problem 1.

In the rest of this section we propose an algorithm for solving this problem
and thus generalize our solution to
$\operatorname{\textsc{Dyck}}^{\prime}_{k,n,t}$, i.e. to the case with
arbitrarily encoded sequences of brackets.

Let $T$ be an integer such that $2T$ is an upper bound for the code of a
bracket in the input string (e.g. the size of the input alphabet). Let
$Type:\\{1,\dots,2T\\}\to\\{1,\dots,t\\}$ be a function that returns the type
of a bracket. Let
$q:\\{1,\dots,n\\}\times\\{1,\dots,2T+1\\}\to\\{0,\dots,2T\\}$ be a function
which returns

  * •

$q(i,r)=Type(i)$ if $Type(i)<r$; or

  * •

$q(i,r)=0$ otherwise.

We consider the following procedure:

  * Step $1$

Compute $y_{1}=max\\{q(i,2T+1),1\leq i\leq n\\}$ by using Dürr’s and Høyer’s
algorithm for finding the maximum [8]. Thus we compute the maximum among all
the codes of brackets.

  * Step $2$

Compute $y_{2}=max\\{q(i,y_{1}),1\leq i\leq n\\}$ in the same manner, the
second-biggest code among all the codes of brackets.

  * …

…

  * Step $j$

Compute $y_{j}=max\\{q(i,y_{j-1}),1\leq i\leq n\\}$.

This procedure lasts until $y_{j}=0$, which means that there are no bracket
codes less than $y_{j-1}$ and that there are exactly $j-1$ different types of
brackets contained in string $S$. Then condition $j-1\leq t$ indicates whether
Step 1 was executed correctly. We formalize this idea in the code listing of
Algorithm 4, assuming subroutine $\textsc{QMax}(q(*,y_{1}),1,n)$ to implement
the quantum algorithm for maximum search [8].

Algorithm 4 Step 1 for solving $\operatorname{\textsc{Dyck}}^{\prime}_{k,n,t}$

$j\leftarrow 1$

$y_{1}\leftarrow\textsc{QMax}(q(*,2T+1),1,n)$

while $y_{j}\neq 0$ do

if $j>t$ then

return $0$

end if

$j\leftarrow j+1$

$y_{j}\leftarrow\textsc{QMax}(q(*,y_{j-1}),1,n)$

end while

return $1$

###### Lemma 5

The query complexity of Algorithm 4 is $O(t\sqrt{n}\log t)$, and the error
probability is some constant $\varepsilon<1$.

###### Proof

The expected query complexity of $\textsc{QMax}(q(*,y_{j-1}),1,n)$ is
$O(\sqrt{n})$ [8]. According to Markov’s inequality, also the exact query
complexity of $\textsc{QMax}(q(*,y_{j-1}),1,n)$ is $O(\sqrt{n})$. As the error
probability of QMax is some constant, repeating it $2\log_{2}t$ times results
in the error probability $O(\frac{1}{t^{2}})$. $\Box$

If $t=O(\log n^{0.5(k-1)})$, then the query complexity of Algorithm 4 (run at
Step 1) won’t exceed the complexity of Step 2, and the overall complexity of
the algorithm will remain the same.

###### Theorem 4.1

Algorithm 3 with Step 1 implemented by Algorithm 4, solves
$\operatorname{\textsc{Dyck}}^{\prime}_{k,n,t}$. If $t=O(\log n^{0.5(k-1)})$,
then the query complexity of this solution is $O(\sqrt{n}(\log n)^{0.5k})$,
and the two-side bounded error probability is $\varepsilon<0.5$.

###### Proof

According to Lemma 5, the query complexity of Step 1 is $O(\sqrt{n}\log
n^{0.5(k-1)}\log\log n)=O(\sqrt{n}\log n^{0.5k})$. Steps 2 and 3 are the same
as in Algorithm 3, with complexities resp. $O(\sqrt{n}\log n^{0.5k})$ and
$O(\sqrt{n}\log n^{0.5(k-1)})$ proven as for Theorem 3.1. Thus the overall
query complexity is

$O(\sqrt{n}\log n^{0.5k})+O(\sqrt{n}\log n^{0.5k})+O(\sqrt{n}\log
n^{0.5(k-1)})=O(\sqrt{n}\log n^{0.5k}).$

The estimation of the error probability is analogous to the one in the proof
of Theorem 3.1 $\Box$

Although we strongly believe that there exists a more efficient quantum
algorithm for solving Step 1 of
$\operatorname{\textsc{Dyck}}^{\prime}_{k,n,t}$, but for now we limit our
considerations with the just proposed iterative maximum search.

Acknowledgements. The research is funded by the subsidy allocated to Kazan
Federal University for the state assignment in the sphere of scientific
activities, project No. 0671-2020-0065.

## References

  * [1] Scott Aaronson, Daniel Grier, and Luke Schaeffer.  A quantum query complexity trichotomy for regular languages.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 942–965. IEEE, 2019.
  * [2] F. Ablayev, M. Ablayev, J. Z. Huang, K. Khadiev, N. Salikhova, and D. Wu.  On quantum methods for machine learning problems part i: Quantum tools.  Big Data Mining and Analytics, 3(1):41–55, 2019.
  * [3] A. Ambainis.  Understanding quantum algorithms via query complexity.  In Proc. Int. Conf. of Math. 2018, volume 4, pages 3283–3304, 2018\.
  * [4] A. Ambainis, Kaspars Balodis, Jānis Iraids, Kamil Khadiev, Vladislavs Kļevickis, Krišjānis Prūsis, Yixin Shen, Juris Smotrovs, and Jevgēnijs Vihrovs.  Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language.  In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:14, 2020.
  * [5] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp.  Tight bounds on quantum searching.  Fortschritte der Physik, 46(4-5):493–505, 1998.
  * [6] G. Brassard, P. Høyer, M. Mosca, and A. Tapp.  Quantum amplitude amplification and estimation.  Contemporary Mathematics, 305:53–74, 2002.
  * [7] Harry Buhrman, Subhasree Patro, and Florian Speelman.  A Framework of Quantum Strong Exponential-Time Hypotheses.  In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), volume 187 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1–19:19, 2021.
  * [8] C. Dürr and P. Høyer.  A quantum algorithm for finding the minimum.  arXiv:quant-ph/9607014, 1996.
  * [9] Adam Glos, Nikolajs Nahimovs, Konstantin Balakirev, and Kamil Khadiev.  Upperbounds on the probability of finding marked connected components using quantum walks.  Quantum Information Processing, 20(1):1–23, 2021.
  * [10] Lov K Grover.  A fast quantum mechanical algorithm for database search.  In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219. ACM, 1996.
  * [11] Peter Høyer, Michele Mosca, and Ronald de Wolf.  Quantum search on bounded-error inputs.  In Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, and Gerhard J. Woeginger, editors, Automata, Languages and Programming, pages 291–299, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg.
  * [12] Stephen Jordan.  Quantum algorithms zoo, 2021.  http://quantumalgorithmzoo.org/.
  * [13] K. Khadiev, D. Kravchenko, and D. Serov.  On the quantum and classical complexity of solving subtraction games.  In Proceedings of CSR 2019, volume 11532 of LNCS, pages 228–236. 2019.
  * [14] K. Khadiev and L. Safina.  Quantum algorithm for dynamic programming approach for dags. applications for zhegalkin polynomial evaluation and some problems on dags.  In Proceedings of UCNC 2019, volume 4362 of LNCS, pages 150–163. 2019.
  * [15] Kamil Khadiev, Ilnaz Mannapov, and Liliya Safina.  The quantum version of classification decision tree constructing algorithm c5. 0.  CEUR Workshop Proceedings, 2500, 2019.
  * [16] D. Kravchenko, K. Khadiev, D. Serov, and R. Kapralov.  Quantum-over-classical advantage in solving multiplayer games.  Lecture Notes in Computer Science, 12448:83–98, 2020.
  * [17] M. A Nielsen and I. L Chuang.  Quantum computation and quantum information.  Cambridge univ. press, 2010.