# Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear
Sketches

Amit Chakrabarti Department of Computer Science, Dartmouth College. Email:
{ac<EMAIL_ADDRESS>Work supported in part by NSF under award
CCF-1907738. Prantar Ghosh Justin Thaler Department of Computer Science,
Georgetown University. Email<EMAIL_ADDRESS>Work supported by
NSF SPX award CCF-1918989, and NSF CAREER award CCF-1845125. Parts of this
work were performed while visiting the Simons Institute for the Theory of
Computing.

###### Abstract

We study graph computations in an enhanced data streaming setting, where a
space-bounded client reading the edge stream of a massive graph may delegate
some of its work to a cloud service. We seek algorithms that allow the client
to _verify_ a purported _proof_ sent by the cloud service that the work done
in the cloud is correct. A line of work starting with Chakrabarti et al.
(ICALP 2009) has provided such algorithms, which we call _schemes_ , for
several statistical and graph-theoretic problems, many of which exhibit a
tradeoff between the length of the proof and the space used by the streaming
verifier.

This work designs new schemes for a number of basic graph problems—including
triangle counting, maximum matching, topological sorting, and single-source
shortest paths—where past work had either failed to obtain smooth tradeoffs
between these two key complexity measures or only obtained suboptimal
tradeoffs. Our key innovation is having the verifier compute certain
_nonlinear_ sketches of the input stream, leading to either new or improved
tradeoffs. In many cases, our schemes in fact provide optimal tradeoffs up to
logarithmic factors.

Specifically, for most graph problems that we study, it is known that the
product of the verifier’s space cost $v$ and the proof length $h$ must be at
least $\Omega(n^{2})$ for $n$-vertex graphs. However, matching upper bounds
are only known for a handful of settings of $h$ and $v$ on the curve $h\cdot
v=\tilde{\Theta}(n^{2})$. For example, for counting triangles and maximum
matching, schemes with costs lying on this curve are only known for
$(h=\tilde{O}(n^{2}),v=\tilde{O}(1))$, $(h=\tilde{O}(n),v=\tilde{O}(n))$, and
the trivial $(h=\tilde{O}(1),v=\tilde{O}(n^{2}))$. A major message of this
work is that by exploiting nonlinear sketches, a significant “portion” of
costs on the tradeoff curve $h\cdot v=n^{2}$ can be achieved.

##  1 Introduction

It is far easier to verify a proof than to find one. This intuitively clear
fact has been given precise meanings in several settings, leading to such
landmark results as the IP $=$ PSPACE [Sha92] and PCP Theorems [ALM+98, AS98].
There is a growing body of work on results of this flavor for space-efficient
computations on large data streams [Tha16a]. In this setting, a space-bounded
client (henceforth named Verifier) that can only process inputs in the
restrictive data streaming setting has access to a computationally powerful
entity (henceforth named Prover), such as cloud computing service, that has no
such space limitations. As past work has shown, many fundamental problems that
are intractable in the plain data-streaming model—in the sense that they
cannot be solved using sublinear space—do admit nontrivial solutions in this
Verifier/Prover model, without Verifier having to trust Prover blindly.

An algorithm in this model specifies a protocol to be followed by Verifier and
Prover so that the former may compute some function $f(\sigma)$ of the input
stream $\sigma$. Prover, by performing the specified actions honestly,
convinces Verifier to output the correct value $f(\sigma)$. However, if Prover
fails to follow the protocol, whether out of malice or error (modeling
hardware, software, or network faults in the cloud service), then Verifier is
highly likely to detect this and reject. Past work has considered a few
different instances of this setup, such as (a) annotated data streaming
algorithms [CCMT14]—also called online schemes—where the parties read $\sigma$
together and the protocol consists of Prover streaming a “help message”
(a.k.a. proof) to Verifier either during stream processing and/or at the end;
(b) prescient schemes [CCGT14, CCMT14], which are a variant of the above where
Prover knows all of $\sigma$ before Verifier sees it; (c) streaming
interactive proofs (SIPs) [CCM+15, CTY11], where Verifier and Prover engage in
multiple rounds of communication.

This work focuses on the first and arguably best-motivated of these models,
namely, online schemes. We simply call them schemes. We give new and improved
schemes for several graph-theoretic problems, including triangle counting,
maximum matching, topological sorting, and shortest paths. In all cases, the
input is a huge $n$-vertex graph $G$ given as a stream $\sigma$ of edge
insertions and/or deletions. While most of our problems have been studied
before, we give schemes that (a) have better complexity parameters, in some
cases achieving optimality, and (b) use cleverer algebraic encodings of the
relevant combinatorial problems, often exploiting the ability of a streaming
algorithm to compute nonlinear sketches.

###  1.1 Setup, Terminology, and Motivation

We formalize the setup described above. A scheme for a function $f$ specifies
three things: (i) a space-bounded data streaming algorithm used by Verifier to
process the input $\sigma$ and compute a summary $\mathcal{V}_{R}(\sigma)$,
using random coins $R$; (ii) a help function used by Prover to send a message
$\mathcal{H}(\sigma)$ to Verifier as a “proof stream” after the input stream
ends;111A more general (though seldom used) model allows Prover to send help
messages after each data item in $\sigma$. and (iii) an output algorithm
$\operatorname{out}_{R}(\mathcal{V}_{R}(\sigma),\mathcal{H}(\sigma))$
capturing Verifier’s work during and after the proof stream, which produces
values in range$(f)\cup\\{\bot\\}$, where an output of $\bot$ indicates
“reject.” If $\mathcal{V}_{R}$ and $\operatorname{out}_{R}$ run in $O(v)$ bits
of space and $\mathcal{H}$ provides $O(h)$ bits of help, then this scheme is
called an $(h,v)$-scheme. A scheme is interesting if we can use $h>0$ to
achieve a value of $v$ asymptotically smaller than what is feasible or known
for a basic streaming algorithm, where $h=0$. A scheme is said to have

  * •

completeness error $\varepsilon_{c}$ if
$\forall\sigma\,\exists\mathcal{H}:\Pr_{R}[\operatorname{out}_{R}(\mathcal{V}_{R}(\sigma),\mathcal{H}(\sigma))=f(\sigma)]\geqslant
1-\varepsilon_{c}$;

  * •

soundness error $\varepsilon_{s}$ if
$\forall\sigma,\mathcal{H}^{\prime}:\Pr_{R}[\operatorname{out}_{R}(\mathcal{V}_{R}(\sigma),\mathcal{H}^{\prime}(\sigma))\notin\\{f(\sigma),\bot\\}]\leqslant\varepsilon_{s}$.

In designing schemes, we will aim for $\varepsilon_{s}\leqslant 1/3$, which
can be reduced further via parallel repetition in standard ways. We will also
achieve perfect completeness, i.e., $\varepsilon_{c}=0$. For an $(h,v)$-scheme
we refer to $h$ as its hcost (short for “help cost”) and $v$ as its vcost
(“verification cost”). We use the notation $[h,v]$-scheme as a shorthand for
an $(\tilde{O}(h),\tilde{O}(v))$-scheme.222The notation $\tilde{O}(\cdot)$
hides factors polynomial in $\log n$.

It is intuitive that the parameters $h$ and $v$ are in tension, suggesting
that they can be traded off against one another. Most of our algorithms do
obtain such tradeoffs. We emphasize that actually obtaining a smooth tradeoff
for large ranges of $h$ and $v$ values is not automatic: indeed, an important
contribution of this work is to obtain such tradeoffs for problems where past
work gave comparable results only for specific settings of $h$ and $v$.

When studying the results discussed below, it is useful to keep a few cost
regimes in mind. We focus on graph problems on $n$-vertex inputs. An
$(h,v)$-scheme for such a problem is sublinear if $h=o(n^{2})$ and
$v=o(n^{2})$; frugal if it is sublinear and achieves the stronger guarantee
$v=o(n)$; and laconic if it is sublinear and achieves the stronger guarantee
$h=o(n)$.

Many graph problems are intractable in the basic one-pass streaming model,
meaning that they provably require $\Omega(n^{2})$ space. Past work [CCMT14]
implies that any $(h,v)$-scheme for such a problem must have
$hv=\Omega(n^{2})$. Thus, an $[h,v]$-scheme with $hv=O(n^{2})$ for an
intractable problem has achieved an optimal tradeoff, up to logarithmic
factors. All of the problems we consider in this paper (except for counting
connected components) are intractable for dense graphs (i.e., graphs with
$\Omega(n^{2})$ edges).

Frugal schemes are important when Verifier is so starved for space that it
cannot afford to store even a constant fraction of the vertices. They are also
very interesting from a theoretical standpoint, since even “easy” graph
problems require at least $\Omega(n)$ space in the basic streaming model. On
the other hand, laconic schemes are naturally motivated by settings where
Verifier does not have streaming access to the proof and has to store it in
full. Consider for example a retail client that uploads transactions to the
cloud as they occur. It makes sense to have uploaded even terabytes of
information in total over a long period of time: days, months, or years.
However, it might not be reasonable for the cloud to transfer a proof
consisting of, say, tens of gigabytes to the client. From a theoretical
standpoint, in solving an intractable problem, if Verifier has to store the
proof, there is no reason to ever try to reduce vcost to $o(n)$, since hcost
will then blow up to $\omega(n)$.

###  1.2 Problems, Results, and Comparisons with Related Work

Throughout, the input graph $G$ will be on the fixed vertex set
$V=[n]:=\\{1,\ldots,n\\}$ and will have $m$ edges. Many results will be stated
in terms of tunable parameters $t,s\in\mathbb{Z}^{+}$ that must satisfy
$ts\geqslant n$. Since bounds are asymptotic, this condition can be read as
$ts=n$.

Problem | Scheme | Tradeoff | Reference
---|---|---|---
| $[h,v];hv=n^{3}$ | Suboptimal | [CCMT14]
| $[n^{2},1]$ | Optimal | [CCMT14]
| $[n,n]$ | Optimal | [Tha16b]
|  $[t^{3},s^{2}]$; $ts=n$ | Suboptimal | [CG19]
TriangleCount |  $[nt^{2},s]$; $ts=n$ |  | Theorem 2.1
|  $[t,ns]$; $ts=n$ | Optimal | Theorem 2.2
| $[mn/\sqrt{v},~{}v]$ | Suboptimal | [CCGT14]
|  $[m+h,v]$; $hv=n^{2}$ |  | Theorem 4.5
TriangleCount-Adj |  $[h,v]$; $hv=n^{2}$ |  | Theorem 4.6
| $[m,1]$ | Optimal | [CMT13]
| $[n,n]$ | Optimal | [Tha16b]
MaxMatching |  $[t^{3},s^{2}]$; $ts=n$ | Suboptimal | [CG19]
|  $[nt,s]$; $ts=n$ | Optimal | Theorem 4.1
|  $[\alpha^{\prime}+h,v]$; $hv=n^{2}$ |  | Theorem 4.4
MIS |  $[nt,s]$; $ts=n$ | Optimal | Theorem 4.7
Acyclicity/TopoSort | $[m,1]$ | Optimal | [CMT13]
|  $[nt,s]$; $ts=n$ | Optimal |  Theorem 4.8; Corollary 4.9
|  $[Dnt,s]$; $ts=n$ |  | [CMT13]
st-ShortestPath | $[Kn,n]$ |  | [CG19]
|  $[Knt,s]$; $ts=n$ |  | Corollary 5.3
Unweighted SSSP |  $[Dnt,s]$; $ts=n$ |  | Theorem 5.2
| $[m+n,1]$ | Optimal | [CMT13]
Weighted SSSP | $[DWn,n]$ |  | Theorem 5.4
| $[Dn,Wn]$ |  | Theorem 5.5

Table 1: Summary of results on the problems considered in this paper. A scheme
is deemed _optimal_ if it has help cost at most $h$ and space cost at most $v$
for at least one pair $h,v$ such that $h\cdot v\leqslant\tilde{O}(L)$, whereas
it is known that _any_ $(h,v)$ scheme that applies to all graphs requires
$h\cdot v\geqslant\Omega(L)$. A blank space in the _Tradeoff_ column indicates
that it remains open whether the scheme can be strictly improved. Here,
$\alpha^{\prime}$ is the size of a maximum matching in the input graph, $K$ is
the length of a shortest $v_{s}$–$v_{t}$ path, $D$ is the maximum distance
from the source to the any other reachable vertex, and $W$ is the maximum
weight of an edge.

Triangle Counting. Our starting point is the triangle counting problem
(henceforth, TriangleCount), studied heavily in past work on graph streaming
[BKS02, BC17, BFL+06, JSP13, JG05, KMSS12, MVV16, Tha16b]. Given a multigraph
$G$ as a dynamic stream (i.e., insertions and deletions), the goal is to
compute $T$, the number of triangles in $G$. The exact counting version
studied in this paper is an intractable problem in the sense of Section 1.1:
it requires $\Omega(n^{2})$ space in basic streaming.

As noted in Table 1, we give several new algorithms for TriangleCount. Our
$[nt^{2},s]$-scheme improves upon the best known frugal scheme for the
problem: for a fixed hcost $h\geqslant n$, it improves the vcost from
$v^{4/3}$ to $v$, where $v=n^{3/2}/\sqrt{h}$, and for a fixed vcost
$v\leqslant n$, it improves the hcost from $n^{3}/v^{3/2}$ to $n^{3}/v^{2}$.
Our $[t,ns]$-scheme is not only the first laconic scheme for the problem but
also achieves smooth optimal tradeoff in its parameter range; thus, it settles
the complexity of the problem in the laconic regime. The $[m+h,v]$-scheme
whenever $hv=n^{2}$ generalizes the $[n^{2},1]$-scheme from prior work for any
$m$-edge graph (for the setting $h=m$ and $v=n^{2}/m$) and is interesting in
the frugal regime for sparse graphs.

The problem has also been studied in the adjacency-list model (call it
TriangleCount-Adj) [BFL+06, KMPV19, KMPT12, MVV16], where the stream presents
the full neighbor list for each vertex contiguously. We give an $[h,v]$-scheme
for any $hv=n^{2}$ for TriangleCount-Adj (again, exact counting). In basic
streaming, there is no nontrivial algorithm for computing $T$ exactly, or even
approximately when $T$ is small; in fact, under a long-standing conjecture in
communication complexity, these problems require $\Omega(m)$ space [KMPV19].

Maximum Matching. There is a recent and ongoing flurry of activity on
streaming algorithms for MaxMatching, the problem of computing the cardinality
$\alpha^{\prime}(G)$ of a maximum-sized matching333The notation
$\alpha^{\prime}(G)$ is by analogy with $\alpha(G)$, which denotes the
cardinality of a maximum independent set of vertices. It can be found, e.g.,
in the textbook by West [Wes01]. in $G$ [AKL17, CK15, FKM+08, GKK12, Kap13,
McG05, FHM+20, KMNT20]. The exact version of the problem (which is what we
study here) is intractable. For the special case of detecting whether a
bipartite graph has a perfect matching, there is a frugal $[nt,s]$-scheme
[CCMT14], which achieves optimal tradeoff. See Table 1 for previous results
for the general problem.

In this work, we give (i) the first optimal frugal $[nt,s]$-scheme for the
general MaxMatching problem, settling its complexity in the frugal regime, and
(ii) an $[\alpha^{\prime}+h,v]$-scheme whenever $hv=n^{2}$, which yields a
laconic scheme provided $\alpha^{\prime}(G)=o(n)$. Obtaining a fully general
laconic scheme remains an interesting open problem and we suspect that it will
require a breakthrough in exploiting the problem’s combinatorial structure.

Further Graph Problems and a Common Framework. We obtain new schemes for the
MIS problem, which asks for an inclusion-wise maximal independent set of
vertices; the Acyclicity problem, which asks whether the input digraph is
acyclic; and the TopoSort problem, which asks for a vertex ordering of the
input DAG that orients all edges “forwards.” In each case, we give an
$[nt,s]$-scheme. Recent results show that MIS [ACK19, CDK19] and TopoSort
[CGMV20] are intractable in basic streaming, so our schemes are optimal in the
frugal regime. Importantly, these schemes, the frugal MaxMatching scheme, and
two of the TriangleCount schemes all fit a common framework: they boil the
problem down to counting the number of edges in one or more induced subgraphs
of the input graph. Our scheme for this InducedEdgeCount problem could be a
useful technical result for future work.

Shortest Paths. The single-source shortest path (SSSP) problem is perhaps the
most basic problem in classic graph algorithms. In the streaming setting, even
the special case of undirected $v_{s}$–$v_{t}$ connectivity in constant-
diameter graphs is intractable [FKM+08]. As Table 1 shows, our
$[Dnt,s]$-scheme for unweighted SSSP (where $D$ is the maximum distance from
the source vertex $v_{s}$ to any vertex reachable from it) generalizes the
result of Cormode et al. [CMT13] from st-ShortestPath to SSSP. Again, as a
corollary, we obtain a $[Knt,s]$-scheme for st-ShortestPath, where $K$ is the
length of a shortest $v_{s}$–$v_{t}$ path. This result generalizes the
$[Kn,n]$-scheme of Chakrabarti and Ghosh [CG19] and improves upon the
$[Dnt,s]$-scheme of Cormode et al. [CMT13], since $K$ can be arbitrarily
smaller than $D$. The schemes for the weighted version are interesting for
small $D$ and $W$, where $W$ is the maximum weight of any edge.

###  1.3 Other Related Works

Abdullah et al. [ADRV16] studied the TriangleCount and MaxMatching problems in
the stronger SIP model that allows rounds of interaction between Prover and
Verifier. For TriangleCount, they gave a $(\log^{2}n,\log^{2}n)$-SIP using
$\log n$ rounds of interaction. They also designed an $(n^{1/\gamma}\log
n,\log n)$-SIP with $\gamma=O(1)$ rounds. For the weighted MaxMatching
problem, they gave a $(\rho+n^{1/\gamma^{\prime}}\log n,\log n)$-SIP using
$\gamma$ rounds of interaction, where $\gamma^{\prime}$ is a linear function
of $\gamma$, and $\rho$ is the weight of an optimal matching.

Early works on the concept of annotated streams include Tucker et al. [TMD+05]
and Yi et al. [YLH+08], who studied stream punctuations and stream outsourcing
respectively. Motivated by these works, Chakrabarti et al. [CCMT14] then
formalised the model theoretically as the annotated streaming model and gave
schemes for statistical streaming problems including frequency moments and
heavy hitters, along with some basic results for graph problems. This non-
interactive model was subsequently studied by multiple works including Klauck
and Prakash [KP13], Cormode et al. [CMT13], and Chakrabarti et al. [CCGT14].
Subsequent works considered generalized versions of the model, allowing rounds
of interaction. These include Arthur-Merlin streaming protocols of Gur and Raz
[GR13] and the streaming interactive proofs (SIP) of Cormode et al. [CTY11].
Chakrabarti et al. [CCM+15] and Abdullah et al. [ADRV16] further studied this
generalized setting. We refer to the expository article of Thaler [Tha16a] for
a more detailed survey of this area.

###  1.4 Our Techniques

Sum-Check and Polynomial Encodings. As with much prior work in this area (and
probabilistic proof systems more generally), our schemes are variants of the
famous _sum-check protocol_ of Lund et al. [LFKN92]. Specialized to our (non-
interactive) schemes, this protocol allows Verifier to make Prover honestly
compute $\sum_{x\in\mathcal{X}}g(x)$ for some low-degree polynomial $g(X)$
derived from the input data and some designated set $\mathcal{X}$. Verifier
has no space to compute $g$ explicitly, nor all values
$\langle{g(x):x\in\mathcal{X}}\rangle$, but he can afford to evaluate $g(r)$
at a random point $r$. The Prover steps in by explicitly providing
$\hat{g}(X)$, a polynomial claimed to equal $g(X)$: this is cheap since $g$
has low degree. Verifier can be convinced of this claim by checking that
$\hat{g}(r)=g(r)$.

Hence, the main challenge in applying the sum-check technique is to find a way
to encode the data stream problem’s output as the sum of the evaluations of a
low-degree polynomial $g$ so that Verifier can, in small space, evaluate $g$
at a random point $r$.

Sketches: Linearity and Beyond. A streaming Verifier evaluates $g(r)$ by
suitably summarizing the input in a sketch. Viewing the input as updates to a
data vector $\mathbf{f}=(f_{1},\ldots,f_{N})$, such a sketch $\mathbf{v}$ is
linear if $\mathbf{v}=S\mathbf{f}$ for some matrix $S\in\mathbb{F}^{v\times
N}$, for some field $\mathbb{F}$.444This field is finite in the streaming
verification literature, whereas traditional data streaming uses $\mathbb{R}$.
Typically, $S$ is implicit in the sketching algorithm and enables stream
processing in $\tilde{O}(v)$ space by translating a stream update
$f_{i}\leftarrow f_{i}+\Delta$ into the sketch update
$\mathbf{v}\leftarrow\mathbf{v}+\Delta S\mathbf{e}_{i}$, where
$\mathbf{e}_{i}$ is the $i$th standard basis vector. In essentially all prior
works on stream verification, the polynomial $g$ was such that $g(r)$ could be
derived from such a linear sketch $\mathbf{v}$.

There is one exception: Thaler [Tha16b] introduced an optimal $[n,n]$-scheme
for TriangleCount in which Verifier computes a nonlinear sketch.555Simliar
nonlinearity was used recently in the more powerful model of $2$-pass schemes
[CG19]. Roughly speaking, the verifier in Thaler’s protocol maintains two
$n$-dimensional linear sketches $\mathbf{v}^{(1)}$ and $\mathbf{v}^{(2)}$,
plus a value $C$ that is _not_ a linear function of the input stream but
instead depends quadratically on $\mathbf{v}^{(1)}$ and $\mathbf{v}^{(2)}$.
Moreover, the $j$th increment to $C$ uses information that is available while
processing the $j$th stream update, but not after the stream is gone. This is
in contrast to linear sketches themselves, where the $j$th sketch update
depends only on the $j$th stream update and no others.

The Shaping Technique. Another ubiquitous idea in streaming verification is
the shaping technique, which transforms a data vector into a multidimensional
array. This trick realizes $g(X)$ as a summation of an even simpler
multivariate polynomial: the latter can be evaluated directly by Verifier at
several points, which forms the basis for his sketching. When applied to graph
problems, this technique was historically used to reshape the
$\binom{n}{2}$-dimensional vector of edge multiplicities. Recently,
Chakrabarti and Ghosh [CG19] introduced the idea of reshaping the graph’s
vertex space, rather than just the edge space, thereby transforming the
adjacency matrix into a $4$-dimensional array. This trick was crucial to
obtaining the first frugal schemes for TriangleCount and MaxMatching.

Our Contributions. The new schemes in this work make the following
contributions.

  * •

We design new polynomial encodings for the graph-theoretic problems we study.

  * •

We prominently employ nonlinear sketches, in the above sense, for almost all
of our scheme designs.

  * •

We use the shaping technique on the vertex space, often combining it with
nonlinear sketching, thus expanding the applications of this very recent
innovation.

Our solutions for TriangleCount are particularly good illustrations of all of
these ideas. Where Thaler’s nonlinear-sketch protocol treated each vertex as
monolithic, our view of each vertex as an object in $[t]\times[s]$ (for some
pair $t,s$ with $t\cdot s=n$) let us do two things. In the laconic regime, we
get to use Verifier’s increased space allowance in a way that Thaler’s
protocol cannot, thereby extending his $[n,n]$-scheme to get an optimal
tradeoff. In the frugal regime, it is significantly harder to exploit vertex-
space shaping because Verifier cannot even afford to devote one entry per
vertex in his linear sketches. We overcome this by finding a way for many
vertices to “share” each entry of each linear sketch (see the string of
equations culminating in eq. 7), thus extending Thaler’s protocol to smoothly
trade off communication for space.

We also extend the applicability of nonlinear sketching by identifying many
further graph problems for which it yields significant improvements.
Specifically, in Section 3, we describe two technical problems called
InducedEdgeCountand CrossEdgeCount, which are later used as primitives to
optimally solve several important graph problems, including MaxMatching. We
show how to apply sum-check with a nonlinear Verifier (see, e.g, eq. 11) to
optimally solve InducedEdgeCount and CrossEdgeCount.

Finally, our schemes for SSSP feature a different kind of innovation on top of
vertex-space shaping and new, clever encodings of shortest-path problems in a
manner amenable to sum-check. They overcome the frugal Verifier’s space
limitation by exploiting the Prover’s room to generate a proof stream that
mimics an iterative algorithm. For the Verifier to play along with such an
iterative algorithm while lacking even one bit of space per vertex, a careful
layering of fingerprint-based checks is needed on top of the sum-checks. We
hope that our work here opens up possibilities for other instances of porting
iterative algorithms to a streaming setting with the help of a prover.

###  1.5 Preliminaries

In this work, the input graph, multigraph, or digraph is denoted $G$ and
defined on a fixed vertex set $V=[n]$. In the vanilla streaming model, $G$ is
given as a stream of $(u,v)$ tokens, where $u,v\in V$: the token is
interpreted as an insertion of edge $\\{u,v\\}$ or directed edge $(u,v)$. If
$G$ is edge-weighted, the tokens are of the form $(u,v,w)$, where
$w\in\mathbb{Z}^{+}$ is a weight. In the turnstile streaming model, tokens are
of the form $(u,v,\Delta)$, denoting that the quantity $\Delta\in\mathbb{Z}$
(which can be negative) is added either to the multiplicity or the weight of
the edge $\\{u,v\\}$.

An important primitive in all our schemes is sketching a data vector by
evaluating its low-degree extension at a random point. Let us explain what
this means. Suppose our data vector, which has dimensionality $N$, is shaped
into a $k$-dimensional array $f$ with dimensions $(s_{1},\ldots,s_{k})$, where
$s_{1}s_{2}\cdots s_{k}\geqslant N$. Equivalently, we have a function $f$ on
domain $[s_{1}]\times\cdots\times[s_{k}]$. We work over a suitable finite
field666The characteristic of $\mathbb{F}$ must be large enough to avoid “wrap
around” problems under arithmetic in $\mathbb{F}$. $\mathbb{F}$. By Lagrange
interpolation, there is a unique polynomial
$\tilde{f}(X_{1},\ldots,X_{k})\in\mathbb{F}[X_{1},\ldots,X_{k}]$ such that

  * •

for all $(x_{1},\ldots,x_{k})\in[s_{1}]\times\cdots[s_{k}]$, we have
$\tilde{f}(x_{1},\ldots,x_{k})=f(x_{1},\ldots,x_{k})$, and

  * •

for all $i\in[k]$, we have $\deg_{X_{i}}\tilde{f}\leqslant s_{i}-1$.

We call $\tilde{f}$ the low-degree $\mathbb{F}$-extension of $f$. Since
$f\mapsto\tilde{f}$ is a linear map, we can write $\tilde{f}$ as a linear
combination of “unit impulse” functions (also known as Lagrange basis
polynomials):

$\displaystyle\delta_{u_{1},\ldots,u_{k}}(X_{1},\ldots,X_{k}):=\prod_{i=1}^{k}\prod_{x_{i}\in[s_{i}]\setminus\\{u_{i}\\}}(u_{i}-x_{i})^{-1}(X_{i}-x_{i})\,.$
(1)

To be precise,
$\tilde{f}(X_{1},\ldots,X_{k})=\sum_{(u_{1},\ldots,u_{k})\in[s_{1}]\times\cdots\times[s_{k}]}f(u_{1},\ldots,u_{k})\,\delta_{u_{1},\ldots,u_{k}}(X_{1},\ldots,X_{k})$.
In particular, if $f$ is built up from a stream of pointwise updates, where
the $j$th update adds $\Delta_{j}$ to entry $(u_{1},\ldots,u_{k})_{j}$ of the
array, then

$\tilde{f}(X_{1},\ldots,X_{k})=\sum_{j}\Delta_{j}\,\delta_{(u_{1},\ldots,u_{k})_{j}}(X_{1},\ldots,X_{k})\,.$
(2)

######  Fact 1.1.

Given $\mathbf{p}=(p_{1},\ldots,p_{k})\in\mathbb{F}^{k}$ and a stream of
pointwise updates to an initially-zero array with dimensions
$(s_{1},\ldots,s_{k})$, we can maintain the evaluation $\tilde{f}(\mathbf{p})$
using $O(\log|\mathbb{F}|)$ space, performing $O(k)$ field arithmetic
operations per update. In applications, we usually take
$\mathbf{p}\in_{R}\mathbb{F}^{k}$.777The notation $r\in_{R}A$ means that $r$
is drawn uniformly at random from the finite set $A$. For details and
implementation considerations, see Cormode et al. [CTY11]. ∎

Another useful primitive is fingerprinting, used prominently in our SSSP
scheme and subtly in subroutines within other schemes. Its goal is to check
equality between two vectors $\mathbf{a}=(a_{1},\ldots,a_{N})$ and
$\mathbf{b}=(b_{1},\ldots,b_{N})$ that are provided via turnstile streams in
some possibly intermixed order. This is achieved by checking that
$\varphi_{\mathbf{a}}(r)=\varphi_{\mathbf{b}}(r)$ for $r\in_{R}\mathbb{F}$,
where $\varphi_{\mathbf{a}}(X)=\sum_{j=1}^{N}a_{j}X^{j}$ is the fingerprint
polynomial of $\mathbf{a}$ and has degree at most $N$. Both fingerprinting and
the eventual uses of 1.1 in sum-check protocols depend upon the following
basic but powerful result.

######  Fact 1.2 (Schwartz–Zippel Lemma).

For a nonzero polynomial
$P(X_{1},\ldots,X_{n})\in\mathbb{F}[X_{1},\ldots,X_{n}]$ of total degree $d$,
where $\mathbb{F}$ is a finite field,
$\Pr_{(r_{1},\ldots,r_{n})\in_{R}\mathbb{F}^{n}}\left[P(r_{1},\ldots,r_{n})=0\right]\leqslant
d/|\mathbb{F}|$. ∎

At various points, we shall use a couple of schemes from Chakrabarti et al.
[CCGT14, CCMT14].

######  Fact 1.3 (subset and intersection schemes; Prop. 4.1 of [CCMT14] and
Thm. 5.3 of [CCGT14]).

