Quantum and Classical Log-Bounded Automata for the Online Disjointness Problem

Abstract

We consider online algorithms with respect to the competitive ratio. In this paper, we explore one-way automata as a model for online algorithms. We focus on quantum and classical online algorithms. For a specially constructed online minimization problem, we provide a quantum log-bounded automaton that is more effective (has less competitive ratio) than classical automata, even with advice, in the case of the logarithmic size of memory. We construct an online version of the well-known Disjointness problem as a problem. It was investigated by many researchers from a communication complexity and query complexity point of view.

1. Introduction

In the paper, we discuss a computational model used to solve optimization problems. We focus on online algorithms that many researchers explore. An online algorithm processes an input data stream and outputs a data stream in an online fashion. It should return a piece of output variables immediately after reading a piece of input variables. At the same time, the best answer can depend on the whole input. The main goal is a minimization of an objective function (we call it the cost of an output). We can say that an online algorithm solves an online minimization problem. Researchers consider different measures of effectiveness for online algorithms [1,2]. At the same time, the competitive ratio is the most standard and useful [3,4]. If we consider the cost of the output generated by an online algorithm and the cost of the output produced by an optimal offline algorithm, then the competitive ratio is the ratio of these to costs. If the ratio is at most c in the worst case, then we call the algorithm c-competitive. We also can say that the competitive ratio of the algorithm is c.

Typically, online algorithms have no limits for time and memory complexity. The main restriction is a lack of knowledge about future input variables. At the same time, researchers develop online algorithms with different types of restrictions. Some of them are restrictions on memory [5,6,7,8,9,10,11], other ones are restrictions on time complexity [12,13,14]. Often, an algorithm with restricted resources is closer to real-world applications.

In this paper, we focus on the memory complexity of online algorithms. We expect that an input stream is such big that it cannot be stored entirely in memory. An online algorithm processes a data stream. That is why we can consider automata (streaming algorithms, state machines) as online algorithms for this setup. In the paper, we use the “log-bounded automata” term. It is a uniform automata-like model with memory such that the size of memory can depend on the length of an input. This model was explored in [5,7,8]. Note that the automaton is allowed to use only one input head in the considered model. Sometimes, for emphasizing that the model is input data processing model and it is “one-pass”, we call the model one-way log-bounded automata. It means that we cannot reread the input and store the whole required information about the past in memory. Sometimes, to emphasize that the algorithms are used as online algorithms or for solving an online minimization problem, we call the model one-way log-bounded automata for an online minimization problem.

We consider classical and quantum models of “log-bounded automata” as online algorithms. The classical model was developed in papers of different researchers [5,6,7,10,11] for a long time. At the same time, the quantum model was introduced several years ago in [8] and discussed in [9]. Quantum computing [15,16,17] itself is one of the hot topics in computer science of the last few decades. There are many problems where quantum algorithms outperform the best-known classical algorithms [18,19,20]. A restriction for the memory size is especially important for the quantum model of algorithms because near-future quantum computers are able to manipulate with a few qubits.

In the case of one-way log-bounded automata as online algorithms, we know that the quantum model can be more effective than its classical counterparts with respect to a competitive ratio. The result was proven for two cases. The first one is sublogarithmic size of memory [8]. The second case is polylogarithmic size of memory [21]. Note that if an algorithm can use the linear size of memory, then it can store the whole input in memory. In that case, it is equivalent to the standard online algorithm model without restriction on the memory size. That is why the only sub-linear size of memory is interesting in the case of the restricted size of memory.

Researchers also considered other quantum models. One of them is quantum online algorithms with repeated test [22]; another one is quantum online algorithms with restriction on the size of memory [23,24]; quantum algorithms with a buffer [25,26] and others. The question of comparing quantum and classical models was explored for data stream processing models by different researches [27,28,29,30,31,32,33,34,35,36,37,38,39,40].

Our Results

Let us focus on demonstrating the quantum supremacy in the case of the logarithmic size of memory. For this goal, we choose a problem and demonstrate that a quantum model for the problem is more effective than a classical counterpart.

A similar result was proven in [21]. At the same time, the problem that was considered in [21] has one restriction. It is not defined for all inputs and requires a pre-validation to check whether an input is permissible. Such problems are called “promise problems” or “partial functions”. It is an important restriction for a problem. The paper explores “total functions” or problems without a pre-validation procedure for an input.

We investigate an online minimization problem $\mathtt{onlineDISJ}$ that is based on the Disjointness Boolean function $DISJ(x,y)$. For some integer b, the function $DISJ$ is defined on two binary strings $\mathcal{S}=({\mathcal{S}}_1,\dots {\mathcal{S}}_b)$ and $\mathcal{U}=({\mathcal{U}}_1,\dots ,{\mathcal{U}}_b)$, and $DISJ(\mathcal{S},\mathcal{U})=\neg {\bigvee }_{i=1}^b{\mathcal{S}}_i\wedge {\mathcal{U}}_i$. Here $\mathcal{S}$ and $\mathcal{U}$ are bit-masks (or characteristic vectors) of two input sets $\mathtt{A},\mathtt{B}\subset \{1,\dots ,b\}$. The result is 1 iff $\mathtt{A}\cap \mathtt{B}=\varnothing$.

Researchers explored communication complexity and quantum query algorithms for the Disjointness Boolean function [41,42,43]. Additionally, the function was used for comparing quantum and classical streaming algorithms in [28].

In this paper, we consider an online version of this well-known problem that is $\mathtt{onlineDISJ}$. The definition of the $\mathtt{onlineDISJ}$ problem is based on the problems that were presented in [28,44]. We provide a c-competitive quantum log-bounded automaton for $\mathtt{onlineDISJ}$, and we show that any classical counterpart is less effective. Formally, any log-bounded automaton for the problem is $c^{\prime }$-competitive and $c^{\prime }>c$. A similar result was presented in [44]. This paper presents a more significant separation between the competitive ratios of quantum and classical algorithms.

Often, online algorithms are investigated in terms of advice complexity measure [45,46,47]. We are interested in this measure also. The model with advice was not considered in [44].

The main point of the model is the following one. An online algorithm gets some bits of advice about an input. A trusted Adviser sending these bits knows the whole input and has unlimited computational power. Such additional information helps the online algorithm for the computation process and allows to obtain a better competitive ratio. Deterministic and randomized online algorithms with advice are considered in [45,48,49]. Typically, online algorithms researchers use the “Adviser” term, and other models researchers use the “Oracle” term.

In this paper, we provide a quantum log-bounded automaton for $\mathtt{onlineDISJ}$ with a single advice bit and a logarithmic size of memory that is almost optimal, i.e., $\tilde{c}$-competitive for $lim\tilde{c}=1$. At the same time, any classical algorithm with the logarithmic size of memory is less effective. Formally, any classical algorithm with the logarithmic size of memory is $c^{″}$-competitive and $c^{″}>1$.

Note that the usage of a specially constructed problem for demonstrating the power of models is a common approach. Sometimes the problems are artificial, but they allow authors to show more representative results [45,49,50].

The paper is organized as follows. We give definitions in Section 2. In Section 3.1 we present our results for the quantum models and Section 3.2 contains results for classical models. The conclusion is presented in Section 4.

2. Preliminaries

In the paper, we use different notations for $\delta$-functions. A function $\delta :\mathbb{R}\times \mathbb{R}\to \{0,1\}$ is such that $\delta (a,b)=1$ iff $a=b$. A function ${\delta }_x$ is such that ${\delta }_x=1$ if $x\ne 0$; otherwise, ${\delta }_x=0$. So, ${\delta }_x=1-\delta (x,0)$.

Let us define the computational models.

