Source author record

Tijn de Vos

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms quant-ph

Catalog footprint

Research overview

3works

2topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A Framework for Distributed Quantum Queries in the CONGEST Model

The Quantum CONGEST model is a variant of the CONGEST model, where messages consist of $O(\log(n))$ qubits. We give a general framework for implementing quantum query algorithms in Quantum CONGEST, using the concept of parallel-queries. We apply our framework for distributed quantum queries in two settings: when data is distributed over the network, and graph theoretical problems where the network defines the input. The first is slightly unusual in CONGEST but our results follow almost directly. The second is more traditional for the CONGEST model but here we require some classical CONGEST steps to get our results. In the setting with distributed data, we show how a network can schedule a meeting in one of $k$ dates using $\tilde{O}(\sqrt{kD}+D)$ rounds, with $D$ the network diameter. We also give an algorithm for element distinctness: if all nodes together hold a list of $k$ numbers, they can find a duplicate in $\tilde O(k^{2/3}D^{1/3}+D)$ rounds. We also generalize the protocol for the distributed Deutsch-Jozsa problem from the two-party setting considered in [arXiv:quant-ph/9802040] to general networks, giving a novel separation between exact classical and exact quantum protocols in CONGEST. When the input is the network structure itself, we almost directly recover the $O(\sqrt{nD})$ round diameter computation algorithm of Le Gall and Magniez [arXiv:1804.02917]. We also compute the radius in the same number of rounds, and give an $ε$ -additive approximation of the average eccentricity in $\tilde{O}(D+D^{3/2}/ε)$ rounds. Finally, we give quantum speedups for the problems of cycle detection and girth computation. We detect whether a graph has a cycle of length at most $k$ in $O(k+(kn)^{1/2-1/Θ(k)})$ rounds. For girth computation we give an $\tilde{O}(g+(gn)^{1/2-1/Θ(g)})$ round algorithm for graphs with girth $g$ , beating the known classical lower bound.

preprint2022arXiv

Faster Cut Sparsification of Weighted Graphs

A cut sparsifier is a reweighted subgraph that maintains the weights of the cuts of the original graph up to a multiplicative factor of $(1\pmε)$ . This paper considers computing cut sparsifiers of weighted graphs of size $O(n\log (n)/ε^2)$ . Our algorithm computes such a sparsifier in time $O(m\cdot\min(α(n)\log(m/n),\log (n)))$ , both for graphs with polynomially bounded and unbounded integer weights, where $α(\cdot)$ is the functional inverse of Ackermann's function. This improves upon the state of the art by Benczúr and Karger (SICOMP 2015), which takes $O(m\log^2 (n))$ time. For unbounded weights, this directly gives the best known result for cut sparsification. Together with preprocessing by an algorithm of Fung et al. (SICOMP 2019), this also gives the best known result for polynomially-weighted graphs. Consequently, this implies the fastest approximate min-cut algorithm, both for graphs with polynomial and unbounded weights. In particular, we show that it is possible to adapt the state of the art algorithm of Fung et al. for unweighted graphs to weighted graphs, by letting the partial maximum spanning forest (MSF) packing take the place of the Nagamochi-Ibaraki (NI) forest packing. MSF packings have previously been used by Abraham at al. (FOCS 2016) in the dynamic setting, and are defined as follows: an $M$ -partial MSF packing of $G$ is a set $\mathcal{F}=\{F_1, \dots, F_M\}$ , where $F_i$ is a maximum spanning forest in $G\setminus \bigcup_{j=1}^{i-1}F_j$ . Our method for computing (a sufficient estimation of) the MSF packing is the bottleneck in the running time of our sparsification algorithm.

preprint2022arXiv

The Laplacian Paradigm in the Broadcast Congested Clique

In this paper, we bring the main tools of the Laplacian paradigm to the Broadcast Congested Clique. We introduce an algorithm to compute spectral sparsifiers in a polylogarithmic number of rounds, which directly leads to an efficient Laplacian solver. Based on this primitive, we consider the linear program solver of Lee and Sidford (FOCS 2014). We show how to solve certain linear programs up to additive error $ε$ with $n$ constraints on an $n$ -vertex Broadcast Congested Clique network in $\tilde O(\sqrt{n}\log(1/ε))$ rounds. Using this, we show how to find an exact solution to the minimum cost flow problem in $\tilde O(\sqrt{n})$ rounds.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Tijn de Vos

Research overview

Is this your work?

3 publications

A Framework for Distributed Quantum Queries in the CONGEST Model

Faster Cut Sparsification of Weighted Graphs

The Laplacian Paradigm in the Broadcast Congested Clique

See the researcher in context

Building this map preview