Given a stream of elements of sets $S,T\subseteq[N]$ interleaved arbitrarily,
for any $h,v$ with $hv\geqslant N$, there are $[h,v]$-schemes to compute
$|S\cap T|$ and to determine whether $S\subseteq T$. ∎

##  2 The Triangle Counting Problem

A triangle in a (multi)graph is a set of three edges of the form
$\\{\\{u,v\\},\\{v,w\\},\\{u,w\\}\\}$. The TriangleCount problem asks for the
number of such triangles in the input graph. We solve this problem for
multigraphs given by a turnstile stream, establishing the following two
theorems. The first gives improved (but possibly still not tight) tradeoffs
between hcost $h$ and vcost $v$ in the parameter regime where $h\geqslant n$
and $v\leqslant n$. The second gives _optimal_ tradeoffs (up to logarithmic
factors) in the regime where $h\leqslant n$ and $v\geqslant n$, based on the
known lower bound that $hv$ must be $\Omega(n^{2})$. Both results were
previously only known when $h=\Theta(n)$.

We remind the reader that parameters $t,s\in\mathbb{Z}^{+}$ are tunable,
subject to $ts=n$.

######  Theorem 2.1 (Improved frugal schemes).

There is an $[nt^{2},s]$-scheme for TriangleCount.