An online minimization problem is presented by a set of possible inputs $\mathcal{I}$ and a cost function. An input $I=(x_1,\dots ,x_n)$ is a sequence of input variables. Here n is a length of the input, shortly $\left|I\right|=n$. Let $\mathcal{O}\left(I\right)$ be a set of feasible outputs associated with an input I. An output is a sequence of output variables $O=(y_1,\dots ,y_n)$. The cost function assigns a positive real value $cost(I,O)$ to an input $I\in \mathcal{I}$ and an output $O\in \mathcal{O}\left(I\right)$. We call $O_{opt}\left(I\right)$ an optimal solution for $I\in \mathcal{I}$ if it satisfies the next statement

$$O_{opt}\left(I\right)={argmin}_{O\in \mathcal{O}\left(I\right)}cost(I,O).$$

An online algorithm for this problem is defined as follows. A deterministic online algorithm A outputs a sequence $A\left(I\right)=(y_1,\dots ,y_n)$ such that the variable $y_i$ is computed from input variables $x_1,\dots ,x_i$.

An algorithm A is c-competitive if we can present a constant $\alpha \ge 0$ such that for every positive integer n and for any input $I\in \mathcal{I}$ of size n, the following statement is correct

$$cost(I,A(I\left)\right)\le c·cost(I,Opt(I\left)\right)+\alpha .$$

Here $Opt\left(I\right)$ is an output of an optimal offline algorithm for the considered problem; c is the minimal number that satisfies the inequality. The number c is the competitive ratio of the algorithm A. In a case of $\alpha =0$ and $c=1$, the algorithm A is optimal. Typically c is constant. At the same time, c can be a function on n.

We can define An online algorithm A with advice as a sequence of algorithms $A=(A^0,\dots ,A^{2^b-1})$ where $b=b\left(n\right)$. The trusted adviser chooses $\varphi \in \{0,\dots ,2^{b-1}\}$ that depends on an input I and the algorithm $A^{\varphi }$ computes an output sequence $A^{\varphi }\left(I\right)=(y_1,\dots ,y_n)$ such that $y_i=y_i(x_1,\dots ,x_i)$. An algorithm A is c-competitive with advice complexity $b=b\left(n\right)$ if there exists a constant $\alpha \ge 0$ such that, for every n and for any input I of size n, there exists some $\varphi \in \{0,\dots ,2^{b-1}\}$ such that $cost(I,A^{\varphi }\left(I\right))\le c·cost(I,Opt\left(I\right))+\alpha$.

A randomized online algorithmR computes an output sequence $R^{\psi }\left(I\right)=(y_1,\dots ,y_n)$ such that $y_i$ is computed from $\psi ,x_1,\dots ,x_i$, where $\psi$ is a content of the random tape, i. e., an infinite binary sequence, where every bit is chosen uniformly at random and independently of all the others. By $cost(I,R^{\psi }\left(I\right))$ we denote the random variable expressing the cost of the solution computed by R on I. R is c-competitive in expectation if there exists a constant $\alpha \ge 0$ such that, for every I, $𝔼\left[cost(I,R^{\psi }\left(I\right))\right]\le c·cost(I,Opt\left(I\right))+\alpha$.

We use one-way automata for online minimization problems as online algorithms with restricted memory size. In the paper, we use the terminology for branching programs [51] and algorithms. We say that an automaton computes a Boolean function $f_m$ if for any input X of length m, the automaton returns 1 iff $f_m\left(X\right)=1$. We can say that an automaton returns 1 if it accepts an input word and returns 0 otherwise. Additionally, we use the terminology on memory from algorithms. We say that an automaton has s bits of memory if it has $2^s$ states. In fact, the model that we consider is a stable id-OBDD [30,31,51], that is an algorithm that uses at most s bits of memory and processes a data stream.

Let us present the definitions of log-bounded automata that we use. A deterministic log-bounded automaton with $s=s\left(n\right)$ bits of memory that processes an input $I=(x_1,\dots ,x_n)$ is a 4-tuple $(d_0,D,\Delta ,Result)$.

• The set D is a set of states, $\left|D\right|=2^s$, $d_0\in D$ is the initial state.
• The function $\Delta$ is a transition function $\Delta :\{0,\dots ,\gamma -1\}\times D\to D$, where $\gamma$ is a size of the input alphabet.
• $Result$ is an output function $Result:D\to \{0,\dots ,\beta -1\}$, where $\beta$ is a size of the output alphabet.

It is a uniform model. The computation starts from the state $d_0$. Then, on reading an input symbol $x_j$, it changes the current state $d\in D$ to $\Delta (x_j,d)$. At the end of the computation, the automaton outputs $Result\left(d\right)$.

A probabilistic log-bounded automaton is a probabilistic counterpart of the model. It chooses from more than one transition in each step such that each transition is associated with a probability. Thus, the automaton can be in a probability distribution over states during the computation. The total probability must be 1, i.e., the sum of probabilities of outgoing transitions from a single state for a single letter must be 1. Thus, a probabilistic automaton returns a result for each input with some probability. For $v\in \{0,\dots ,\beta -1\}$, the automaton returns a result v for an input with bounded-error if the automaton returns the result v with probability at least $1/2+\epsilon$ for some $\epsilon \in (0,1/2]$. The automaton computes a function $f:{\{0,\dots ,\gamma -1\}}^n\to \{0,\dots ,\beta \}$ with bounded error if it returns $f\left(X\right)$ with bounded error for each $X\in {\{0,\dots ,\gamma -1\}}^n$. The automaton computes a function f exactly if $\epsilon =0.5$.

A deterministic online streaming algorithm (a deterministic log-bounded automaton for online minimization problem) with $s=s\left(n\right)$ bits of memory that process input $I=(x_1,\dots ,x_n)$ is a 4-tuple $(d_0,D,\Delta ,Result)$.

• The set D is a set of states, $\left|D\right|=2^s$, $d_0\in D$ is the initial state.
• $\Delta$ is a transition function $\Delta :\{0,\dots ,\gamma -1\}\times D\to D$.
• $Result$ is an output function $Result:D\to \{0,\dots ,\beta -1\}$.

The computation starts from the state $d_0$. Then on reading an input symbol $x_j$ it change the current state $d\in D$ to $\Delta (x_j,d)$ and outputs $Result\left(d\right)$. The main difference between an “online streaming algorithm” and a standard “online algorithm” definition is a restriction on memory and forbidding reading the previous input variables.

A randomized online streaming algorithm and a deterministic online streaming algorithm with advice have similar definitions, but with respect to definitions of corresponding models of online algorithms.

Comment. Note that any online algorithm can be simulated by an online streaming algorithm (automaton for online minimization problem) using $O\left(n\right)$ bits of memory. It is n bits in the case of binary input and $\lceil n{log}_2\gamma \rceil$ bits in the general case.

Let us consider a quantum online streaming algorithm (quantum log-bounded automaton for online minimization problem). More information on quantum computation and quantum streaming computational models (automata) can be found in [17,35,52,53,54]. For some integer $n>0$, a quantum online algorithm Q with q qubits is defined on an input $I=(x_1,\dots ,x_n)\in {\{0,\dots ,\gamma -1\}}^n$ and outputs $(y_1,\dots ,y_n)\in {\{0,\dots ,\beta -1\}}^n$. A memory of the quantum algorithm is a state of a quantum register of q qubits. In other words, the computation of Q on an input I can be traced by a $2^q$-dimensional vector from Hilbert space over the field of complex numbers. The initial state is a given $2^q$-vector ${|\psi \rangle }_0$ (we use Dirac notation for vectors). The algorithm can perform one of two kinds of operators. The first one is applying a unitary $2^q\times 2^q$-matrix. The second one is measurement.

