Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks

• URL: http://arxiv.org/abs/2206.02767v2
• Date: Mon, 26 Sep 2022 06:32:05 GMT
• Title: Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks
• Authors: Xudong Wu and Penghui Yao
• Abstract summary: This paper studies the complexity of computing the weighted diameter and radius of a graph in the quantum CONGEST model. We present a quantum algorithm that $widetilde Oleft(minleftn9/10D3/10,nrightright)$, where $D$ denotes the unweighted diameter.
• Score: 6.236743421605786
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies the round complexity of computing the weighted diameter and radius of a graph in the quantum CONGEST model. We present a quantum algorithm that $(1+o(1))$-approximates the diameter and radius with round complexity $\widetilde O\left(\min\left\{n^{9/10}D^{3/10},n\right\}\right)$, where $D$ denotes the unweighted diameter. This exhibits the advantages of quantum communication over classical communication since computing a $(3/2-\varepsilon)$-approximation of the diameter and radius in a classical CONGEST network takes $\widetilde\Omega(n)$ rounds, even if $D$ is constant [Abboud, Censor-Hillel, and Khoury, DISC '16]. We also prove a lower bound of $\widetilde\Omega(n^{2/3})$ for $(3/2-\varepsilon)$-approximating the weighted diameter/radius in quantum CONGEST networks, even if $D=\Theta(\log n)$. Thus, in quantum CONGEST networks, computing weighted diameter and weighted radius of graphs with small $D$ is strictly harder than unweighted ones due to Le Gall and Magniez's $\widetilde O\left(\sqrt{nD}\right)$-round algorithm for unweighted diameter/radius [PODC '18].

Related papers

• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  We study the estimation of relative entropy $D(rho|sigma)$ when $sigma$ is known. Our estimator attains the Cram'er-Rao type bound when the dimension $d$ is fixed.
  arXiv  Detail & Related papers  (2024-06-25T06:07:20Z)
• Quantum connection, charges and virtual particles [65.268245109828]
  A quantum bundle $L_hbar$ is endowed with a connection $A_hbar$ and its sections are standard wave functions $psi$ obeying the Schr"odinger equation. We will lift the bundles $L_Cpm$ and connection $A_hbar$ on them to the relativistic phase space $T*R3,1$ and couple them to the Dirac spinor bundle describing both particles and antiparticles.
  arXiv  Detail & Related papers  (2023-10-10T10:27:09Z)
• Unitarity estimation for quantum channels [7.323367190336826]
  Unitarity estimation is a basic and important problem in quantum device certification and benchmarking. We provide a unified framework for unitarity estimation, which induces ancilla-efficient algorithms. We show that both the $d$-dependence and $epsilon$-dependence of our algorithms are optimal.
  arXiv  Detail & Related papers  (2022-12-19T09:36:33Z)
• A Fourier Approach to Mixture Learning [46.995354373649675]
  We give an algorithm that efficiently learns the means in $d = O(log k/loglog k)$ dimensions under separation $d/sqrtlog k (modulo factors) Our results can be easily extended to learning mixtures of non-Gaussian distributions, under a mild condition on the Fourier spectrum of the distribution.
  arXiv  Detail & Related papers  (2022-10-05T17:35:46Z)
• A Framework for Distributed Quantum Queries in the CONGEST Model [0.0]
  We give a general framework for implementing quantum query algorithms in Quantum CONGEST. We generalize the protocol for the distributed Deutsch-Jozsa problem. We also give quantum speedups for the problems of cycle detection and computation.
  arXiv  Detail & Related papers  (2022-02-22T15:18:39Z)
• On quantum algorithms for the Schr\"odinger equation in the semi-classical regime [27.175719898694073]
  We consider Schr"odinger's equation in the semi-classical regime. Such a Schr"odinger equation finds many applications, including in Born-Oppenheimer molecular dynamics and Ehrenfest dynamics.
  arXiv  Detail & Related papers  (2021-12-25T20:01:54Z)
• Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
  We show that a given suboptimality $epsilon0$ is achieved master/workers networks in $Omegabig. We then propose algorithms matching the lower bounds either types of networks (up to log-overs) We assess effectiveness of the proposed algorithms on a robust logistic regression problem.
  arXiv  Detail & Related papers  (2021-07-22T14:25:16Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Quantum Distributed Complexity of Set Disjointness on a Line [3.2590610391507444]
  Set Disjointness on a Line is a variant of the Set Disjointness problem in a distributed computing scenario. We prove an unconditional lower bound of $widetildeOmegabig(sqrt[3]n d2+sqrtn, big)$ rounds for Set Disjointness on a Line with $d + 1$ processors.
  arXiv  Detail & Related papers  (2020-02-26T21:17:53Z)
• Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks [0.0]
  The computation of the diameter is one of the most central problems in distributed computation. We show a $tilde O(sqrtnD)$-round quantum distributed algorithm for exact diameter computation, where $D$ denotes the diameter. This shows a separation between the computational power of quantum and classical algorithms in the CONGEST model.
  arXiv  Detail & Related papers  (2018-04-09T11:24:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.