######  Theorem 2.2 (Optimal tradeoff for laconic schemes).

There is a $[t,ns]$-scheme for TriangleCount. This is optimal up to
logarithmic factors.

Overview of Our Methods. Consider an adjacency matrix $A$ of a graph on vertex
set $V$. The addition of a new edge $\\{u,v\\}$ creates $\sum_{z\in
V}A(u,z)A(v,z)$ new triangles.

Suppose that the input stream consists of $L$ edge updates, the $j$th being
$(v_{1j},v_{2j},\Delta_{j})$; recall that its effect is to add $\Delta_{j}$ to
the multiplicity of edge $\\{v_{1j},v_{2j}\\}$. Suppose that the cumulative
effect of the first $j$ updates is to produce a multigraph $G_{j}$ whose
adjacency matrix is $A_{j}$ and which has $T_{j}$ triangles (counting
multiplicity). As in Thaler’s protocol [Tha16b], we can then account for the
number of triangles added by the $j$th update:

$\displaystyle T_{j}-T_{j-1}$ $\displaystyle=\sum_{v_{3}\in
V}\Delta_{j}\,A_{j-1}(v_{1j},v_{3})\,A_{j-1}(v_{2j},v_{3})\,.$

As a result, the number of triangles $T$ in the final graph $G=G_{L}$ is

$\displaystyle T$ $\displaystyle=\sum_{j\in[L]}\sum_{v_{3}\in
V}\Delta_{j}\,A_{j-1}(v_{1j},v_{3})\,A_{j-1}(v_{2j},v_{3})\,.$ (3)

Our two new families of schemes for TriangleCount apply the shaping technique
to the above equation in two distinct ways, resulting in markedly different
complexity behaviors.

###  2.1 The Laconic Schemes Regime (Proof of Theorem 2.2)

Let $t,s\in\mathbb{N}$ be parameters with $ts=n$. We first consider rewriting
the variable $v_{3}$ in eq. 3 as a pair of integers
$(x_{3},y_{3})\in[t]\times[s]$ using some canonical bijection. This shapes
each matrix $A_{j-1}$ into a $3$-dimensional array $a_{j-1}$, i.e., a function
with domain $[n]\times[t]\times[s]$. Let $\tilde{a}$ be the
$\mathbb{F}$-extension of $a$ for a sufficiently large finite field
$\mathbb{F}$ to be chosen later. Then eq. 3 becomes

$\displaystyle T$
$\displaystyle=\sum_{j\in[L]}\sum_{x_{3}\in[t]}\sum_{y_{3}\in[s]}\Delta_{j}\,\tilde{a}_{j-1}(v_{1j},x_{3},y_{3})\,\tilde{a}_{j-1}(v_{2j},x_{3},y_{3})=\sum_{x_{3}\in[t]}p(x_{3})\,,\quad\text{where}$
(4) $\displaystyle p(X_{3})$
$\displaystyle=\sum_{j\in[L]}\sum_{y_{3}\in[s]}\Delta_{j}\,\tilde{a}_{j-1}(v_{1j},X_{3},y_{3})\,\tilde{a}_{j-1}(v_{2j},X_{3},y_{3})\,.$
(5)

By the properties of $\mathbb{F}$-extensions observed above, we have the bound
$\deg p\leqslant 2(t-1)$. We now design our scheme as follows.

Stream processing.

Verifier starts by picking $r_{3}\in_{R}\mathbb{F}$. As the stream arrives, he
maintains a $2$-dimensional array of values $\tilde{a}_{j-1}(v,r_{3},y)$, for
all $(v,y)\in[n]\times[s]$, using 1.1. He also maintains an accumulator that
starts at zero and, after the $j$th update, is incremented by
$\Delta_{j}\sum_{y_{3}\in[s]}\tilde{a}_{j-1}(v_{1j},r_{3},y_{3})\,\tilde{a}_{j-1}(v_{2j},r_{3},y_{3})$.
By eq. 5, the final value of this accumulator is $p(r_{3})$.

Help message.

Prover sends Verifier a polynomial $\hat{p}(X_{3})$ of degree $\leqslant
2(t-1)$ that she claims equals $p(X_{3})$.

Verification and output.

Using Prover’s message, Verifier computes the check value $C:=\hat{p}(r_{3})$
and the result value $\hat{T}:=\sum_{x_{3}\in[t]}\hat{p}(x_{3})$. If he finds
that $C\neq p(r_{3})$, he outputs $\bot$. Otherwise, he believes that
$\hat{p}\equiv p$ and accordingly, based on eq. 4, outputs $\hat{T}$ as the
answer.

The analysis of this scheme proceeds along standard lines long established in
the literature.

Error probability.

An honest Prover ($\hat{p}\equiv p$) clearly ensures perfect completeness. The
soundness error is the probability that Verifier’s check passes despite
$\hat{p}\not\equiv p$, i.e., that the random point $r_{3}\in\mathbb{F}$ is a
root of the nonzero degree-$(2t-2)$ polynomial $\hat{p}-p$. By the
Schwartz–Zippel Lemma (1.2), this probability is at most
$(2t-2)/|\mathbb{F}|<1/n$, by choosing $|\mathbb{F}|$ large enough.

Help and Verification costs.

Prover describes $\hat{p}$ by listing its $O(t)$ many coefficients, spending
$O(t\log n)$ bits, since each is an element of $\mathbb{F}$ and
$|\mathbb{F}|=n^{O(1)}$ suffices above. Verifier maintains an $n\times s$
array whose entries are in $\mathbb{F}$, for a vcost of $O(ns\log n)$.
Overall, we get a $[t,ns]$-scheme, as required.

###  2.2 The Frugal Schemes Regime (Proof of Theorem 2.1)

Designing frugal schemes on the basis of eq. 3 is more intricate. This time we
rewrite the variables $v_{1j}$ and $v_{2j}$ as pairs $(x_{1j},y_{1j})$ and
$(x_{2j},y_{2j})$, each in $[t]\times[s]$ for parameters $t,s$ with $ts=n$.
The matrices $A_{j-1}$ are now shaped into $3$-dimensional arrays $b_{j-1}$
that can be seen as functions on the domain $[t]\times[s]\times[n]$. As
before, let $\tilde{b}$ be an appropriate $\mathbb{F}$-extension. Working from
eq. 3 and cleverly using the “unit impulse” function $\delta$ seen in eq. 1,

$\displaystyle T$ $\displaystyle=\sum_{v_{3}\in
V}\sum_{j\in[L]}\Delta_{j}\,\tilde{b}_{j-1}(x_{1j},y_{1j},v_{3})\,\tilde{b}_{j-1}(x_{2j},y_{2j},v_{3})$
$\displaystyle=\sum_{v_{3}\in
V}\sum_{w_{1},w_{2}\in[t]}\sum_{j\in[L]}\Delta_{j}\,\tilde{b}_{j-1}(w_{1},y_{1j},v_{3})\,\tilde{b}_{j-1}(w_{2},y_{2j},v_{3})\,\delta_{x_{1j}}(w_{1})\,\delta_{x_{2j}}(w_{2})$
$\displaystyle=\sum_{v_{3}\in
V}\sum_{w_{1},w_{2}\in[t]}q(w_{1},w_{2},v_{3})\,,\quad\text{where}$ (6)
$\displaystyle q(W_{1},W_{2},V_{3})$
$\displaystyle=\sum_{j\in[L]}\Delta_{j}\,\tilde{b}_{j-1}(W_{1},y_{1j},V_{3})\,\tilde{b}_{j-1}(W_{2},y_{2j},V_{3})\,\delta_{x_{1j}}(W_{1})\,\delta_{x_{2j}}(W_{2})\,.$
(7)

In contrast to section 2.1, we have a multivariate polynomial
$q(W_{1},W_{2},V_{3})$. We have the bounds $\deg_{W_{1}}q\leqslant 2(t-1)$,
$\deg_{W_{2}}q\leqslant 2(t-1)$, and $\deg_{V_{3}}q\leqslant 2(n-1)$, for a
total degree of $O(t+n)=O(n)$. Importantly, the number of monomials in $q$ is
at most $(2t-1)^{2}(2n-1)=O(nt^{2})$. We now present the corresponding scheme
and its analysis.

Stream processing.

Verifier picks $r_{1},r_{2},r_{3}\in_{R}\mathbb{F}$. As the stream arrives, he
maintains two $1$-dimensional arrays: $\tilde{b}_{j-1}(r_{1},y,r_{3})$ and
$\tilde{b}_{j-1}(r_{2},y,r_{3})$, for all $y\in[s]$ (using 1.1). He also
maintains an accumulator that starts at zero and, after the $j$th update
$(x_{1j},y_{1j},x_{2j},y_{2j})$, is incremented by

$\Delta_{j}\,\tilde{b}_{j-1}(r_{1},y_{1j},r_{3})\,\tilde{b}_{j-1}(r_{2},y_{2j},r_{3})\,\delta_{x_{1j}}(r_{1})\,\delta_{x_{2j}}(r_{2})\,.$

By eq. 7, the final value of this accumulator is $q(r_{1},r_{2},r_{3})$.

Notice that the accumulator is a nonlinear sketch of the input.

Help message.

Prover sends Verifier a polynomial $\hat{q}(W_{1},W_{2},V_{3})$ that she
claims equals $q(W_{1},W_{2},V_{3})$. It should satisfy the degree bounds
noted above. He lacks the space to store $\hat{q}$, so she streams the
coefficients of $\hat{q}$ in some canonical order.

Verification and output.

As $\hat{q}$ is streamed in, Verifier computes the check value
$C:=\hat{q}(r_{1},r_{2},r_{3})$ and the result value
$\hat{T}:=\sum_{v_{3}\in[n]}\sum_{w_{1},w_{2}\in[t]}\hat{q}(w_{1},w_{2},v_{3})$.
If he finds that $C\neq q(r_{1},r_{2},r_{3})$, he outputs $\bot$. Otherwise,
he believes that $\hat{q}\equiv q$ and accordingly, based on eq. 6, outputs
$\hat{T}$ as the answer.

Error probability.