Let us describe a measurement process. Suppose that Q is in a state $|\psi \rangle =(v_1,\dots ,v_{2^q})$ before a measurement and the algorithm measures the i-th qubit. Let 0-value for the qubit i is associated with states $a_1^0,\dots ,a_{2^{q-1}}^0$; let 1-value for the qubit i is associated with states $a_1^1,\dots ,a_{2^{q-1}}^1$. If we measure the qubit, then we obtain 1-result with probability ${\mathtt{Pr}}_1={\sum }_{j=1}^{2^{q-1}}{\left|v_{a_j^1}\right|}^2$ and we obtain 0-result with probability ${\mathtt{Pr}}_0=1-{\mathtt{Pr}}_1$. If the result of the measurement is $u\in \{0,1\}$, then after measurement, the quantum system is converted to the state $\left|\psi \right(u)\rangle$ such that $v_{a_j^u}\left(u\right)=v_{a_j^u}/\sqrt{{\mathtt{Pr}}_u}$, where $v_{a_j^u}\left(u\right)$ is an element of the new vector and $v_{a_j^u}$ is an element of the old vector. All other elements of the new vector are 0.

Suppose, on j-th step, the algorithm measures v qubit. Then, an outcome of the measurement is $u\in \{0,\dots ,2^v-1\}$. We test $x_j$ variable on j-th step, for $j\in \{1,\dots ,n\}$. The algorithm does all three following operations in the presented order.

1.

It does a measurement. Let the outcome be u.

2.

The algorithm applies a unitary $2^q\times 2^q$-matrix $G^{x_j,u}$ that depends on the input variable $x_j$ and the outcome u.

3.

It does a measurement. Let the outcome be $u^{\prime }$. Then, the algorithm outputs $Result\left(u^{\prime }\right)$ on this step. Here $Result:\{0,\dots ,2^q-1\}\to \{0,\dots ,\beta -1\}$ is a function that converts the result of the measurement to an output variable.

The algorithm Q is c-competitive in expectation if there exists a non-negative constant $\alpha$ such that, for every I, $\mathbb{E}\left[cost\right(I,Q\left(I\right)\left)\right]\le c·cost(I,Opt(I\left)\right)+\alpha$.

A quantum log-bounded automaton has a similar definition, but it returns $Result\left(u\right)$ at the end of the computation. See [35,55] for more details on quantum automata.

3. On Quantum Online Streaming Algorithm for the Online Disjointness Problem

Let us define ${\mathtt{onlineDISJ}}_{t,k,r,w}$ problem that is based on the Disjointness Boolean function. The $DISJ:{\{0,1\}}^b\times {\{0,1\}}^b\to \{0,1\}$ function is such that

$$DISJ(\mathcal{S},\mathcal{U})=\neg \underset{i=1}{\overset{b}{\bigvee }}{\mathcal{S}}_i\wedge {\mathcal{U}}_i.$$

We can say that $\mathcal{S}$ and $\mathcal{U}$ are bit-masks or characteristic vectors for sets $\mathtt{A},\mathtt{B}\subset \{1,\dots ,b\}$. The function is such that $DISJ(\mathcal{S},\mathcal{U})=1$ iff the corresponding have no intersections, i.e., $\mathtt{A}\cap \mathtt{B}=\varnothing$. For some positive integers t, k, r, and w such that k mod t = 0, $r<w$, the online minimization problem ${\mathtt{onlineDISJ}}_{t,k,r,w}$ is organized as follows. Figure 1 describes the structure of an input.

Let m be an positive integer. Formally, an input $I=(x_1,\dots ,x_n)\in {\{0,\dots ,6\}}^n$ has the following structure: $I=bin\left(m\right)6L^{1}6L^{2}6\dots 6L^k,$ where $bin\left(m\right)$ is a binary representation of m and $L^i\in {\{0,\dots ,5\}}^{\ast }$, where $1\le i\le k$. For some positive integer n, let $\left|I\right|=n$. Let $MDIS{J}^m:{\{0,\dots ,5\}}^{\ast }\to \{0,1\}$ be a function such that $MDIS{J}^m\left(L^i\right)=1$ iff the following properties are right:

1.

For some positive integer $m_i$ and binary strings ${\mathcal{Z}}^{i,j},{\mathcal{U}}^{i,j},{\mathcal{S}}^{i,j},M^i$, the structure of $L^i$ is $L^i=M^{i}5{\mathcal{S}}^{i,1}2{\mathcal{U}}^{i,1}3{\mathcal{Z}}^{i,1}4\dots 4{\mathcal{S}}^{i,m_i}2{\mathcal{U}}^{i,m_i}3{\mathcal{Z}}^{i,m_i}4;$

2.

${\mathcal{S}}^{i,1}=\dots ={\mathcal{S}}^{i,m_i},$${\mathcal{U}}^{i,1}=\dots ={\mathcal{U}}^{i,m_i}$ and ${\mathcal{Z}}^{i,1}=\dots ={\mathcal{Z}}^{i,m_i};$

3.

${\mathcal{S}}^{i,1}={\mathcal{Z}}^{i,1}$;

4.

$|{\mathcal{S}}^{i,1}|=|{\mathcal{U}}^{i,1}|$, where $\left|v\right|$ is a length of a vector v;

5.

$val\left(M^i\right)=m_i=2+2\lceil \sqrt{|{\mathcal{S}}^{i,1}|}\rceil ·\lceil {log}_2|{\mathcal{S}}^{i,1}{|\rceil }^2$, where $M^i$ is a binary representation of an integer $val\left(M^i\right)$.

6.

The value of the function $DISJ({\mathcal{S}}^{i,1},{\mathcal{U}}^{i,1})=1$.

7.

$m_i=m$.

The authors of [28] have constructed a problem using a similar idea.

For $i\in \{1,\dots ,k\}$, let a Boolean variable $g_i$ be such that $g_i={⨁}_{j=i}^{k}MDIS{J}^m\left(L^j\right)$. Let $O^{\prime }=(y_1,\dots ,y_k)$ be output variables that correspond to input variables $x_j=6$. The cost function is

$$cost(I,O^{\prime })=tw+(r-w)·\sum _{q=0}^t\prod _{j=q·T+1}^{q·T+T}\delta (g_j,y_j),$$

where $T=k/t$. Recall, parameters $t,k,w$ and r or the problem satisfy conditions k mod $t=0$ and $r<w$. Let us discuss the meaning of the cost function. The output is split into t blocks. The size of each block is T. We say that a block is “right” if all each element $y_j$ from the block satisfies $y_j=g_j$. Otherwise it is a “wrong” block. The cost of a “right” block is r, and the cost of a “wrong” block is w. The sum of costs of all blocks is the total cost of the output. Our goal is to develop an algorithm that minimizes the cost of the output. A similar concept of the cost function was used, for example, in [49].

3.1. A Quantum Online Streaming Algorithm for the Online Disjointness Problem

Let us discuss a quantum log-bounded automaton for $MDISJ$ function. For construction of the automaton, we will use the following existing result:

Lemma 1

([56]). We can construct a quantum log-bounded automaton that checks the equality of two binary strings with bounded error ${\epsilon }^{\prime }$ for ${\epsilon }^{\prime }>0$. The size of the memory of the automaton is $O(logd-log{\epsilon }^{\prime })$.

Note that the proof of the following lemma is similar to the proof from [44]. At the same time, the structure of $MDIS{J}^m\left(L^i\right)$ differs from the structure of the corresponding function from [44]. That is why we present the full proof here. The current form of the function allows us to obtain better error probability.

Lemma 2.

Suppose that we have a quantum register $|\mu \rangle$ that stores m, i.e., $|\mu \rangle =|m\rangle$. There is a bounded error quantum log-bounded automaton for $MDIS{J}^m\left(L^i\right)$ that uses $O(logd)$ qubits of memory and has $O\left(\frac{1}{d}\right)$ error probability for $d=|L^i|$, where $|L^i|$ is a length of $L^i$.

Proof. 

As proof, we construct a quantum automaton for the $MDIS{J}^m\left(L^i\right)$ problem. The automaton consists of five parallel procedures. A procedure per property from the following list:

1.

For an integer b, the string $L^i$ have the following structure:

