Quantum algorithms for graph problems with cut queries

Lee, T; Santha, M; Zhang, S

Quantum algorithms for graph problems with cut queries

Lee, T

Santha, M Zhang, S

Permalink

Publication Type:: Journal Article
Citation:: 2020
Issue Date:: 2020-07-16

Recently Added

	Filename	Description	Size
	2007.08285v2.pdf	Accepted Manuscript	444.86 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is new to OPUS and is not currently available.

Full metadata record

Field	Value	Language
dc.contributor.author	Lee, T https://orcid.org/0000-0001-6912-2338
dc.contributor.author	Santha, M
dc.contributor.author	Zhang, S
dc.date.accessioned	2021-05-18T05:21:10Z
dc.date.available	2021-05-18T05:21:10Z
dc.date.issued	2020-07-16
dc.identifier.citation	2020
dc.identifier.uri	http://hdl.handle.net/10453/148939
dc.description.abstract	Let $G$ be an $n$-vertex graph with $m$ edges. When asked a subset $S$ of vertices, a cut query on $G$ returns the number of edges of $G$ that have exactly one endpoint in $S$. We show that there is a bounded-error quantum algorithm that determines all connected components of $G$ after making $O(\log(n)^6)$ many cut queries. In contrast, it follows from results in communication complexity that any randomized algorithm even just to decide whether the graph is connected or not must make at least $\Omega(n/\log(n))$ many cut queries. We further show that with $O(\log(n)^8)$ many cut queries a quantum algorithm can with high probability output a spanning forest for $G$. En route to proving these results, we design quantum algorithms for learning a graph using cut queries. We show that a quantum algorithm can learn a graph with maximum degree $d$ after $O(d \log(n)^2)$ many cut queries, and can learn a general graph with $O(\sqrt{m} \log(n)^{3/2})$ many cut queries. These two upper bounds are tight up to the poly-logarithmic factors, and compare to $\Omega(dn)$ and $\Omega(m/\log(n))$ lower bounds on the number of cut queries needed by a randomized algorithm for the same problems, respectively. The key ingredients in our results are the Bernstein-Vazirani algorithm, approximate counting with "OR queries", and learning sparse vectors from inner products as in compressed sensing.
dc.language	en
dc.rights	info:eu-repo/semantics/restrictedAccess
dc.title	Quantum algorithms for graph problems with cut queries
dc.type	Journal Article
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	recently_added	*
dc.date.updated	2021-05-18T05:21:08Z

Abstract:

Let $G$ be an $n$-vertex graph with $m$ edges. When asked a subset $S$ of vertices, a cut query on $G$ returns the number of edges of $G$ that have exactly one endpoint in $S$. We show that there is a bounded-error quantum algorithm that determines all connected components of $G$ after making $O(\log(n)^6)$ many cut queries. In contrast, it follows from results in communication complexity that any randomized algorithm even just to decide whether the graph is connected or not must make at least $\Omega(n/\log(n))$ many cut queries. We further show that with $O(\log(n)^8)$ many cut queries a quantum algorithm can with high probability output a spanning forest for $G$. En route to proving these results, we design quantum algorithms for learning a graph using cut queries. We show that a quantum algorithm can learn a graph with maximum degree $d$ after $O(d \log(n)^2)$ many cut queries, and can learn a general graph with $O(\sqrt{m} \log(n)^{3/2})$ many cut queries. These two upper bounds are tight up to the poly-logarithmic factors, and compare to $\Omega(dn)$ and $\Omega(m/\log(n))$ lower bounds on the number of cut queries needed by a randomized algorithm for the same problems, respectively. The key ingredients in our results are the Bernstein-Vazirani algorithm, approximate counting with "OR queries", and learning sparse vectors from inner products as in compressed sensing.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/148939