As before, we have perfect completeness and by the Schwartz–Zippel Lemma (1.2,
this time using its full multivariate strength), this soundness error is at
most $\deg q/|\mathbb{F}|=O(n)/|\mathbb{F}|<1/n$, by choosing $|\mathbb{F}|$
large enough.

Help and Verification costs.

Prover can describe $\hat{q}$ by listing its $O(nt^{2})$ coefficients.
Verifier maintains two $s$-length arrays. Overall, we get an
$[nt^{2},s]$-scheme, as required.

##  3 A Technical Result: Counting Edges in Induced Subgraphs

We introduce two somewhat technical, though still natural, graph problems:
InducedEdgeCount and CrossEdgeCount. We design schemes for these problems
giving optimal tradeoffs (as usual, up to logarithmic factors). These schemes
are key subroutines in our schemes for more standard, well-studied graph
problems—such as MaxMatching—considered in Section 4.

The InducedEdgeCount problem is defined as follows. The input is a stream of
edges of a graph $G=(V,E)$ followed by a stream of vertex subsets $\langle
U_{1},\ldots U_{\ell}\rangle$ for some $\ell\in\mathbb{N}$, where
$U_{i}\subseteq V$ for $i\in[\ell]$. To be precise, the latter portion of the
stream consists of the vertices of $U_{1}$ in arbitrary order, followed by a
delimiter, followed by the vertices of $U_{2}$ in arbitrary order, and so on.
The desired output is $\sum_{i=1}^{\ell}|E(G[U_{i}])|$, the sum of the numbers
of edges in the induced subgraphs $G[U_{1}],\ldots,G[U_{\ell}]$. Note that
$U_{1},\ldots,U_{\ell}$ need not be pairwise disjoint, so the sum may count
some edges more than once.

The CrossEdgeCount problem is an analog of the above for induced bipartite
subgraphs. The input is a stream of edges followed by $\ell$ pairs of vertex
subsets $\langle(U_{1},W_{1}),\ldots,(U_{\ell},W_{\ell})\rangle$, where
$U_{i}\cap W_{i}=\varnothing$ for $i\in$ $[\ell]$. The desired output is
$\sum_{i=1}^{\ell}|E(G[U_{i},W_{i}])|$, the sum of the number of cross-edges
in the induced bipartite subgraphs
$G[U_{1},W_{1}],\ldots,G[U_{\ell},W_{\ell}]$. Note that the $U_{i}$s (or
$W_{i}$s) need not be disjoint among themselves.

Importantly, in both of these problems, the edges precede the vertex subsets
in the stream. This makes the problems intractable in the basic data streaming
model. We shall prove the following results.

######  Lemma 3.1.

For any $h,v$ with $hv=n^{2}$, there is an $[h,v]$-protocol for
InducedEdgeCount.

######  Lemma 3.2.

For any $h,v$ with $hv=n^{2}$, there is an $[h,v]$-protocol for
CrossEdgeCount.

Scheme for InducedEdgeCount (Proof of Lemma 3.1). For the given instance, let
$M$ denote the desired output and let $A$ be the adjacency matrix of $G$. For
each $i\in\ell$, let $B_{i}\in\\{0,1\\}^{V}$ be the indicator vector of the
set $U_{i}$, i.e., $B_{i}(v)=1\iff v\in U_{i}$. Then,

$M=\frac{1}{2}\sum_{i=1}^{\ell}\sum_{v_{1},v_{2}\in
V}B_{i}(v_{1})\,B_{i}(v_{2})\,A(v_{1},v_{2})\,.$ (8)

Let $t,s$ be integer parameters such that $ts=n$. We apply the shaping
technique to eq. 8 by rewriting the variables $v_{j}$ as pairs of integers
$(x_{j},y_{j})\in[t]\times[s]$, for $j\in\\{1,2\\}$. This transforms the
matrix $A$ into a $4$-dimensional array $a$ and each $B_{i}$ into a
$2$-dimensional array $b_{i}$. Let $\tilde{a}$ and $\tilde{b}_{i}$ be the
respective $\mathbb{F}$-extensions. Equation 8 now gives

$\displaystyle 2M$
$\displaystyle=\sum_{i=1}^{\ell}\sum_{x_{1},x_{2}\in[t]}\sum_{y_{1},y_{2}\in[s]}\tilde{b}_{i}(x_{1},y_{1})\,\tilde{b}_{i}(x_{2},y_{2})\,\tilde{a}(x_{1},y_{1},x_{2},y_{2})=\sum_{x_{1},x_{2}\in[t]}p(x_{1},x_{2})\,,\quad\text{where}$
(9) $\displaystyle p(X_{1},X_{2})$
$\displaystyle=\sum_{i=1}^{\ell}\sum_{y_{1},y_{2}\in[s]}\tilde{b}_{i}(X_{1},y_{1})\,\tilde{b}_{i}(X_{2},y_{2})\,\tilde{a}(X_{1},y_{1},X_{2},y_{2})\,.$
(10)

Our scheme exploits this expression in the same general manner as the
analogous expressions for the TriangleCount schemes from Section 2 (e.g.,
Equation (4)). Prover sends a bivariate polynomial $\hat{p}(X_{1},X_{2})$,
which is claimed to be $p$, by streaming its coefficients. Since
$\deg_{X_{j}}p\leqslant 2(t-1)$ for $j\in\\{1,2\\}$, Prover need only send
$O(t^{2})$ coefficients, for a help cost of $\tilde{O}(t^{2})$. Verifier
computes his output using eq. 9, giving perfect completeness. On the soundness
side, Verifier checks the condition $\hat{p}(r_{1},r_{2})=p(r_{1},r_{2})$ for
randomly chosen $r_{1},r_{2}\in_{R}\mathbb{F}$. By the Schwartz-Zippel Lemma
(1.2), the probability that he is fooled is at most $\deg
p/|\mathbb{F}|=O(t)/|\mathbb{F}|<1/n$, for the right choice of $\mathbb{F}$.
It remains to describe how exactly Verifier evaluates $p(r_{1},r_{2})$, which
we now address.

Processing the stream of edges.

This is straightforward: Verifier maintains the $2$-dimensional array of
values $\tilde{a}(r_{1},w,r_{2},z)$, for all $w,z\in[s]$, using 1.1.

Processing the stream of vertex subsets.

Verifier initializes an accumulator to zero and allocates workspace for two
arrays of length $s$ with entries in $\mathbb{F}$. For each $i\in[\ell]$, as
the vertices of $U_{i}$ arrive, he maintains $\tilde{b}_{i}(r_{1},z)$ and
$\tilde{b}_{i}(r_{2},z)$ for each $z\in[s]$, using that workspace. Upon seeing
the delimiter marking the end of $U_{i}$, he computes

$\sum_{y_{1},y_{2}\in[s]}\tilde{b}_{i}(r_{1},y_{1})\,\tilde{b}_{i}(r_{2},y_{2})\,\tilde{a}(r_{1},y_{1},r_{2},y_{2})$
(11)

and adds this quantity to the accumulator. Note that the workspace is reused
when the stream moves on from $U_{i}$ to $U_{i+1}$. By eq. 10, after the last
set $U_{\ell}$ is streamed, the accumulator holds $p(r_{1},r_{2})$.

Help and verification costs.

We argued above that the hcost is $\tilde{O}(t^{2})$. Meanwhile, Verifier’s
storage is dominated by the $s\times s$ array he maintains, leading to a vcost
of $\tilde{O}(s^{2})$.

Therefore, we obtain a $[t^{2},s^{2}]$-scheme for any parameters $t,s$ with
$ts=n$. In other words, we get an $[h,v]$-scheme for any $h,v$ with
$hv=n^{2}$.

Scheme for CrossEdgeCount (Proof of Lemma 3.2). Our solution for
InducedEdgeCount can easily be modified to obtain a protocol for
CrossEdgeCount with the same costs. If $B_{i}$ and $C_{i}$ are the indicator
vectors of the sets $U_{i}$ and $W_{i}$, respectively, then the desired output
is

$M=\sum_{i=1}^{\ell}\sum_{v_{1},v_{2}\in
V}B_{i}(v_{1})\,C_{i}(v_{2})\,A(v_{1},v_{2})\,,$ (12)

where we used the fact that each $U_{i}\cap W_{i}=\varnothing$. Since eq. 12
has essentially the same form as eq. 8, a scheme very similar to the previous
one solves CrossEdgeCount: Verifier simply keeps track of arrays corresponding
to $C_{i}$ alongside ones corresponding to $B_{i}$.

##  4 Maximum Matching and Other Applications of Edge Counting

In this section, we show how InducedEdgeCount and CrossEdgeCount can be used
as subroutines to solve multiple problems that have been widely studied in the
basic and annotated data streaming models. These problems include Maximum
Matching, Triangle-Counting, Maximal Independent Set, Acyclicity Testing,
Topological Sorting, and Graph Connectivity. For the frugal regime where vcost
$=o(n)$, our schemes are often optimal. We specifically discuss the
application to MaxMatching in Section 4.1, and give an account of the other
applications in Section 4.2.

###  4.1 The Maximum Matching Problem

We give the first optimal frugal scheme for computing the cardinality
$\alpha^{\prime}(G)$ of a maximum matching. As noted in prior works [CG19,
Tha16b], checking whether $\alpha^{\prime}(G)\geqslant k$ for some $k$ is not
hard, given $\tilde{\Omega}(k)$ bits of help: Prover can simply send a
matching of size $k$ and prove its validity. The interesting part is to verify
that $\alpha^{\prime}(G)\leqslant k$. For this, as in prior works, we exploit
the Tutte–Berge formula [BM08]:

$\alpha^{\prime}(G)=\frac{1}{2}\,\min_{U\subseteq
V}\Big{(}\,|U|+|V|-\text{odd}(G\setminus U)\,\Big{)}\,,$ (13)

where $\text{odd}(G\setminus U)$ denotes the number of connected components in
$G\setminus U$ with an odd number of vertices. Thus, to show that
$\alpha^{\prime}(G)\leqslant k$, Prover needs to exhibit $U^{*}\subseteq V$
such that $k=\frac{1}{2}(|U^{*}|+|V|-\text{odd}(G\setminus U^{*}))$. Set
$H:=G\setminus U^{*}$. To verify the value of odd$(H)$, the most important
sub-check that Verifier must do is to check that all purported connected
components of $H$ (sent by Prover) are actually disconnected from each other.
Thaler [Tha16b] gave an $[n,n]$-scheme for this subproblem (thus obtaining the
first $[n,n]$-scheme for MaxMatching), while Chakrabarti and Ghosh [CG19] gave
a $[t^{3},s^{2}]$-scheme for any $ts=n$ (thus designing the first frugal
scheme for MaxMatching, though suboptimal). The latter work notes that all
other sub-checks for MaxMatching can be done by _optimal_ frugal schemes (see
[CG19], Section 4).

Optimal Frugal Scheme. To optimally check that the purported connected
components of $H$ are indeed disconnected from each other, we use the
InducedEdgeCount scheme as a subroutine. Prover streams the vertices in $H$ by
listing its connected components in some order $\langle
U_{1},\ldots,U_{\ell}\rangle$. Verifier uses Lemma 3.1 to count
$m_{1}:=|E(H)|$ (invoking that lemma with a single subset $V(H)$). In
parallel, using the same scheme, Verifier computes the sum
$m_{2}=\sum_{i=1}^{\ell}|E(G[U_{i}])|$. The subsets $U_{i}$ are pairwise
disconnected iff $m_{2}=m_{1}$, which Verifier checks. The sub-checks of
whether $U_{i}$s are indeed pairwise disjoint (as sets) and whether
$U^{*}\sqcup V(H)=V(G)$ can be done via fingerprinting (as in section 1.5).

Help and verification costs. Prover streams $U^{*}$ and the vertices in $H$ in
a certain order, which adds $O(n\log n)$ bits to the hcost of the
InducedEdgeCount protocol. The vcost stays the same, asymptotically, giving us
an $[n+h,v]$-scheme for MaxMatching for any $h,v$ with $hv=n^{2}$. Overall, we
have established the following theorem.

######  Theorem 4.1.

There is an $[nt,s]$-scheme for MaxMatching. This is optimal up to logarithmic
factors, since any $(h,v)$-scheme is known to require $hv=\Omega(n^{2})$
[CCMT14].

Protocol for Space Larger Than $n$. There is no laconic scheme known for the
general MaxMatching problem. The barrier seems to be that a natural witness
for the problem is an actual maximum matching of the graph, which can be of
size $\Theta(n)$. We show that large maximum matching size
$\alpha^{\prime}(G)$ is indeed the sole barrier to obtaining a laconic scheme.
In particular, for any graph $G$, we give a scheme for MaxMatching with hcost
$\alpha^{\prime}(G)$. This yields a laconic scheme for the case when
$\alpha^{\prime}(G)=o(n)$.

Let $H=G\setminus U^{*}$ as above, and let $U_{1},\ldots,U_{\ell}$ be the
connected components of $H$. By the Tutte-Berge formula (eq. 13), we have
$2k=|U^{*}|+(n-\text{odd}(H))$. This leads to the following observations.

######  Observation 4.2.

$|U^{*}|=O(k)$.

######  Observation 4.3.

The number of edges in a spanning forest of $H$ is $|V(H)|-\ell\leqslant
n-\text{odd}(H)=O(k)$.

We now describe our protocol, which is along the lines of the protocol above,
but this time we crucially use the fact that we are allowing Verifier a space
usage of $v\geqslant n$.

To show that $\alpha^{\prime}(G)\geqslant k$, Prover sends a matching $M$ of
size $k$. Verifier stores $M$ explicitly and checks that it is indeed a
matching. Then, he verifies that $M\subseteq E$ using the Subset Scheme (Fact
1.3). Therefore, this part of the scheme uses hcost $\tilde{O}(k+h)$ and vcost
$\tilde{O}(v)$ for any $h,v$ with $hv=n^{2}$ and $v\geqslant n$.