$$L^i={\{0,1\}}^{\ast }5{\left({\{0,1\}}^{b}2{\{0,1\}}^{b}3{\{0,1\}}^{b}4\right)}^{\ast }.$$

Here, we use ${}^{\ast }$ for several repetitions of the string.

2.

The string $M^i$ satisfies $val\left(M^i\right)=m_i=2+2\lceil \sqrt{|{\mathcal{S}}^{i,1}|}\rceil ·\lceil {log}_2|{\mathcal{S}}^{i,1}{|\rceil }^2$ and $m=m_i$;

3.

${\mathcal{S}}^{i,1}=\dots ={\mathcal{S}}^{i,m_i}$, ${\mathcal{U}}^{i,1}=\dots ={\mathcal{U}}^{i,m_i}$ and ${\mathcal{Z}}^{i,1}=\dots ={\mathcal{Z}}^{i,m_i}$;

4.

${\mathcal{S}}^{i,1}={\mathcal{Z}}^{i,1}$;

5.

$DISJ({\mathcal{S}}^{i,1},{\mathcal{U}}^{i,1})=1$.

Property 1. We use a deterministic procedure for checking the first property. The size of memory is $O(logd)$. Firstly, we check whether the strings have the following structure

$${\{0,1\}}^{\ast }5{\left({\{0,1\}}^{\ast }2{\{0,1\}}^{\ast }3{\{0,1\}}^{\ast }4\right)}^{\ast }.$$

We can do it using a constant number of states. Secondly, it checks that all binary parts have the same length and stores its length in a quantum register $|{\lambda }^{\prime }\rangle$. We can use $O\left(d\right)$ states or $O(logd)$ memory. The detailed implementation is presented in Appendix A.1.

Property 2. We use a deterministic procedure for checking the second property. We store the $M^i$ string and compute a number of 4s and 5s that is $m_i$. Then, we check whether $m=val\left(M^i\right)=m_i=2+2{\lceil {log}_2\sqrt{b}\rceil }^2·\lceil \sqrt{b}\rceil$ is correct, where $b=|{\mathcal{S}}^{i,1}|$. The algorithm stores $M^i$ and counts $m_i$ using $O\left(d\right)$ states or $O(logd)$ bits of memory. The algorithm for the first property already stored b and m is stored in $|\mu \rangle$, that is why we can use them for checking the equality. The detailed implementation is presented in Appendix A.2.

Property 3. We use a quantum fingerprinting technique [56,57] based on a quantum procedure for checking the third property. We assemble two strings from the existing ones:

$$s^1=({\mathcal{S}}^{i,1}\circ {\mathcal{U}}^{i,1}\circ {\mathcal{Z}}^{i,1})\circ ({\mathcal{S}}^{i,2}\circ {\mathcal{U}}^{i,2}\circ {\mathcal{Z}}^{i,2})\circ \dots \circ ({\mathcal{S}}^{i,m_i-1}\circ {\mathcal{U}}^{i,m_i-1}\circ {\mathcal{Z}}^{i,m_i-1}),$$

$$s^2=({\mathcal{S}}^{i,2}\circ {\mathcal{U}}^{i,2}\circ {\mathcal{Z}}^{i,2})\circ ({\mathcal{S}}^{i,3}\circ {\mathcal{U}}^{i,3}\circ {\mathcal{Z}}^{i,3})\circ \dots \circ ({\mathcal{S}}^{i,m_i}\circ {\mathcal{U}}^{i,m_i}\circ {\mathcal{Z}}^{i,m_i}),$$

where “∘” is concatenation. If $s^1=s^2$, then

$${\mathcal{S}}^{i,1}={\mathcal{S}}^{i,2},{\mathcal{S}}^{i,2}={\mathcal{S}}^{i,3},\dots ,{\mathcal{S}}^{i,m_i-1}={\mathcal{S}}^{i,m_i},$$

$${\mathcal{U}}^{i,1}={\mathcal{U}}^{i,2},{\mathcal{U}}^{i,2}={\mathcal{U}}^{i,3},\dots ,{\mathcal{U}}^{i,m_i-1}={\mathcal{U}}^{i,m_i}$$

and

$${\mathcal{Z}}^{i,1}={\mathcal{Z}}^{i,2},{\mathcal{Z}}^{i,2}={\mathcal{Z}}^{i,3},\dots ,{\mathcal{Z}}^{i,m_i-1}={\mathcal{Z}}^{i,m_i}.$$

Let us choose ${\epsilon }^{\prime }=1/d$. Due to Lemma 1, we can present a log-bounded automaton for checking equality of $s^1$ and $s^2$. The size of memory is $O(logd)$. The detailed implementation is presented in Appendix A.3.

Property 4. We use a quantum procedure for checking the fourth property. The procedure is based on the quantum fingerprinting method also and checks whether ${\mathcal{S}}^{i,1}={\mathcal{Z}}^{i,1}$ is correct. We construct an automaton using Lemma 1 for checking the property with bounded error ${\epsilon }^{″}$. Suppose ${\epsilon }^{″}=1/d$, then the automaton reaches an error probability $O\left(\frac{1}{d}\right)$ using $O(logd)$ qubits. The detailed implementation is presented in Appendix A.4.

Property 5. We use a quantum procedure for checking the fifth property, and it uses some ideas from [28]. As a base, we use the well-known Grover’s algorithm [58,59] for the unstructured search problem. The size of quantum memory for the procedure is $O(logd)$ and error probability is $O(1/b)$. Let us present the description of the procedure. Let $\mathcal{S}={\mathcal{S}}^{i,1}$ and $\mathcal{U}={\mathcal{U}}^{i,1}$. If the input satisfies the first four properties, then we can say that the input is m copies of $\mathcal{S}\circ \mathcal{U}\circ \mathcal{S}$ string. The Grover’s Search algorithm was defined for Query model [16,17] and it does $O\left(\sqrt{b}\right)$ queries to the oracle or $O(\sqrt{b}logb)$ queries in a case of unknown number of solutions. We simulate a query to the oracle by reading the input string $\mathcal{S}\circ \mathcal{U}\circ \mathcal{S}$. So, $O(\sqrt{b}logb)$ copies of this string allow as to provide multiple queries. We simulate the search of the index $a_0$ such that ${\mathcal{S}}_{a_0}={\mathcal{U}}_{a_0}=1$ or ${\mathcal{S}}_{a_0}\wedge {\mathcal{U}}_{a_0}=1$. In that case $DISJ({\mathcal{S}}^{i,1},{\mathcal{U}}^{i,1})=0$.

Let us provide the emulation of a query to the oracle. We have $p=\lceil {log}_2(b+1)\rceil$ qubits as a quantum register $|\phi \rangle$, p qubits as a quantum register $|{\phi }_{ones}\rangle$. Additionally, there is a qubit $|{\phi }^{\prime }\rangle$ and a qubit $|{\phi }^{″}\rangle$.

Initially, the quantum system is in the $|0\rangle \otimes |0\rangle \otimes |0\rangle \otimes |0\rangle$ state. Firstly, the automaton reads the ${\mathcal{S}}^{i,2}$ string. In other words, it processes $s^2$. We assume that the automaton already knows b on this step. Firstly, we apply the Hadamard transformation for obtaining the following state $|\phi \rangle \to \frac{1}{\sqrt{2^p}}{\sum }_{a=0}^{2^p-1}|a\rangle$. Then, we apply the inversion transformation (X-gate or NOT-gate) for obtaining the following state $|{\phi }_{ones}\rangle \to |1\rangle$.