Recall that to show that $\alpha^{\prime}(G)\leqslant k$, it suffices to
compute odd$(H)$. Prover sends the set $U^{*}$. By 4.2, this takes
$\tilde{O}(k)$ hcost. Verifier has $\Omega(n)$ space, and hence, he can store
$V\setminus U^{*}=V(H)$. Next, Prover sends a spanning forest $F$ of $H$. By
4.3, this again incurs hcost $\tilde{O}(k)$. Verifier stores $F$ and verifies
that $F\subseteq E$ using the Subset Scheme (Fact 1.3). From $F$, Verifier
explicitly knows the purported connected components $U_{1},\ldots,U_{\ell}$ of
$H$. He finally verifies that $U_{i}$’s are disconnected from each other by
checking that all edges in $H$ are contained in these components. He can do
this by checking whether $|E\cap(V(H)\times
V(H))|=|E\cap(\cup_{i=1}^{\ell}U_{i}\times U_{i})|$ using the Intersection
Scheme (Fact 1.3). If the check passes he goes over the $U_{i}$s to compute
odd$(H)$ and thus, this part can also be solved using a $[k+h,v]$ scheme for
any $h,v$ with $hv=n^{2}$ and $v\geqslant n$. Hence, we obtain the following
theorem.

######  Theorem 4.4.

For any $h,v$ with $hv\geqslant n^{2}$ and $v\geqslant n$, there is an
$[\alpha^{\prime}+h,v]$-scheme for MaxMatching, where $\alpha^{\prime}$ is the
size of the maximum matching of the input graph. In particular, there is an
$[\alpha^{\prime},n^{2}/\alpha^{\prime}]$-scheme.

###  4.2 Applications to Other Graph Problems

In Section 4.1, we used a scheme for InducedEdgeCount to obtain an optimal
frugal scheme for MaxMatching. Below, we give applications of edge-counting
schemes to several other well-studied graph problems.

Triangle-Counting. A scheme for TriangleCount follows immediately from
InducedEdgeCount. For $v\in[n]$, set the subsets $U_{v}=N(v)$, the
neighborhood of vertex $v$. Then, observe that InducedEdgeCount returns three
times the total number of triangles in the graph. The sets $U_{v}$, however,
need to be sent in some order by Prover, and so the additional hcost to
InducedEdgeCount is $\tilde{O}\left(\sum_{v}|N(v)|\right)=\tilde{O}(m)$. As
Prover basically repeats the edge stream in a different order, we can check if
it’s consistent with the input stream by fingerprinting (see Section 1.5).
Hence, we get an $[m+h,v]$-scheme for any $h,v$ with $hv=n^{2}$.

######  Theorem 4.5.

For any $h,v$ with $hv\geqslant n^{2}$, there is an $[m+h,v]$-scheme for
TriangleCount. In particular, there is an $[m,n^{2}/m]$-scheme.

The only other scheme for TriangleCount achieving $hv=n^{2}$ tradeoff with
vcost $=o(n)$ was an $[n^{2},1]$-scheme by Chakrabarti et al. [CCMT14]. Our
result generalizes it for any graph with $m$ edges, thus achieving a better
hcost and a smooth tradeoff for sparse graphs.

We note that in the above scheme, Prover needs to send the sets $U_{v}=N(v)$
because the InducedEdgeCount protocol needs the neighborhood of each vertex to
arrive contiguously in the stream. This is essentially the input stream order
in the _adjacency-list_ or the _vertex-arrival_ streaming model. Thus, for the
problem TriangleCount-Adj, Verifier gets the $U_{v}$s in the desired order as
part of the input; so Prover need not repeat them, saving the huge
$\tilde{O}(m)$ hcost. However, there is another issue in directly applying the
InducedEdgeCount subroutine in this case. In the definition of
InducedEdgeCount, we assume that all the edges in the graph arrive before the
vertex subsets $U_{i}$. Here, the $U_{v}$s and the edges arrive in interleaved
manner (although each $U_{v}$ arrives contiguously). But we show that we can
still apply the scheme for InducedEdgeCount to get the desired output. Let the
order in which the $U_{v}$s appear be $\langle U_{1},\ldots U_{n}\rangle$, and
let $G_{v}$ denote the graph consisting of edges seen till the arrival of
$U_{v}=N(v)$. Then, applying InducedEdgeCount, what we count is

$\displaystyle\sum_{v\in[n]}|E(G_{v}[N(v)])|=\sum_{v\in[n]}\\#\\{\text{triangles
incident on $v$ in }G_{v}\\}=2T\,.$

The last equality follows since every triangle whose vertices appear in the
order $\langle v_{1},v_{2},v_{3}\rangle$ will be counted twice: once when
$v_{2}$ arrives and once when $v_{3}$ arrives. We therefore obtain the
following theorem.

######  Theorem 4.6.

For any $h,v$ with $hv\geqslant n^{2}$, there is an $[h,v]$-scheme for
TriangleCount-Adj.

Maximal Independent Set (MIS). Recent works [ACK19, CDK19] have studied the
problem of finding a maximal independent set in the basic data streaming
model. They show a lower bound of $\Omega(n^{2})$ for a one-pass streaming
algorithm. This implies a lower bound of $hv\geqslant n^{2}$ for any
$[h,v]$-scheme for MIS. Hence, we aim for $hv=n^{2}$ and describe a frugal
scheme using InducedEdgeCount. Since the output size of the problem can be
$\Theta(n)$, it would only make sense in the frugal regime if the Prover sends
the output as a stream and the Verifier checks that it is valid using $o(n)$
space.

Let $U$ be an MIS in the graph $G$. Prover sends $U$ and Verifier uses
InducedEdgeCount to count the number of edges in $G[U]$ and verifies that it
equals $0$. If the check passes, $U$ is indeed an independent set. It remains
to check the maximality of $U$. If $U$ is maximal, then, for each vertex $v$
in $G\setminus U$, there must be a vertex $u$ in $U$, such that $(v,u)$ is an
edge. Prover points out such a vertex $u\in U$ for each $v\in G\setminus U$.
Let $F$ denote this set of $|G\setminus U|$ purported edges. Now, we use
Subset Scheme (Fact 1.3) to verify that $F\subseteq E$, i.e., all these edges
are actually present in $G$. We can use fingerprinting (as in Section 1.5) to
check that $F$ contains an edge for each vertex in $G\setminus U$ and the
Intersection Scheme to verify that the set of their partners is disjoint from
$G\setminus U$, i.e., belong to $U$. Thus, the additional hcost to
InducedEdgeCount, Subset, and Intersection Schemes is $\tilde{O}(n)$, the
number of bits required to send $U$ and $F$. Therefore, by Lemma 3.1, we get
an $[n+h,v]$-scheme for MIS for any $h,v$ with $hv=n^{2}$. Thus, our scheme is
optimal for the frugal regime.

######  Theorem 4.7.

For any $t,s$ with $ts=n$, there is an $[nt,s]$-scheme for MIS. This is
optimal up to logarithmic factors, since any $(h,v)$-scheme is known to
require $hv=\Omega(n^{2})$.

Acyclicity Testing and Topological Sorting. We now turn to the Acyclicity
problem in directed graphs. It is easy to prove that a graph is not acyclic by
showing the existence of a cycle $C$. Verifier checks that $C\subseteq E$
using Subset Scheme (Fact 1.3). Hence, this can be done using an
$[h,v]$-scheme for any $h\geqslant|C|$.

The more interesting case is when the graph is indeed acyclic. Note that a
directed graph is acyclic if and only if it has a topological ordering. Thus,
it suffices to show a valid topological ordering of the vertices. TopoSort is
a fundamental graph algorithmic problem of independent interest. Acyclicity
has a one-pass lower bound of $\Omega(n^{2})$ in the basic data streaming
model. Recently, Chakrabarti et al. [CGMV20] showed that TopoSort also
requires $\Omega(n^{2})$ space in one pass. These translate to a lower bound
of $hv\geqslant n^{2}$ for any $[h,v]$-scheme for these problems. Hence, we
aim for a scheme with $hv=n^{2}$ and design a protocol for TopoSort in the
frugal regime. Since this problem has output size $\tilde{\Theta}(n)$, we aim
for a protocol where Prover sends a topological ordering of the graph and
Verifier checks its validity using $o(n)$ space. Moreover, this protocol can
be used for the YES case of Acyclicity.

Verifier uses CrossEdgeCount to solve this. As Prover sends the topological
order $\langle v_{1},\ldots,v_{n}\rangle$, for each $i\in[n-1]$, Verifier sets
$U_{i}=\\{v_{1},\ldots,v_{i}\\}$ and $W_{i}=\\{v_{i+1}\\}$ for CrossEdgeCount.
Thus, the protocol counts precisely the number of forward edges induced by the
ordering. If it equals $m$, then the ordering is indeed a valid topological
order. Note that since $U_{i+1}=U_{i}\cup\\{v_{i+1}\\}$, Prover doesn’t need
to send $U_{i+1}$ afresh; just $v_{i+1}$ is enough for Verifier to update his
sketch. Verifier can use fingerprinting (see Section 1.5) to make sure that
precisely the set $V$ was sent in some order. Hence, the additional hcost to
CrossEdgeCount is the number of bits required to express the topological
order, i.e., $\tilde{O}(n)$. Therefore, by Lemma 3.2, we get a
$[n+h,v]$-scheme for any $hv=n^{2}$.

######  Theorem 4.8.

For any $t,s$ with $ts=n$, there is an $[nt,s]$-scheme for TopoSort. This is
optimal up to logarithmic factors, since any $(h,v)$-scheme is known to
require $hv=\Omega(n^{2})$.

######  Corollary 4.9.

For any $t,s$ with $ts=n$, there is an $[nt,s]$-scheme for Acyclicity. This is
optimal up to logarithmic factors, since any $(h,v)$-scheme is known to
require $hv=\Omega(n^{2})$.

For dense graphs, our result generalizes the $[m,1]$-scheme of Cormode et al.
[CMT13] for Acyclicity by achieving a smooth tradeoff.

Graph Connectivity. The graph connectivity problem has garnered considerable
attention in the basic and annotated streaming settings [AGM12, CCMT14,
Tha16b]. For any $t,s$ with $ts=n$, Chakrabarti et al. [CCMT14] gave an
$[nt,s]$-scheme that determines whether an input graph is connected or not.
Their scheme cannot, however, solve the more general problem of returning the
number of connected components. The $[t^{3},s^{2}]$-scheme (for any $ts=n$) of
Chakrabarti and Ghosh [CG19] does solve this problem, but has a worse
tradeoff. As noted in Section 4.1, we can use InducedEdgeCount to check that
all purported connected components are indeed disconnected from each other. On
the other hand, the scheme of Chakrabarti et al. [CCMT14] can check whether
each component is actually connected. Hence, we can verify the number of
connected components claimed by Prover by running these schemes parallelly.
Thus, we generalize the result of Chakrabarti et al. [CCMT14] by obtaining an
$[nt,s]$-scheme for counting the number of connected components of a graph.

######  Theorem 4.10.

For any $t,s$ with $ts=n$, there is an $[nt,s]$-scheme for counting the number
of connected components of a graph.

##  5 The Single-Source Shortest Path Problem

In the single-source shortest path (SSSP) problem, the goal is to find the
distances from a source vertex $v_{s}$ to every other vertex reachable from
it. In Section 5.1, we give a $[Dnt,s]$-scheme for the unweighted version,
whenever $ts=n$. If $s=o(n)$, Verifier does not have enough space to store the
output; therefore, we aim for a protocol where Prover streams the output, and
Verifier checks that it is correct using $o(n)$ space, thus achieving a frugal
scheme.

In Section 5.2, we state our results for weighted SSSP for the two different
weight update models described in Section 1.5 : (i) a $[DWn,n]$-scheme for the
“turnstile” model, and (ii) a $[Dn,Wn]$-scheme for the “vanilla” model.

###  5.1 Unweighted SSSP

We shall design a scheme that works even if the same edge appears multiple
times in the stream (unlike prior work [CMT13] that assumes that an edge
appears at most once).

Prover sends distance labels $\widehat{\text{dist}}[v]$ for all $v\in V$,
claiming that $\widehat{\text{dist}}[v]=\operatorname{dist}(v_{s},v)$, the
actual distance from the source vertex $v_{s}$ to $v$. Let the radius-$d$ ball
around $v_{s}$ be $B_{d}:=\\{v\in V:\,\operatorname{dist}(v_{s},v)\leqslant
d\\}$ and let $\mathcal{B}:=\\{B_{d}:\,d\in[D]\\}$ be the family of such
balls. Let $\widehat{B}_{d}$ be the corresponding balls implied by Prover’s
$\widehat{\text{dist}}$ labels, and
$\widehat{\mathcal{B}}:=\\{\widehat{B}_{d}:d\in[D]\\}$.

To check correctness, Verifier uses fingerprinting (Section 1.5) modified as
follows. Letting $B,\widehat{B}$ also denote the respective characteristic
vectors, define fingerprint polynomials

$\varphi_{\mathcal{B}}(X,Y):=\sum_{i\in[n]}\sum_{d\in[D]}B_{d}(i)X^{i}Y^{d}\,,\quad\varphi_{\widehat{\mathcal{B}}}(X,Y):=\sum_{i\in[n]}\sum_{d\in[D]}\widehat{B}_{d}(i)X^{i}Y^{d}\,,$

As the $\widehat{\text{dist}}$ labels are streamed, Verifier constructs the
fingerprint $\varphi_{\widehat{\mathcal{B}}}(\beta_{1},\beta_{2})$ for some
$\beta_{1},\beta_{2}\in_{R}\mathbb{F}$.

Over the course of the protocol, using further help from Prover, Verifier will
construct the sets $B_{d}$ inductively and, in turn, the “actual” fingerprint
$\varphi_{\mathcal{B}}(\beta_{1},\beta_{2})$. The next claim shows that
comparing this with $\varphi_{\widehat{\mathcal{B}}}(\beta_{1},\beta_{2})$
validates Prover’s $\widehat{\text{dist}}$ labels.

######  Claim 5.1.

If $\widehat{B}_{d}=B_{d}$ for all $d$, then
$\widehat{\text{dist}}[v]=\operatorname{dist}(v_{s},v)$ for all vertices $v$.

###### Proof.

Suppose not. Let $d^{*}$ be the smallest $d$ such that $\exists\,u\in
B_{d^{*}}$ with $\widehat{\text{dist}}[u]\neq\operatorname{dist}(v_{s},u)$.
Therefore, $\operatorname{dist}(v_{s},u)=d^{*}$. Now, $d^{*}$ cannot be $0$
since $v_{s}$ is the only vertex in $B_{0}$ and Verifier would reject
immediately if $\widehat{\text{dist}}(v_{s})\neq 0$. Since
$B_{d^{*}}=\widehat{B}_{d^{*}}$, we have $u\in\widehat{B}_{d^{*}}$. This means
$\widehat{\text{dist}}(u)\leqslant d^{*}$. Since $\widehat{\text{dist}}(u)\neq
d^{*}$, we have $\widehat{\text{dist}}(u)\leqslant d^{*}-1$. Thus,
$u\in\widehat{B}_{d^{*}-1}$, i.e., $u\in B_{d^{*}-1}$, which is a
contradiction to the minimality of $d^{*}$. ∎

As before, $A$ denotes the adjacency matrix of the graph. Putting

$\displaystyle q_{d}(u):=\sum_{v\in V}B_{d}(v)\,A(v,u)\,,\text{ for each }u\in
V\,,$ (14) $\displaystyle\text{we have~{}~{}}B_{d+1}=\left\\{u\in
V:q_{d}(u)\neq 0\right\\}\,.$ (15)

To apply the shaping technique to (14), rewrite $v$ as $(x,y)\in[t]\times[s]$.
This reshapes $A$ into a $t\times s\times n$ array $a(x,y,u)$ and $B_{d}$ into
a $t\times s$ array $b_{d}(x,y)$. As usual, let $\tilde{a}$ and
$\tilde{b}_{d}$ be the respective $\mathbb{F}$-extensions for a suitable
finite field $\mathbb{F}$. Then, eq. 14 gives

$\displaystyle q_{d}(u)$
$\displaystyle=\sum_{x\in[t]}p_{d}(x,u)\,,\quad\text{where}$ (16)
$\displaystyle p_{d}(X,U)$
$\displaystyle:=\sum_{y\in[s]}\tilde{b}_{d}(X,y)\,\tilde{a}(X,y,U)\,.$ (17)

Stream processing.

Verifier picks $r_{1},r_{2}\in_{R}\mathbb{F}$ and maintains
$\tilde{a}(r_{1},y,r_{2})$. When he sees vertices in $B_{1}$, i.e., $v_{s}$
and its neighbors, he maintains $b_{1}(r_{1},y)$ for all $y\in[s]$ and also
updates the fingerprint $\varphi_{\mathcal{B}}(\beta_{1},\beta_{2})$
accordingly.

Verifier wants to construct the values $b_{d}(r_{1},y)$ inductively for
$d\in[D]$. For constructing $b_{d+1}$ values for some $d$, he wants all $u$
such that $q_{d}(u)\neq 0$ (eq. 15) in streaming order since he doesn’t have
enough space to either store the entire polynomial of degree $n-1$ that agrees
with $q_{d}$ (so as to go over all evaluations), or to parallelly evaluate it
at $n$ values while its coefficients are streamed. Hence, he asks for the
following help message.

Help message processing.

Prover continues her proof stream by sending
$\langle\hat{p}_{1},Q_{1},\ldots,\hat{p}_{D},Q_{D}\rangle$, where
$Q_{d}:=\langle\hat{q}_{d}(u):u\in V\rangle$, claiming that $\hat{p}_{d}\equiv
p_{d}$ and $\hat{q}_{d}(u)=q_{d}(u)$ for each $d\in[D]$ and $u\in[n]$.

While $\hat{p}_{d}$ is streamed, Verifier computes the following in parallel:

  * •

$\hat{p}_{d}(r_{1},r_{2})$;

  * •

$p_{d}(r_{1},r_{2})$, using eq. 17;

  * •

the fingerprint $g_{d}:=\sum_{u\in[n]}\sum_{x\in[t]}\hat{p}_{d}(x,u)\beta^{u}$
(for some $\beta\in_{R}\mathbb{F}$).

After reading $\hat{p}_{d}$, he checks whether
$\hat{p}_{d}(r_{1},r_{2})=p_{d}(r_{1},r_{2})$. If so, he believes that
$\hat{p}_{d}\equiv p_{d}$ and, in turn, that
$g_{d}=\sum_{u\in[n]}q_{d}(u)\beta^{u}$ (by eq. 16). Next, as $Q_{d}$ is
streamed,

  * •

Verifier computes the fingerprint
$g_{d}^{\prime}:=\sum_{u\in[n]}\hat{q}_{d}(u)\beta^{u}$.

  * •

For each $u$ with $\hat{q}_{d}(u)\neq 0$, due to eq. 15 (and assuming for now
that the $\hat{q}_{d}$ values are correct), he treats $u$ as a stream update
for $B_{d+1}$, and (i) maintains $b_{d+1}(r_{1},y)$ for all $y\in[s]$, and
(ii) accordingly updates the fingerprint
$\varphi_{\mathcal{B}}(\beta_{1},\beta_{2})$.

After reading $Q_{d}$, he checks if the fingerprints $g_{d}$ and
$g_{d}^{\prime}$ match. If they do, he believes that all $\hat{q}_{d}$ values
in $Q_{d}$ were correct and hence, the $b_{d+1}$ values he constructed are
correct as well. He moves on to the next iteration, i.e., starts reading
$\hat{p}_{d+1}$.

Final Verification.

After the $D$th iteration, Verifier checks if the two fingerprints
$\varphi_{\mathcal{B}}(\beta_{1},\beta_{2})$ and
$\varphi_{\widehat{\mathcal{B}}}(\beta_{1},\beta_{2})$ match. If the check
passes, then he believes that the $\widehat{\text{dist}}$ labels were correct,
at least upto distance $D$ (by 5.1). Finally, he checks if fingerprints for
$B_{D}$ and $B_{D+1}$ match to verify that vertices in $V\setminus B_{D}$ are
indeed unreachable.

Error probability.

Verifier does $O(D)$ fingerprint-checks and $O(D)$ sum-checks, using
degree-$O(n)$ polynomials. Using $|\mathbb{F}|>n^{3}$ (and a union bound), the
soundness error is $<1/n$.

Help and verification costs.

The set of $\widehat{\text{dist}}$ labels sent by the Prover has size
$\tilde{O}(n)$. Each polynomial $\hat{p}_{d}$ has $nt$ monomials and each
$Q_{d}$ has $O(n)$ field elements, and hence, size $\tilde{O}(n)$. Therefore,
the total hcost is $\tilde{O}(Dnt)$. Initially, the $\tilde{A}$ and
$\tilde{b}_{1}$ values are stored using $\tilde{O}(s)$ space. Next, the
$\tilde{b}_{d}$ and $g_{d}$ values are maintained reusing space of $b_{d-1}$
and $g_{d-1}$ values respectively. We also use $O(1)$ many other fingerprints
that take $O(\log n)$ space each. Hence, the total vcost is $\tilde{O}(s)$.

######  Theorem 5.2.

There is a $[Dnt,s]$-scheme for unweighted SSSP, where $D=\max\limits_{v\in
V}\operatorname{dist}(v_{s},v)$.

######  Corollary 5.3.

There is a $[Knt,s]$-scheme for st-ShortestPath, where
$K=\operatorname{dist}(v_{s},v_{t})$.

###### Proof.

The protocol for SSSP incurs a factor of $D$ in the hcost since it constructs
$B_{d}$ for each $d\in[D]$. For the simpler st-ShortestPath problem, we can
inductively construct balls and stop as soon as we find the destination vertex
$v_{t}$ in some $B_{d}$ (i.e., get $\hat{q}_{d-1}(v_{t})\neq 0$). We must find
it in $B_{K}$ where $K$ is the length of a shortest $v_{s}$–$v_{t}$ path.
Thus, we will only incur a factor of $K$ in the hcost, which implies a
$[Knt,s]$-scheme for st-ShortestPath. ∎

Thus, we generalize the $[Dnt,s]$-scheme of Cormode et al. [CMT13] from st-
ShortestPath to SSSP. Our result for st-ShortestPath generalizes the
$[Kn,n]$-scheme of Chakrabarti and Ghosh [CG19] by giving a smooth tradeoff
and also improves upon the $[Dnt,s]$-scheme of Cormode et al. [CMT13], since
$K$ can be arbitrarily smaller than $D$.

###  5.2 Weighted SSSP

Here, we consider the general weighted version of SSSP and give schemes for
the problem in the vanilla streaming model as well as the turnstile weight
update model.

Turnstile weight update. Assume that the edge weights are positive integers.
Each stream update increments/decrements the weight of an edge. The _distance_
from vertex $u$ to vertex $v$ refers to the weight of the shortest path from
$u$ to $v$. Let $D$ be the longest distance from the source $s$ to any other
vertex reachable from it, and $W$ be the maximum weight of an edge.

Define

$\delta_{w}(X):={\prod\limits_{\begin{subarray}{c}w^{\prime}\in[W]\\\
w^{\prime}\neq
w\end{subarray}}(X-w^{\prime})}\bigg{/}{\prod\limits_{\begin{subarray}{c}w^{\prime}\in[W]\\\
w^{\prime}\neq w\end{subarray}}(w-w^{\prime})}\,.$

Let $A$ denote the adjacency matrix of the weighted graph $G$, i.e., $A(u,v)$
is the weight of the edge $(u,v)$. Let $B_{d}$ (resp. $N_{d}$) denote the set
of vertices at a distance of at most (resp. exactly) $d$ from the source
vertex $v_{s}$. Then,

$\displaystyle N_{d+1}=\left\\{u\in V\setminus B_{d}:\,p_{d}(u)\neq
0\right\\}\,,$ (18) $\displaystyle\text{where~{}~{}}p_{d}(U)=\sum_{v\in
B_{d}}\delta_{w(v)}(\tilde{A}(v,U))\text{~{}~{}and~{}~{}}w(v)=d+1-\operatorname{dist}[v]\,.$
(19)

Stream processing.

Verifier chooses $r\in_{R}\mathbb{F}$ and maintains $\tilde{A}(v,r)$ for all
$v$. He stores $B_{1}$ with $\text{dist}[v]$ labelled as $1$ for each $v\in
B_{1}$.

Help message processing and verification.

Prover sends polynomials $\hat{p}_{d}$ and claims that $\hat{p}_{d}\equiv
p_{d}$ for each $d\in[D]$. Verifier computes $B_{d}$ inductively for $d\in[D]$
as follows.

Assume that, for some $d\in[D-1]$, he has the set $B_{d}$ with
$\operatorname{dist}[v]$ labeled on each vertex $v\in B_{d}$; this holds
initially as he has stored $B_{1}$. He computes $p_{d}(r)$ using eq. 19 and
checks whether $\hat{p}_{d}(r)=p_{d}(r)$. If the check passes, he believes
that $\hat{p}_{d}\equiv p_{d}$ and evaluates $\hat{p}_{d}(u)$ for each $u\in
V\setminus B_{d}$ and constructs $N_{d+1}$ using eq. 18. Then, $B_{d+1}$ is
given by $N_{d+1}\uplus B_{d}$.

After $B_{D}$ is obtained, we get all vertices reachable from $s$ along with
their distances from $s$. Finally, Verifier checks if the other vertices are
indeed unreachable from $s$ by verifying that there is no cross-edge between
$B_{D}$ and $V\setminus B_{D}$, i.e., if $E\cap(B_{D}\times(V\setminus
B_{D}))=\varnothing$. (Intersection scheme, see Fact 1.3)

Error probability.

Verifier uses the same element $r$ for $O(D)$ invocations of the sum-check
protocol, where each application of the sum-check protocol is to a univariate
polynomial of degree $O(Wn)$. Choosing $|\mathbb{F}|>DWn^{2}$, the soundness
error for each invocation of the sum-check protocol is at most $1/(Dn)$.
Taking a union bound over all $O(D)$ invocations, we get that the total error
probability of the protocol is at most $O(1/n)$.

Help and verification costs

We have $\deg p_{d}=O(Wn)$ for each $d\in[D]$ and hence, hcost is
$\tilde{O}(DWn)$. Verifier needs to store all vertices and $\tilde{A}(v,r)$
for each $v\in[n]$, and hence, vcost is $\tilde{O}(n)$. The final disjointness
can be checked by an $[n,n]$ intersection scheme.

######  Theorem 5.4.

There is a $[DWn,n]$-scheme for SSSP in the turnstile weight update model.

Vanilla Stream. We now describe a protocol for SSSP in the model where the
edges arrive with their weights, without any further update on them. This is
the “vanilla” streaming model.

At the end of the stream, Prover sends the distances $\operatorname{dist}[v]$
and prev$[v]$— the parent of $v$ in the shortest path tree rooted at $s$—for
all $v\in V$. Verifier checks whether the edges and their weights implied by
this proof are correct, using a $[Wn,n]$ subset scheme. Thus, if Prover is
honest, we get the distance as well as shortest path from $s$ to each vertex.
But we also need to check that there is no path to any vertex shorter than the
ones claimed by Prover. We describe a protocol for this.

For $u,v\in V$ and $w\in[W]$, define the indicator function $f$ as
$f(u,v,w)=1$ iff $A(u,v)=w$. Let $\tilde{f}$ be the $\mathbb{F}$-extension of
$f$, for some large finite field $\mathbb{F}$.

Retain the definitions of $B_{d}$ and $N_{d}$ from last section with the
definition of the polynomial $p_{d}$ changed to

$p_{d}(U)=\sum_{v\in B_{d}}\tilde{f}(v,U,d+1-\text{dist}_{s}[v])$ (20)

Hence, it still holds that