We split the automaton’s steps to macro-steps. The l-th one is reading ${\mathcal{S}}^{i,l},{\mathcal{U}}^{i,l},{\mathcal{Z}}^{i,l}$ strings for $l\in \{2,\dots ,m\}$. During checking the third property, we store l in $|{\varphi }^{″}\rangle$. The computing process of l is presented in Appendix A.3. Assume that the automaton reads ${\mathcal{S}}^{i,l}$ string’s a-th symbol. If the automaton reads 1, then we apply the V transformation to registers $|\phi \rangle \otimes |{\phi }^{\prime }\rangle$. Here $V:|a\rangle \otimes |u\rangle \to |a\rangle \otimes |u\oplus 1\rangle$ for $1\le a\le b$. The automaton does not change the quantum registers if it reads 0.

Assume that the automaton reads ${\mathcal{U}}^{i,l}$ string’s a-th symbol. If the automaton reads 1, then we apply the W transformation to registers $|\phi \rangle \otimes |{\phi }^{\prime }\rangle$. Here $W:|a\rangle \otimes |u\rangle \to {(-1)}^u|a\rangle \otimes |u\rangle$ for $1\le a\le b$. The automaton does not change the quantum registers if it reads 0. In other words, the amplitude for a state $|a\rangle$ is inverted only if ${\mathcal{S}}_a={\mathcal{U}}_a=1$. Indexes with such property are our solution. We process the ${\mathcal{Z}}^{i,l}$ string exactly like we process the ${\mathcal{S}}^{i,l}$ string.

Remember that we already tested the equality ${\mathcal{Z}}^{i,l}={\mathcal{S}}^{i,l}$ in procedure 3 and procedure 4. Therefore, after processing ${\mathcal{Z}}^{i,l}$, the effect that ${\mathcal{S}}^{i,l}$ does to the second register is removed. One macro step simulates one query of Grover’s search algorithm.

Then, we apply Grover’s diffusion transformation to the register $|\phi \rangle$. The transformation is $D=H^{\otimes p}R{H}^{\otimes p}$. It rotates all amplitudes near the mean, where R is a unitary transformation that inverts sign for all basis states except zero basis state. Reader can find details on the Grover’s diffusion transformation D in [58,59].

One macro-step (processing of strings ${\mathcal{S}}^{i,l},{\mathcal{U}}^{i,l},{\mathcal{Z}}^{i,l}$) and the Grover’s diffusion transformation together correspond to one step of Grover’s search algorithm. Due to [59], the automaton simulate $\frac{\pi }{4}\sqrt{N/v}$ steps of the algorithm if $v=\left|\right\{a:{\mathcal{S}}_a^{i,l}={\mathcal{U}}_a^{i,l}=1\left\}\right|$, where ${\mathcal{S}}_a^{i,l}$ is a-th symbol of the string ${\mathcal{S}}^{i,l}$. The automaton does $\frac{\pi }{4}\sqrt{N/v}$ steps if $|{\phi }_{ones}\rangle =|v\rangle$, where $1\le v\le b$. Initially, $v=1$. The automaton simulates the required number of Grover’s search steps and measures $|\phi \rangle |{\phi }_{ones}\rangle$. If we obtain $|a\rangle |v\rangle$ result, then we reads one more block ${\mathcal{S}}^{i,l}{\mathcal{U}}^{i,l}{\mathcal{Z}}^{i,l}$ and check the equality ${\mathcal{S}}_a^{i,l}={\mathcal{U}}_a^{i,l}=1$. For checking the equality, we store these two bits in $|{\phi }^{\prime }\rangle \otimes |{\phi }^{″}\rangle$ qubits. Then, we measure both qubits and check equality of measurement results.

If the condition ${\mathcal{S}}_a^{i,l}={\mathcal{U}}_a^{i,l}=1$ is right, then process stops. Otherwise, we assign $|2·v\rangle$ to the $|{\phi }_{ones}\rangle$, initialize $|{\phi }^{\prime }\rangle \otimes |{\phi }^{″}\rangle$ by $|0\rangle \otimes |0\rangle$ and repeat the procedure for the new value of v. The probability of correct answer of the algorithm is at least $0.5$, due to [59]. Using the standard success boosting procedure, we can get the error probability $1/b^2$ by repeating the algorithm $2\lceil {log}_{2}b\rceil$ times.

It is easy to see that the size of memory for presented automaton for $MDISJ$ is $O(logd)=O(logn)$ qubits. The error probability is $O\left(\epsilon \right)$ where $0<\epsilon \le 1-{(1-1/d)}^2(1-1/b^2)\le 1-{(1-1/d)}^3=O(1/d)$.    □

If we compare the obtained result with results of [28,44], then we can see that the function and the automaton have several modifications. Using this modification we show that the error probability is $O\left(\frac{1}{d}\right)$. At the same time, similar constructions from [28,44] allow us to obtain only constant error probability.

Using the previous result, we can construct a quantum online streaming algorithm for $\mathtt{onlineDISJ}$ with a smaller competitive ratio compared to [44]. This property is presented in the following theorem.

Theorem 1.

Suppose $k=O(logn)$. We provide a quantum online streaming algorithm Q for ${\mathtt{onlineDISJ}}_{t,k,r,w}$ that is expected c-competitive, uses $O(logn)$ qubits of memory, where $c\le {\mathcal{C}}_Q$. Here ${\mathcal{C}}_Q\to 0.5(r+w)/r$ for $n\to \infty$.

Proof. 

Firstly, we store m into the quantum register $|\mu \rangle$ of $O(logm)=O(logn)$ qubits. We guess $g_1$, we choose it randomly and uniformly from the set $\{0,1\}$. We output the result of guessing as the first output variable $y_1$. After that the automaton (streaming online algorithm) computes $MDIS{J}^m\left(L^1\right)$ and outputs $y_2$ that is $y_2=y_1\oplus MDIS{J}^m\left(L^1\right)$. On the i-th step the automaton computes $MDIS{J}^m\left(L^{i-1}\right)$ and outputs $y_i=y_{i-1}\oplus MDIS{J}^m\left(L^{i-1}\right)$. If $y_1=g_1$ (we guess $g_1$ correctly), then for each other output variable is correct, i.e., $y_i=g_i$ for $i\in \{1,\dots ,k\}$. If $y_1\ne g_1$, then all output variables are incorrect, i.e., $y_i\ne g_i$ for $i\in \{1,\dots ,k\}$. Let ${\mathcal{C}}_Q=\left(0.5{(1-\epsilon )}^{t-1}·(r-w)+w\right)/r$. We can show that $c\le {\mathcal{C}}_Q$ for $\epsilon =O\left(\frac{logn}{n}\right)$. Let us compute a cost of the output for this algorithm if a probability of computing $MDIS{J}^m\left(L^1\right)$ is $\epsilon$. Let us remind that all output variables $y_i$ are split to t blocks. Let us change the cost function. The new one $cos{t}^{\prime }(I,O)$ is such that 1 is the cost of a “right” block, and 0 is the cost of a “wrong” block. Formally,

$$cos{t}^{\prime }(I,O)=\sum _{r=0}^t\prod _{j=r·(T-1)}^{r·T-1}\delta (g_j,y_j),\mathrm{for} T=k/t.$$

The main cost function can be computed by the new one using the following statement $cos{t}^t(I,O)=t·w+cos{t}^{\prime }(I,O)·(r-w)$.

For computing the competitive ratio, we should calculate $𝔼\left[cos{t}^{\prime }(I,O)\right]$.

Let us compute $p_i$ the probability that a block i is a “right” block (costs 1). Let $i=1$. So, if the i-th block is “right”, then for all $T-1$ binary strings $L^j$ inside the block the computation of $MDISJ$ is right and a guess of $y_1$ is right. A probability of this event is $p_1=0.5·{(1-\epsilon )}^{T-1}$.

Let $i>1$. If the i-th block is “right”, then two conditions should be true:

(i)

for all $T-1$ binary strings $L^j$ inside the block, the computation of $MDISJ$ should be right.

(ii)

If we consider a number of errors for computation of $MDISJ$ for preceding $L^j$s plus 1 if $y_1$ is wrong. Then this number should be even.

A probability of the first condition is ${(1-\epsilon )}^{T-1}$. Let us compute the probability of the second condition.

Let $E\left(j\right)$ be the number of errors before computation of $MDIS{J}^m\left(L^j\right)$. Let ${\lambda }_j$ be the number of of errors during computation of $MDISJ$. If $y_1\ne g_1$, then $E\left(j\right)={\lambda }_j+1$, otherwise $E\left(j\right)={\lambda }_j$. Let the probability $F\left(j\right)=Pr\left\{E\right(j)$ mod $2=0\}$. Hence, $Pr\left\{E\right(j)$ mod $2=1\}=1-F(j)$. If we compute $MDIS{J}^m\left(L^j\right)$ with an error, then we have $E(j-1)$ mod $2=1$. If we compute $MDIS{J}^m\left(L^j\right)$ with no error, then we have $E(j-1)$ mod $2=0$. Hence,

$$F\left(j\right)=F(j-1)(1-\epsilon )+(1-F(j-1\left)\right)\epsilon =\epsilon +(1-2\epsilon )F(j-1).$$

Remember that $y_1=g_1$ with probability $\frac{1}{2}$. Hence, $F\left(1\right)=\frac{1}{2}$.

We can compute the probability $F\left(j\right)$ as follows

$$F\left(j\right)=\epsilon +(1-2·\epsilon )·F(j-1)=$$

$$\epsilon +\epsilon ·(1-2·\epsilon )+{(1-2·\epsilon )}^2·F(j-2)=$$

$$\dots =\epsilon +\epsilon ·(1-2·\epsilon )+\dots +\epsilon ·{(1-2·\epsilon )}^{j-2}+{(1-2·\epsilon )}^{j-1}·F(j-j+1)=$$

$$\epsilon ·\sum _{l=0}^{j-2}{(1-2·\epsilon )}^l+{(1-2·\epsilon )}^{j-1}·F\left(1\right)=0.5·(1-{(1-2·\epsilon )}^{j-1})+0.5·{(1-2·\epsilon )}^{j-1}=\frac{1}{2}$$

Hence, $p_i=0.5·{(1-\epsilon )}^{T-1}$. Let us compute the expected cost:

$$𝔼\left[cos{t}^{\prime }(I,A\left(I\right))\right]=\sum _{i=1}^t\left(p_i·1+(1-p_i)·0\right)=\sum _{i=1}^t{p}_i=0.5·{(1-\epsilon )}^{T-1}·t.$$

Therefore, $𝔼\left[cos{t}^t(I,A\left(I\right))\right]=0.5·{(1-\epsilon )}^{T-1}·t(r-w)+tw$.

Let us compute the expected competitive ratio.

$$c\le \frac{0.5·{(1-\epsilon )}^{T-1}·t(r-w)+tw}{tr}=\left(0.5·{(1-\epsilon )}^{T-1}·(r-w)+w\right)/r={\mathcal{C}}_Q.$$

Let us estimate $\underset{n\to \infty }{lim}{\mathcal{C}}_Q$.

$$\frac{w+{(1-\epsilon )}^{k-1}·\frac{1}{2}·(r-w)}{r}\le {\mathcal{C}}_Q\le \frac{w+(1-\epsilon )·\frac{1}{2}·(r-w)}{r}$$

$$\underset{n\to \infty }{lim}\frac{w+{(1-\epsilon )}^{k-1}·\frac{1}{2}·(r-w)}{r}\le \underset{n\to \infty }{lim}{\mathcal{C}}_Q\le \underset{n\to \infty }{lim}\frac{w+(1-\epsilon )·\frac{1}{2}·(r-w)}{r}$$

$$\underset{n\to \infty }{lim}\frac{w+{(1-\frac{logn}{n})}^{logn}·\frac{1}{2}·(r-w)}{r}\le \underset{n\to \infty }{lim}{\mathcal{C}}_Q\le \underset{n\to \infty }{lim}\frac{w+(1-\frac{logn}{n})·\frac{1}{2}·(r-w)}{r}$$

$$\left(0.5(r-w)+w\right)/r\le \underset{n\to \infty }{lim}{\mathcal{C}}_Q\le \left(0.5·(r-w)+w\right)/r$$

Hence, $\underset{n\to \infty }{lim}{\mathcal{C}}_Q=\frac{0.5(r+w)}{r}$.    □

The quantum streaming algorithm with advice is presented in the following theorem.

Theorem 2.

There is the expected c-competitive quantum online streaming algorithm Q with $O(logn)$ qubits of memory and single advice bit for ${\mathtt{onlineDISJ}}_{t,k,r,w}$, where $c\le {\mathcal{C}}_{QA}$ and ${\mathcal{C}}_{QA}\to 1$ for $k=O(logn)$ and $n\to \infty$.

Proof. 

The algorithm is the same as in the Theorem 1, but $y_1$ is obtained as an advice bit. Let us compute $p_i$ similarly as in the proof of the previous theorem. Assume that $\epsilon =O\left(\frac{logn}{n}\right)$ is an error for computing $MDISJ$. Let $E\left(j\right)$ be the number of errors before computation of $MDIS{J}^m\left(L^j\right)$. It is a number of errors for computation of $MDISJ$ for preceding Ls. Let the probability $F\left(j\right)=Pr\left\{E\right(j)$ mod $2=0\}$. Hence, $Pr\left\{E\right(j)$ mod $2=1\}=1-F(j)$. Remember that we obtain $y_1$ as the advice bit; therefore, $F\left(1\right)=1$.

$$F\left(j\right)=\epsilon +(1-2·\epsilon )·F(j-1)=$$

$$\dots =\epsilon ·\sum _{l=0}^{j-2}{(1-2·\epsilon )}^l+{(1-2·\epsilon )}^{j-1}·F\left(1\right)=$$

$$0.5·(1-{(1-2·\epsilon )}^{j-1})+{(1-2·\epsilon )}^{j-1}=0.5·(1+{(1-2\epsilon )}^{j-1}).$$

So, $F\left(j\right)=\frac{{(1-2\epsilon )}^{j-1}+1}{2}$.

The probability $p_i$ of the event is $p_i=0.5·(1+{(1-2\epsilon )}^{(i-1)T+1-1})·{(1-\epsilon )}^{T-1}$.

We can compute the expected value for the cost

$$𝔼\left[cos{t}^{\prime }(I,O)\right]=\sum _{i=1}^t\left(1·p_i+0·(1-p_i)\right)=p_1+\sum _{i=2}^t{p}_i=$$

$${(1-\epsilon )}^{T-1}·\left(1+\sum _{i=2}^t(0.5+0.5{(1-2\epsilon )}^{(i-1)T})\right)=$$

$$0.5{(1-\epsilon )}^{T-1}·\left(t+1+\sum _{i=2}^t{(1-2\epsilon )}^{(i-1)T}\right)$$

Let us compute

$$\underset{n\to \infty }{lim}𝔼\left[cos{t}^{\prime }(I,O)\right]=\underset{n\to \infty }{lim}0.5{(1-\frac{logn}{n})}^{T-1}·\left(t+1+\sum _{i=2}^t{(1-2\frac{logn}{n})}^{(i-1)T}\right)\le$$

$$\le \underset{n\to \infty }{lim}0.5(1-\frac{logn}{n})·\left(t+1+\sum _{i=2}^t(1-2\frac{logn}{n})\right)=0.5(1-0)·(t+1+t-1)=t$$

Therefore, $\underset{n\to \infty }{lim}{\mathcal{C}}_{QA}\le 𝔼\left[cos{t}^{\prime }(I,O)\right]/t=t/t=1$ and ${\mathcal{C}}_{QA}\ge 1$. Hence, we obtain the claim of the theorem.    □

3.2. Bounds for Classical Automata for the Online Disjointness Problem