$N_{d+1}=\left\\{u\in V\setminus B_{d}:p_{d}(u)\neq 0\right\\}\,.$ (21)

Stream processing.

The stream updates are of the form $(u,v,w)$ denoting that $A(u,v)=w$.
Verifier picks $r\in_{R}\mathbb{F}$ and maintains $\tilde{f}(v,r,w)$ for each
$v\in V$ and $w\in[W]$. He also stores the set $B_{1}$ with $\text{dist}_{s}$
labels set to $1$ for each vertex in the set.

Help message processing and verification.

This part is similar to the turnstile weight update protocol. Of course, this
time, the Verifier computes $p_{d}(r)$ using Equation 20.

Error probability.

Each polynomial $p_{d}$ has degree $O(n)$. Verifier does sum-checks for $O(D)$
such polynomials. Choosing $|\mathbb{F}|\gg Dn$, we can make the error
probability small by union bound.

Help and Verification costs.

Since the degree of each $p_{d}$ is at most $n$, the total hcost is
$\tilde{O}(Dn)$. Verifier stores $\tilde{f}(v,r,w)$ for each $v\in V$ and
$w\in[W]$, which requires $\tilde{O}(Wn)$ space. We also need to store all
vertices as we go on assigning the distance labels. Hence, the total vcost of
this protocol is $\tilde{O}(Wn)$.

######  Theorem 5.5.

There is a $[Dn,Wn]$-scheme for SSSP in the vanilla streaming model.

## References

  * [ACK19] Sepehr Assadi, Yu Chen, and Sanjeev Khanna.  Sublinear algorithms for ($\Delta$\+ 1) vertex coloring.  In Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 767–786, 2019.
  * [ADRV16] Amirali Abdullah, Samira Daruki, Chitradeep Dutta Roy, and Suresh Venkatasubramanian.  Streaming verification of graph properties.  In Proc. 27th International Symposium on Algorithms and Computation, pages 3:1–3:14, 2016.
  * [AGM12] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Analyzing graph structure via linear measurements.  In Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 459–467, 2012.
  * [AKL17] Sepehr Assadi, Sanjeev Khanna, and Yang Li.  On estimating maximum matching size in graph streams.  In Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1723–1742, 2017.
  * [ALM+98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy.  Proof verification and the hardness of approximation problems.  J. ACM, 45(3):501–555, 1998.  Preliminary version in Proc. 33rd Annual IEEE Symposium on Foundations of Computer Science, pages 14–23, 1992.
  * [AS98] Sanjeev Arora and Shmuel Safra.  Probabilistic checking of proofs: A new characterization of NP.  J. ACM, 45(1):70–122, 1998.  Preliminary version in Proc. 33rd Annual IEEE Symposium on Foundations of Computer Science, pages 2–13, 1992.
  * [BC17] Suman K. Bera and Amit Chakrabarti.  Towards Tighter Space Bounds for Counting Triangles and Other Substructures in Graph Streams.  In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), pages 11:1–11:14, 2017.
  * [BFL+06] Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Christian Sohler.  Counting triangles in data streams.  In Proc. 25th ACM Symposium on Principles of Database Systems, pages 253–262, 2006.
  * [BKS02] Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar.  Reductions in streaming algorithms, with an application to counting triangles in graphs.  In Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 623–632, 2002.
  * [BM08] J.A. Bondy and U.S.R Murty.  Graph Theory.  Springer Publishing Company, Incorporated, 1st edition, 2008.
  * [CCGT14] Amit Chakrabarti, Graham Cormode, Navin Goyal, and Justin Thaler.  Annotations for sparse data streams.  In Proc. 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 687–706, 2014.
  * [CCM+15] Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian.  Verifiable stream computation and Arthur-Merlin communication.  In Proc. 30th Annual IEEE Conference on Computational Complexity, pages 217–243, 2015.
  * [CCMT14] Amit Chakrabarti, Graham Cormode, Andrew McGregor, and Justin Thaler.  Annotations in data streams.  ACM Trans. Alg., 11(1):Article 7, 2014.
  * [CDK19] Graham Cormode, Jacques Dark, and Christian Konrad.  Independent sets in vertex-arrival streams.  In Proc. 46th International Colloquium on Automata, Languages and Programming, pages 45:1–45:14, 2019.
  * [CG19] Amit Chakrabarti and Prantar Ghosh.  Streaming verification of graph computations via graph structure.  In Proc. 33rd International Workshop on Randomization and Approximation Techniques in Computer Science, pages 70:1–70:20, 2019.
  * [CGMV20] Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, and Sofya Vorotnikova.  Vertex ordering problems in directed graph streams.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 1786–1802, 2020.
  * [CK15] Amit Chakrabarti and Sagar Kale.  Submodular maximization meets streaming: matchings, matroids, and more.  Math. Program., 154(1–2):225–247, 2015.  Preliminary version in Proc. 17th Conference on Integer Programming and Combinatorial Optimization, pages 210–221, 2014.
  * [CMT13] Graham Cormode, Michael Mitzenmacher, and Justin Thaler.  Streaming graph computations with a helpful advisor.  Algorithmica, 65(2):409–442, 2013.
  * [CTY11] Graham Cormode, Justin Thaler, and Ke Yi.  Verifying computations with streaming interactive proofs.  Proc. VLDB Endowment, 5(1):25–36, 2011.
  * [FHM+20] Alireza Farhadi, Mohammad Taghi Hajiaghayi, Tung Mai, Anup Rao, and Ryan A. Rossi.  Approximate maximum matching in random streams.  In Proc. 31st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1773–1785, 2020.
  * [FKM+08] Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang.  Graph distances in the data-stream model.  SIAM J. Comput., 38(6):1709–1727, 2008.  Preliminary version in Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 745–754, 2005.
  * [GKK12] Ashish Goel, Michael Kapralov, and Sanjeev Khanna.  On the communication and streaming complexity of maximum bipartite matching.  In Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 468–485, 2012.
  * [GR13] Tom Gur and Ran Raz.  Arthur–Merlin streaming complexity.  In Proc. 40th International Colloquium on Automata, Languages and Programming, pages 528–539, 2013.
  * [JG05] Hossein Jowhari and Mohammad Ghodsi.  New streaming algorithms for counting triangles in graphs.  In Computing and Combinatorics, pages 710–716. Springer Berlin Heidelberg, 2005.
  * [JSP13] Madhav Jha, C. Seshadhri, and Ali Pinar.  A space efficient streaming algorithm for triangle counting using the birthday paradox.  In Proc. 19th Annual SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 589–597, 2013.
  * [Kap13] Michael Kapralov.  Better bounds for matchings in the streaming model.  In Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1679–1697, 2013.
  * [KMNT20] Michael Kapralov, Slobodan Mitrovic, Ashkan Norouzi-Fard, and Jakab Tardos.  Space efficient approximation to maximum matching size from uniform edge samples.  In Proc. 31st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1753–1772, 2020.
  * [KMPT12] Mihail N. Kolountzakis, Gary L. Miller, Richard Peng, and Charalampos E. Tsourakakis.  Efficient triangle counting in large graphs via degree-based vertex partitioning.  Internet Mathematics, 8(1-2):161–185, 2012.
  * [KMPV19] John Kallaugher, Andrew McGregor, Eric Price, and Sofya Vorotnikova.  The complexity of counting cycles in the adjacency list streaming model.  In Proc. 38th ACM Symposium on Principles of Database Systems, pages 119–133, 2019.
  * [KMSS12] Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, and He Sun.  Counting arbitrary subgraphs in data streams.  In Automata, Languages, and Programming, pages 598–609. Springer Berlin Heidelberg, 2012.
  * [KP13] Hartmut Klauck and Ved Prakash.  Streaming computations with a loquacious prover.  In Proc. 4th Conference on Innovations in Theoretical Computer Science, pages 305–320, 2013.
  * [LFKN92] Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan.  Algebraic methods for interactive proof systems.  J. ACM, 39(4):859–868, 1992.
  * [McG05] Andrew McGregor.  Finding graph matchings in data streams.  In Proc. 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pages 170–181, 2005.
  * [MVV16] Andrew McGregor, Sofya Vorotnikova, and Hoa T. Vu.  Better algorithms for counting triangles in data streams.  In Proc. 35th ACM Symposium on Principles of Database Systems, pages 401–411, 2016.
  * [Sha92] Adi Shamir.  IP = PSPACE.  J. ACM, 39(4):869–877, 1992.
  * [Tha16a] Justin Thaler.  Data stream verification.  In Encyclopedia of Algorithms, pages 494–499. Springer Berlin Heidelberg, 2016.
  * [Tha16b] Justin Thaler.  Semi-streaming algorithms for annotated graph streams.  In Proc. 43rd International Colloquium on Automata, Languages and Programming, pages 59:1–59:14, 2016.
  * [TMD+05] Peter A. Tucker, David Maier, Lois M. L. Delcambre, Tim Sheard, Jennifer Widom, and Mark P. Jones.  Punctuated data streams, 2005.
  * [Wes01] Douglas B. West.  Introduction to Graph Theory.  Prentice Hall, 2nd edition, 2001.
  * [YLH+08] Ke Yi, Feifei Li, Marios Hadjieleftheriou, George Kollios, and Divesh Srivastava.  Randomized synopses for query assurance on data streams.  In Proc. 24th International Conference on Data Engineering, pages 416–425, 2008.


# Demonstration of Optimal Fixed-Point Quantum Search Algorithm in IBM Quantum
Computer

Kamal Gurnani1, Bikash K. Behera2, Prasanta K. Panigrahi2 1Department of
Physics, Indian Institute of Technology Kharagpur, Kharagpur 721302, India
2Department of Physical Sciences, Indian Institute of Science Education and
Research Kolkata, Mohanpur 741246, West Bengal, India

###### Abstract

Quantum search algorithm can be described as the rotation of state vectors in
a Hilbert space. The state vectors uniformly rotate by iterative sequences
until they hit the target position. To optimize the algorithm, it is necessary
to have the precise knowledge about some parameters like the number of target
positions. Here we demonstrate the implementation of optimal fixed-point
quantum search (OFPQS) algorithm in a five-qubit quantum computer developed by
IBM Corporation. We perform the OFPQS algorithm for one and two-iterations and
confirm the accuracy of our results by state tomography process.

Search Algorithm, OFPQS Algorithm, IBM Quantum Experience

##  I Introduction

Quantum versions of classical algorithms have always been a boon for the
typical problems which are encountered in various branches of computation and
information processing NCBook ; BennettNat2000  i.e. data security
ChildsQIP2005 ; DiamantiNatPhys2017 , cryptography EkertPRL1991 ; GisinPRL1991
; BennettPRL1992 , database handling MaitraETABA2017 , to name a few. Many of
these exploit the simple but crucial fact that in quantum theory, a
superposition of states can also exist at a time unlike classical domain where
only a single state (string of bits) can be represented at an instance.

Grovers’ search algorithm GroverPSP1996  for unsorted database is another
brilliant example of that. This algorithm comprising of the iterative
applications of the Grovers’ operator has a beautiful geometrical
understanding when the initial state being a superposition of all the states
present in the database is expressed in a 2-dimensional Hilbert space with the
orthogonal states are (a) superposition of unmarked or non-target states (b)
superposition of marked or target sates. Thus, Grover’s operator is a unitary
operator which serves to rotate the given initial state towards the target
state axis in this Hilbert space effectively increasing the amplitude of the
target state in the initial superposition.

This algorithm when applied within an unsorted database of N items having M
marked items, can perform the task in $\sqrt{N/M}$ applications of the
Grover’s operator, decomposition of which depends upon the requirement of
search problem. However, its usefulness is limited as a general problem
doesn’t come up with the known number of marked items without which the number
of iteration is unknown to us. This leads to us the souffle problem i.e. only
a few iterations leave the state mostly comprising of the unmarked states
while too many iterations cause the state vector to surpass the target state
in the assumed 2-D Hilbert space.

Souffle problem is dealt with using the fixed-point quantum search (FPQS)
algorithms which always increases the amplitude of the target state with each
iteration. One such FPQS algorithm is Grover’s $\pi/3$ algorithm. But these
algorithms lose the quadratic speed-up which is the astonishing and useful
feature of quantum algorithms.

Furthermore, Yoder _et al._ YoderPRL2014  developed another algorithm which
avoids the souffle problem with the quadratic speed up. This requires setting
the success probability with a bound over it in the form of a tunable
parameter $\delta$. In this case, we can achieve the quadratic speed-up as
well in our process. This algorithm, abbreviated as OFPQS (Optimal FPQS) has
been discussed in the Sec. II.

IBM Quantum Experience is widely used to perform different tasks in the field
of quantum computation and quantum information RundlePRA2017 ; GrimaldiSD2001
; KalraarXiv2017 ; GhosharXiv2017 ; GangopadhyayarXiv2017 ; MajumderarXiv2017
; LiarXiv2017 ; SisodiaarXiv201794 ; VishnuarXiv2017 ; GedikarXiv2017 ;
BKB6arXiv2017 ; BKB7arXiv2017 ; BKB9arXiv2017 ; SolanoQMQM2017 ;
HuffmanPRA2017 ; AlsinaPRA2016 ; WoottonQST2017 ; BertaNJP2016 ;
DeffnerHel2017 ; GarciaarXiv2017 . Experimental test of Hardy’s paradox
DasarXiv2017 , totpological quantum walks BaluarXiv2017 , quantum permutation
algorithm YalcinkayaarXiv2017  have been illustrated. Error correction with 15
qubit repetition code WoottonarXiv2017  and estimation of molecular ground
state energy KandalaNAT2017  have also been implemented using 16 qubit IBM
quantum computer, ibmqx5. Alvarez-Rodrigue _et al._ Solano2arXiv2017  have
shown artificial life in quantum technologies. Current trends like quantum
machine learning SchuldarXiv2017  has been performed on the quantum computer.
An essential ingredient of quantum communication, quantum repeater has been
designed by Behera _et al._ BKB8arXiv2017  using IBM quantum computer. One of
the important quantum mechanical problems, quantum tunneling BKB10arXiv2017
has been simulated on the universal quantum simulator, ibmqx4.