We use some results from the communication complexity theory. We briefly remind the reader of the model (see [60]). There are two players, Alice and Bob. They want to compute a Boolean function $f\left(X\right)$. Alice has variables from a set $X_A\subset X$ and Bob variables from a set $X\backslash X_A$. Alice starts computation and sends a message to Bob. Then, Bob continues and sends a message to Alice, etc. The player who can compute $f\left(X\right)$ returns an answer. Alice and Bob can use a probabilistic mechanism. The probabilistic communication complexity is the total number of bits in all messages. It is known that

Lemma 3

([42]). The probabilistic communication complexity of the Boolean function $DISJ(\mathcal{S},\mathcal{U})$ is $\Omega \left(b\right)$, where $\mathcal{S},\mathcal{U}\in {\{0,1\}}^b$, Alice has x and Bob has y.

Using this result, we can show the following one.

Lemma 4.

Suppose, we have a promise that properties 1–5 and 7 of $MDIS{J}^m\left(L^i\right)$ are correct. Suppose the length of the string ${\mathcal{S}}^{i,1}$ is $b=|{\mathcal{S}}^{i,1}|$ and the integer m such that $m<b$. Then, there is no bounded error probabilistic log-bounded automata for $MDIS{J}^m\left(L^i\right)$ that uses $o(b/m)$ bits of memory.

Proof. 

Suppose that there is a probabilistic automaton R for $MDIS{J}^m\left(L^i\right)$ with $d=o(b/m)$ bits of memory. Then, we can simulate the work of R by a probabilistic communication protocol such that Alice knows ${\mathcal{S}}^{i,1}$ and Bob knows ${\mathcal{U}}^{i,1}$. Each player simulates R on his part of the input. Then he/she sends a state of the memory of R to the opposite player. See more details on an emulation of stream processing models by communication protocols, for example, in [37,51,61]. Therefore, the communication protocol uses $d·m=o\left(b\right)$ bits of memory for computing $DISJ({\mathcal{S}}^{i,1},{\mathcal{U}}^{i,1})$. This fact contradicts with Lemma 3.    □

Using this result, we can show that for probabilistic and deterministic automata, the ${\mathtt{onlineDISJ}}_{t,k,r,w}$ problem is hard.

Theorem 3.

There is no c-competitive deterministic online streaming algorithm for ${\mathtt{onlineDISJ}}_{t,k,r,w}$ that uses $o\left(\sqrt{n}\right)$ bits of memory, where $c<\frac{w}{r}$, $k=O(logn)$.

Proof. 

Let us consider any online streaming algorithm A for the ${\mathtt{onlineDISJ}}_{t,k,r,w}$ problem such that the size of memory is at most $o\left(\sqrt{n}\right)$ bits. Assume, the algorithm A returns $y_1$ as the first output variable. Let us prove that there are two parts of the input $L_0^1,L_1^1\in {\{0,1\}}^d$ such that A returns the same value $y_2$ for both, but $MDISJ\left(L_0^1\right)=0,MDISJ\left(L_0^1\right)=1$.

Assume that there is no such triple $(y_2,L_0^1,L_1^1)$. Then it means that we can construct an automaton $A^{\prime }$ that uses $o\left(\sqrt{n}\right)$ bits of memory and has the following property: $A^{\prime }\left(L^{1^{\prime }}\right)=A^{\prime }\left(L^{1^{″}}\right)$ iff $f\left(L^{1^{\prime }}\right)=f\left(L^{1^{″}}\right)$, for any $L^{1^{\prime }},L^{1^{″}}\in {\{0,1\}}^d$. The automaton $A^{\prime }$ simulates A. Hence, the automaton $A^{\prime }$ computes the function $MDISJ$ or the function $\neg MDISJ$. If it computes the function $\neg MDISJ$, then we can provide an automaton $A^{″}$ such that $A^{″}\left(L^1\right)=\neg A^{\prime }\left(L^1\right)$. This statement contradicts with the main claim of the theorem. Similarly, we can prove that we have analogous triples $(y_{i+1},L_0^i,L_1^i)$ for $i\in \{2,\dots ,k\}$.

Let us choose ${\sigma }_i=y_i\oplus 1\oplus {⨁}_{j=i+1}^k{\sigma }_j$, for $i\in \{1,\dots ,k\}$.

Let $I_A$ be such that $L^i=L_{{\sigma }_i}^i$. An optimal offline solution is $(g_1,\dots ,g_k)$ where $g_i={⨁}_{j=i}^k{\sigma }_j$.

Let us prove that $g_i\ne y_i$ for each $i\in \{1,\dots ,k\}$. We have ${\sigma }_i=y_i\oplus 1\oplus {⨁}_{j=i+1}^k{\sigma }_j$, hence $y_i=1\oplus {\sigma }_i\oplus {⨁}_{j=i+1}^k{\sigma }_j=1\oplus {⨁}_{j=i}^k{\sigma }_j=1\oplus g_i$, so we obtain $y_i=\neg g_i$.

Therefore, all output variables are “wrong” and the cost is $cos{t}^t(I_A,A\left(I_A\right))=tw$. Hence, the competitive ratio c more than $\frac{tw}{tr}=\frac{w}{r}$.    □

Theorem 4.

There is no expected c-competitive randomized online streaming algorithm for ${\mathtt{onlineDISJ}}_{t,k,r,w}$ that uses $o\left(\sqrt{n}\right)$ bits of memory, where $k=o(logn)$ and $c<\frac{1}{2^T}+(1-\frac{1}{2^T})\frac{w}{r}$, $T=\frac{k}{t}$.

Proof. 

We can show that a bounded error randomized online streaming algorithm A cannot compute $y_i$. We prove the claim using the idea from the proof of Theorem 3. It is easy to see that the only option for an algorithm is to guess the value of $y_i$ and randomly uniformly choose it. Using this strategy, we can obtain the required competitive ratio. If we want to get a cost r for a block, then it should guess all output bits of the block. So, the cost of the i-th block is $c_i=w(1-\frac{1}{2^T})+\frac{r}{2^T}$. Hence, $cos{t}^t(I_A,A\left(I_A\right))=(w(1-\frac{1}{2^T})+\frac{r}{2^T})·t$. Therefore, the algorithm A is c competitive in expectation, for $c\ge t·((1-\frac{1}{2^T})w+\frac{r}{2^T})/\left(tr\right)=2^{-T}+(1-2^{-T})w/r$.    □

For proofs of properties for classical models with advice (Theorems 5 and 6), we show that if the model does not have enough memory, then the problem can be interpreted as the “String Guessing, Unknown History” ($2-SQUH$) from [50].

The following result for the $2-SQUH$ is known:

Lemma 5

([50]). Consider an input string of length k for $2-SGUH$, for some positive integer k. Any online algorithm that is correct in more than $\alpha k$ characters, for $0.5\le \alpha <1$, needs to read at least $\left(1+(1-\alpha ){log}_2(1-\alpha )+\alpha {log}_2\alpha \right)k$ advice bits.

Using above result we show complexity of the ${\mathtt{onlineDISJ}}_{t,k,r,w}$ problem.

Theorem 5.

There is no c-competitive deterministic online streaming algorithm for ${\mathtt{onlineDISJ}}_{t,k,r,w}$ that uses $o\left(\sqrt{n}\right)$ bits of memory and b advice bits, where $c<\frac{w(t-h)+rh}{tr}$, $T=\frac{k}{t},h=\lfloor \frac{v}{T}\rfloor$, v is such that $b=(\frac{v}{k}{log}_2\frac{v}{k}+(1-\frac{v}{k}){log}_2(1-\frac{v}{k})+1)k$, $\frac{k}{2}\le v<k$ and $k=o(logn)$.

Proof. 

We start with a proof of the following claim. For any online algorithm for $MDISJ$ that obtains b advice bits, we can suggest an input such that the algorithm has at least $k-b$ errors in computation. We prove it by induction.