In this letter, we demonstrate the OFPQS algorithm in IBM Q Composer by taking
a uniform superposition of four 2 qubit states which has one target state in
it. We follow the circuit proposed by Yoder _et al._ YoderPRL2014 ;
BholePRA2016  with the oracle designed for the desired state. Due to the
limitations of space provided by IBM Q Composer, we have been able to perform
the task only for one and two iterations of the Grover’s operator.

This paper is organized as follows. In Sec. II, we briefly introduce the
mathematical formalism used in the design of the circuit. In Sec. III, we
discuss the oracle used in this OFPQS algorithm for the mentioned initial
state and the target state. Sec. IV comprises of the plots of the results
obtained from the IBM Q simulator and real quantum processor. We present the
results for one and two iterations of the Grover’s operator with a success
probability initially set to some value close to unity. In Sec. V, we compare
the results for both the cases and present the plausible reasons for the
noticeable differences.

##  II OFPQS Algorithm

Following are the steps to implement the aforementioned algorithm, for which
the quantum circuit for one iteration is depicted in Fig. 1. We choose the
lower bound on the success probability $P_{L}\geq 1-\delta^{2}=0.8$; $L$ is
$2l+1$ and $l$ is the number of Grover iterations.

Figure 1: The quantum circuit depicting one iteration of the OFPQS algorithm.
The boxes coloured red represent the Oracle and the green ones are used to
prepare the initial state $|++0\rangle$.

We make the corresponding circuits for $l=1$ and $2$ i.e. one and two
iterations. The value of $\alpha_{i}$ and $\beta_{i}$ are calculated using the
following relations:

$\alpha_{j}=-\beta_{l-j-1}=2\cot^{-1}(\tan(2\pi j/L)\sqrt{1-\gamma^{2}})$ (1)

where $j=1,2,3...$ and

$\gamma=T_{1/L}(1/\delta)$ (2)

where $T_{1/L}(x)=cos(Lcos^{-1}x)$ is the Lth Chebyshev polynomial of the
first kind.

Single Iteration: We put $l=1$ and $\delta=1/\sqrt{5}$ in Eq. (1). Thus, we
obtain the values:

$\alpha_{1}$=-$\beta_{1}$=4.4597

Double Iteration: We put $l=2$ and $\delta=1/\sqrt{5}$ in Eq. (1). Following
are the values of corresponding parameters:

$\alpha_{1}$=-$\beta_{2}$=1.7156

$\alpha_{2}$=-$\beta_{1}$=3.5443

##  III The Oracle

Our demonstration is for the equal superposition of $\ket{00}$, $\ket{01},$
$\ket{10}$ and $\ket{11}$ and we design our oracle to search the target state
$\ket{00}$. Our oracle U is such that
U$\ket{00}$$\ket{b}$=$\ket{00}$$\ket{b\oplus 1}$ where $\ket{b}$ is the
ancilla qubit. It is obvious that our oracle is nothing but a variant of the
Toffoli gate which works when both the control qubits are $\ket{0}$. A Toffoli
gate can be decomposed in terms of elementary single and two qubit gates
GarciaarXiv2017 .

It should be noted that the circuit which we have prepared in the IBM Q
Composer is the reversed version of what has been discussed in the letter. It
has been done so because the ibmqx4 processor allows C-NOT gate in only one
direction where the control qubit remains downwards and target qubit is
directed upwards. Hence we consider q[2] as our first qubit and q[1] as the
second qubit. Thus, q[0] serves the purpose of the ancilla qubit.

##  IV Experimental Procedures and Results

We first executed our circuits on the quantum simulator of the IBM Q Composer
and then run it on the actual quantum processor. Results in both the cases are
obtained by taking 8192 shots. As predicted, in both the cases, simulator
showed the results with the state $\ket{00}$ having the highest probability
(measurement basis-ZZ) which was more than 0.8 as we had set initially.
However, actual runs on quantum processors showed a noticeable difference from
the simulator results although they indeed had the highest probability for the
$\ket{00}$ state when measurement was performed in the ZZ basis. One more
aspect was that the deviation from the simulator results was more for two
Grover’s iterations than single iteration. The reason is that in case of two
iterations, more number of quantum gates are used and also the depth of the
quantum circuit is considerably higher than the single iteration case. Hence,
it is natural to have more errors in the later case as each gate introduces
some error in the system.

Quantum state tomography is performed to check the accuracy of the
experimentally prepared quantum states. Figs. 2 and 3 represent the
performance of the algorithm for one and two iterations respectively.

Figure 2: Case-I: One iteration (a) & (b) are the simulational real and
imaginary parts of the density matrix elements of the $|00\rangle$ state; (c)
& (d) are the experimentally reconstructed density matrix elements for the
$|00\rangle$ state. Figure 3: Case-II: Two iterations (a) & (b) are the
simulational real and imaginary parts of the density matrix elements of the
$|00\rangle$ state; (c) & (d) are the experimentally reconstructed density
matrix elements for the target state $|00\rangle$.

##  V Conclusion

To conclude, we have experimentally demonstrated here the optimal fixed-point
quantum search algorithm using the 5 qubit IBM quantum computer. We have
designed the equivalent quantum circuit for one and two iterations of the
algorithm in the real quantum processor ibmqx4. We have explicated the working
of quantum algorithm by fixing a target quantum state, which has been prepared
in our experiment. We have discussed some comments about the results obtained
in both the cases. The two iteration case involves a large number of gates
which introduce more noise and decoherence in the system. Hence, it is
experimentally observed that the target state in case of one iteration is
prepared with a more fidelity as compared to the two iteration case.

## References

  * (1) Nielsen, M. & Chuang, I.  Quantum Computation and Quantum Information.  _Cambridge University Press_ , (2000).
  * (2) Bennett, C. H. & DiVincenzo, D. V.  Quantum information and computation.  _Nature_ 404, 247-255(2000).
  * (3) Childs, A. M.  Secure assisted quantum computation.  _Nature_ 5, 456-466(2005).
  * (4) Diamanti, E. & Kashefi, E.  Best of both worlds.  _Nat. Phys._ 13, 3-4(2017).
  * (5) Ekert, A. K.  Quantum cryptography based on Bell’s theorem.  _Phys. Rev. Lett._ 67, 661(1991).
  * (6) Gisin, N., Ribordy, G., Tittel, W. & Zbinden, H.  Quantum cryptography.  _Rev. Mod. Phys._ 74, 145(2002).
  * (7) Bennett, C. H., Brassard, G. & Mermin, N. D.  Quantum cryptography without Bell’s theorem.  _Phys. Rev. Lett._ 68, 557(1992).
  * (8) Maitra, A., Maitra, S. & Pal, A. K.  Data Analytics in Quantum Paradigm: An Introduction.  _Emerg. Technol. Archit. Big-data Anal._ , 313-330(2017).
  * (9) Grover, L. K.  A fast quantum mechanical algorithm for database search.  _Proc. STOC ’96 Proc. twenty-eighth annu. ACM symp. Theor. comput._ , 212-219(1996).
  * (10) Yoder, T. J., Low, G. H. & Chuang, I. L.  Fixed-Point Quantum Search with an Optimal Number of Queries.  _Phys. Rev. Lett._ 113, 210501(2014).
  * (11) Rundle, R. P., Mills, P. W., Tilma, T., Samson, J. H. & Everitt, M. J.  Simple procedure for phase-space measurement and entanglement validation.  _Phys. Rev. A_ 96, 02217(2017).
  * (12) Grimaldi, D. & Marinov, M.  Distributed measurement systems.  _Measurement_ 30, 279-287(2001).
  * (13) Kalra, A. R., Prakash, S., Behera, B. K. & Panigrahi, P. K.  Experimental Demonstration of the No Hiding Theorem Using a 5 Qubit Quantum Computer.  _arXiv preprint arXiv:1707.09462_ , (2017).
  * (14) Ghosh, D., Agarwal, P., Pandey, P., Behera, B. K. & Panigrahi, P. K.  Automated Error Correction in IBM Quantum Computer and Explicit Generalization.  _arXiv preprint arXiv:1708.02297_ , (2017).
  * (15) Gangopadhyay, S., Manabputra, Behera, B. K. & Panigrahi, P. K.  Generalization and Partial Demonstration of an Entanglement Based Deutsch-Jozsa Like Algorithm Using a 5-Qubit Quantum Computer.  _arXiv preprint arXiv:1708.06375_ , (2017).
  * (16) Majumder, A., Mohapatra, S. & Kumar, A.  Experimental Realization of Secure Multiparty Quantum Summation Using Five-Qubit IBM Quantum Computer on Cloud.  _arXiv preprint arXiv:1707.07460_ , (2017).
  * (17) Li, R., Alvarez-Rodriguez, U., Lamata, L. & Solano, E.  Approximate Quantum Adders with Genetic Algorithms: An IBM Quantum Experience.  _arXiv preprint arXiv:1611.07851_ , (2017).
  * (18) Sisodia, M., Shukla, A., Thapliyal, K. & Pathak, A.  Design and experimental realization of an optimal scheme for teleportion of an n-qubit quantum state.  _arXiv preprint arXiv:1704.05294_ , (2017).
  * (19) Vishnu, P. K., Joy, D., Behera, B. K. & Panigrahi, P. K.  Experimental Demonstration of Non-local Controlled-Unitary Quantum Gates Using a Five-qubit Quantum Computer.  _arXiv preprint arXiv:1709.05697_ , (2017).
  * (20) Yalçinkaya, İ & Gedik, Z.  Optimization and experimental realization of quantum permutation algorithm.  _arXiv preprint arXiv:1708.07900_ , (2017).
  * (21) Dash, A., Rout, S., Behera, B. K. & Panigrahi, P. K.  A Verification Algorithm and Its Application to Quantum Locker in IBM Quantum Computer.  _arXiv preprint arXiv:1710.05196_ , (2017).
  * (22) Roy, S., Behera, B. K. & Panigrahi, P. K.  Demonstration of Entropic Noncontextual Inequality Using IBM Quantum Computer.  _arXiv preprint arXiv:1710.10717_ , (2017).
  * (23) Satyajit, S., Srinivasan, K., Behera, B. K. & Panigrahi, P. K.  Discrimination of Highly Entangled Z-states in IBM Quantum Computer.  _arXiv preprint arXiv:1712.05485_ , (2017).
  * (24) Li, R., Alvarez-Rodriguez, U., Lamata, L. & Solano, E.  Approximate Quantum Adders with Genetic Algorithms: An IBM Quantum Experience.  _Quantum Meas. Quantum Metrol._ 4, 1-7(2017).
  * (25) Huffman, E. & Mizel, A.  Violation of noninvasive macrorealism by a superconducting qubit: Implementation of a Leggett-Garg test that addresses the clumsiness loophole.  _Phys. Rev. A_ 95, 032131(2017).
  * (26) Alsina, D. & Latorre, J. I.  Experimental test of Mermin inequalities on a five-qubit quantum computer.  _Phys. Rev. A_ 94, 012314(2016).
  * (27) Wootton, J. R.  Demonstrating non-Abelian braiding of surface code defects in a five qubit experiment.  _Quantum Sci. Technol._ 2, 015006(2017).
  * (28) Berta, M., Wehner, S. & Wilde, M. M.  Entropic uncertainty and measurement reversibility.  _New J. Phys._ 18, 073004(2016).
  * (29) Deffner, S.  Demonstration of entanglement assisted invariance on IBM’s quantum experience.  _Heliyon_ 3, e00444(2016).
  * (30) García-Martín, D., & Sierra, G.  Five Experimental Tests on the 5-Qubit IBM Quantum Computer.  _arXiv preprint arXiv:1712.05642_ , (2017).
  * (31) Das, S., & Paul, G.  Experimental test of Hardy’s paradox on a five-qubit quantum computer.  _arXiv preprint arXiv:1712.04925_ , (2017).
  * (32) Balu, R., Castillo, D. & Siopsis, G.  Physical realization of topological quantum walks on IBM-Q and beyond.  _arXiv preprint arXiv:1710.03615_ , (2017).
  * (33) Yalçinkaya, İ. & Gedik, Z.  Optimization and experimental realization of quantum permutation algorithm.  _arXiv preprint arXiv:1708.07900_ , (2017).
  * (34) Wootton, J. R. & Loss, D.  A repetition code of 15 qubits.  _arXiv preprint arXiv:1709.00990_ , (2017).
  * (35) Kandala, A., Mezzacapo, A., Temme, K., Takita, M., Brink, M., Chow, J. M. & Gambetta, J. M.  Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets.  _Nature_ 549, 242-246(2017).
  * (36) Alvarez-Rodriguez, U., Sanz, M., Lamata, L., & Solano, E.  Artificial Life in Quantum Technologies.  _arXiv preprint arxiv:1505.03775_ , (2016).
  * (37) Schuld, M., Fingerhuth, M. & Petruccione, F.  Implementing a distance-based classifier with a quantum interference circuit.  _arXiv preprint arXiv:1703.10793_ , (2017).
  * (38) Behera, B. K., Seth, S., Das, A. & Panigrahi, P. K.  Experimental Demonstration of Quantum Repeater in IBM Quantum Computer.  _arXiv preprint arXiv:1712.00854_ , (2017).
  * (39) Hegade, N. N., Behera, B. K. & Panigrahi, P. K.  Experimental Demonstration of Quantum Tunneling in IBM Quantum Computer.  _arXiv preprint arXiv:1712.07326_ , (2017).
  * (40) Bhole, G., Anjusha, V. S. & Mahesh, T. S.  Steering quantum dynamics via bang-bang control: Implementing optimal fixed-point quantum search algorithm.  _Phys. Rev. A_ 93, 042339(2016).

Acknowledgements BKB acknowledges the support of DST Inspire Fellowship. We
are extremely grateful to IBM team and IBM Quantum Experience project.