Firstly, let us prove the claim for $b=k$. Then the adviser can send $(g_1,\dots ,g_k)$, where $g_i={⨁}_{j=i}^{k}MDIS{J}^m\left(L^j\right)$. Using this advise we return all correct output variables $y_1,\dots ,y_k$.

Secondly, let us show the correctness of the claim in a case of $b=0$. Therefore, there is no advice at all. So, it is exactly the Theorem 3 situation.

Thirdly, let us show the correctness of the claim in a case of $b\notin \{0,k\}$. Assume that the claim is correct for a pair $(b^{″},k^{\prime })$ such that $b^{\prime }\le b$, $k^{\prime }\le k$ and at least one of these inequalities is strict. Let us consider the computation process of the $MDIS{J}^m\left(L^1\right)$ function.

Assume that there is an input $L^1\in {\{0,1\}}^d$ such that there is no way to compute an output with bounded error. Then using the input, we obtain the case for $k-1$ input variables and b advice bits. So, the computation of $MDISJ$ for $k-b-1$ binary strings $L^i$ is incorrect, and the computation for $L^1$ is incorrect also.

Assume that the algorithm computes an output for $MDIS{J}^m\left(L^1\right)$ with a bounded error always. So we can describe the process of communication with the adviser in the following way: the adviser separates all possible inputs into $2^b$ non-overlapping groups $G_1,\dots ,G_{2^b}$. After that, he sends a group number containing current input to the algorithm. Then, the algorithm A processes the input with the knowledge that an input can be only from this group.

Let us consider three sets of groups:

• $I_0=\{G_i:\forall \sigma \in {\{0,1\}}^d$ such that $\sigma$ is $L^1$ and $MDIS{J}^m\left(\sigma \right)=0\}$,
• $I_1=\{G_i:\forall \sigma \in {\{0,1\}}^{m_1}$ such that $\sigma$ is $L^1$ and $MDIS{J}^m\left(\sigma \right)=1\}$,
• $I_{10}=\{G_1,\dots ,G_{2^b}\}\backslash (I_1\cup I_0)$.

Let $|I_a|\ne 0$, for some $a\in \{0,1\}$. If $|I_a|\le 2^{b-1}$, then as ${\mathcal{Z}}^1$ we take any input from any group $G\in I_a$. Hence we have at most $2^{b-1}$ possible groups for the adviser that distinguish next $L^i$s. We can say that the adviser can encode them using $b-1$ bits. Therefore, we get the situation for $b-1$ advice bits and $k-1$ binary strings $L^i$. The claim is true for this situation. If $|I_a|>2^{b-1}$, then we pick an input ${\mathcal{S}}^1$ from any group $G\notin I_a$. Therefore, there are at most $2^{b-1}$ possible groups for the adviser and the same situation. For this case, the claim is correct.

Suppose the size of sets $I_0$ and $I_1$ is $|I_0|=|I_1|=0$. Assume that the algorithm solves the problem, and the memory size is $s^{\prime }$, where $s^{\prime }<s-b$. The automaton B with the following structure can simulate the algorithm’s work on $L^1$. The automaton B has two memory registers: a register $M_1$ of b bits and a register $M_2$ of $s^{\prime }$ bits. We assume that $M_1$ is initialized by advice bits. After that, the automaton B invokes A depending on the value of advice bits stored in $M_1$. The memory size of B is $s^{\prime }+b<s$ and it computes $MDISJ$ by simulating A. We obtain a contradiction with the theorem’s claim. Hence, transferring the answer of $MDIS{J}^m\left(L^1\right)$ as an advice bit is the only way to compute the result of the function. So, we have a situation for $k-1$ binary strings $L^i$ and $b-1$ advice bits.

So, it means that for the algorithm, the problem is the same as the String Guessing Problem with Unknown History ($2-SGUH$) from [50].

Due to Lemma 5, for obtaining v right answers $y_i$, we need $b=\left(1+(1-\frac{v}{k}){log}_2(1-\frac{v}{k}\right)$$\left.+\frac{v}{k}{log}_2\frac{v}{k}\right)k$ advice bits.

Because of the cost function properties, the best case for the algorithm is getting all $y_i$s of a block. Therefore, the algorithm can obtain advice bits on $h=\lfloor \frac{v}{T}\rfloor$ full blocks, for $T=\frac{k}{t}$. In that case, the cost of these blocks is r. Each of the rest blocks has at least one “wrong” output variable. So, such a block costs w. Hence, we suggest the input such that the corresponding output costs

$$\lfloor v/T\rfloor ·r+(t-\lfloor v/T\rfloor )w,\mathrm{for} b=\left(1+(1-\frac{v}{k}){log}_2(1-\frac{v}{k})+\frac{v}{k}{log}_2\frac{v}{k}\right)k.$$

Let us compute the competitive ratio c

$$c\ge \frac{\lfloor v/T\rfloor ·r+(t-\lfloor v/T\rfloor )w}{tr},\mathrm{for} b=\left(1+(1-\frac{v}{k}){log}_2(1-\frac{v}{k})+\frac{v}{k}{log}_2\frac{v}{k}\right)k.$$

   □

Next, we show an analog of Theorem 5 for randomized case. Ideas from [62,63,64,65] are the basis for the proof of the following theorem.

Theorem 6.

Suppose $s=o\left(\sqrt{n}\right)$. Any randomized online streaming algorithm A using b advice bits, less than $s-b$ bits of memory, and solving ${\mathtt{onlineDISJ}}_{t,k,r,w}$, has the expected competitive ratio

$$c\ge \frac{hr+{\delta }_u·(2^{u-T}r+(1-2^{u-T})w)+(t-h-{\delta }_u)(2^{-T}r+(1-2^{-T})w)}{tr},$$

for $h=\lfloor \frac{v}{T}\rfloor ,T=\frac{k}{t},u=v-hz$, v is such that $b=\left(1+(1-\frac{v}{k}){log}_2(1-\frac{v}{k})+\frac{v}{k}{log}_2\frac{v}{k}\right)k$, $\frac{k}{2}\le v<k$ and $k=o(logn)$.

Proof. 

Let us suggest the proof that is based on the proof of Theorem 5. Suppose that an online algorithm obtains b advice bits. Then, we can suggest an input such that on this input, the computation of $MDIS{J}^m\left(L^i\right)$ has an error for at least $k-b$ strings $L^i$. The claim can be proven by the way similar to the proof of Theorem 5. At the same time, we use the probabilistic automaton B to simulate A, and the part of the automaton that uses memory $M_2$ is probabilistic.

Therefore, for the algorithm, our problem is equivalent to the String Guessing Problem with Unknown History ($2-SGUH$) from [50].

Hence, if we want to obtain v right answers for $y_i$ output variables, then we should use

$$b=k·\left(\frac{v}{k}{log}_2\frac{v}{k}+(1-\frac{v}{k}){log}_2(1-\frac{v}{k})+1\right).$$

We can show that if we do not know $y_i$ from the adviser, then we cannot compute the output variable with bounded error. Hence, the only way to obtain the variables is randomly uniformly choosing them. We can apply the proof technique as in Theorem 4. We use the same approach for all segments between “known” output variables.    □

4. Conclusions

We provide an expected ${\mathcal{C}}_Q$-competitive quantum online streaming algorithm with no advice and an expected ${\mathcal{C}}_{QA}$-competitive quantum online streaming algorithm with a single advice bit. They are such that ${\mathcal{C}}_Q\to \frac{r+w}{2r}$ and ${\mathcal{C}}_{QA}\to 1$ for $n\to \infty$. At the same time, any classical algorithm with a logarithmic size of memory is $({\mathcal{C}}_Q+{\gamma }_1)$-competitive for a model with no advice and $({\mathcal{C}}_{QA}+{\gamma }_2)$-competitive for a model with $o(logn)$ advice bits, where ${\gamma }_1,{\gamma }_2>0$.