Related papers: Complexity of Eccentricities and All-Pairs Shortest Paths in the Quantum CONGEST Model

Complexity of Eccentricities and All-Pairs Shortest Paths in the Quantum CONGEST Model

URL: http://arxiv.org/abs/2206.02766v1
Date: Mon, 6 Jun 2022 17:42:37 GMT
Title: Complexity of Eccentricities and All-Pairs Shortest Paths in the Quantum CONGEST Model
Authors: ChengSheng Wang, Xudong Wu and Penghui Yao
Abstract summary: This paper investigates he dtistance parameters in the quantum CONGEST models and establishes almost linear lower bounds on eccentricities and APSP. Our results imply that there is not quantum speedup for these two problems.
Score: 5.279257531335345
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Computing the distance parameters of a network, including the diameter, radius, eccentricities and the all-pairs shortest paths (APSP) is a central problem in distributed computing. This paper investigates he dtistance parameters in the quantum CONGEST models and establishes almost linear lower bounds on eccentricities and APSP, which match the classical upper bounds. Our results imply that there is not quantum speedup for these two problems. In contrast with the diameter and radius, exchanging quantum messages is able to save the communication when the networks have low diameters [Le Gall and Magniez, PODC 2018]. We obtain the lower bounds via a reduction from the two-way quantum communication complexity of the set intersection [Razborov, Izvestiya Mathematics 2003].

Related papers

Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
We call this protocol bias-field digitizeddiabatic quantum optimization (BF-DCQO) Our purely quantum approach eliminates the dependency on classical variational quantum algorithms. It achieves scaling improvements in ground state success probabilities, increasing by up to two orders of magnitude.
arXiv Detail & Related papers (2024-05-22T18:11:42Z)
Characterizing randomness in parameterized quantum circuits through expressibility and average entanglement [39.58317527488534]
Quantum Circuits (PQCs) are still not fully understood outside the scope of their principal application. We analyse the generation of random states in PQCs under restrictions on the qubits connectivities. We place a connection between how steep is the increase on the uniformity of the distribution of the generated states and the generation of entanglement.
arXiv Detail & Related papers (2024-05-03T17:32:55Z)
Efficient Quantum Circuits based on the Quantum Natural Gradient [0.0]
Efficient preparation of arbitrary entangled quantum states is crucial for quantum computation. We propose symmetry-conserving modified quantum approximate optimization algorithm(SCom-QAOA) circuits. The proposed scheme enlarges the set of the initial states accessible for variational quantum algorithms and widens the scope of investigation of non-equilibrium phenomena in quantum simulators.
arXiv Detail & Related papers (2023-10-16T16:08:57Z)
Instantaneous nonlocal quantum computation and circuit depth reduction [7.148511452018054]
Two-party quantum computation is a computation process with bipartite input and output, in which there are initial shared entanglement. In the first part, we show that a particular simplified subprocedure, known as a garden-hose gadget, cannot significantly reduce the entanglement cost. In the second part, we show that any unitary circuit consisting of layers of Clifford gates and T gates can be implemented using a circuit with measurements of depth proportional to the T-depth of the original circuit.
arXiv Detail & Related papers (2023-06-15T17:57:50Z)
High-fidelity parallel entangling gates on a neutral atom quantum computer [41.74498230885008]
We report the realization of two-qubit entangling gates with 99.5% fidelity on up to 60 atoms in parallel. These advances lay the groundwork for large-scale implementation of quantum algorithms, error-corrected circuits, and digital simulations.
arXiv Detail & Related papers (2023-04-11T18:00:04Z)
Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z)
Quantum-inspired optimization for wavelength assignment [51.55491037321065]
We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem. Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
arXiv Detail & Related papers (2022-11-01T07:52:47Z)
Cavity-enhanced quantum network nodes [0.0]
A future quantum network will consist of quantum processors that are connected by quantum channels. I will describe how optical resonators facilitate quantum network nodes.
arXiv Detail & Related papers (2022-05-30T18:50:35Z)
Shortcuts to Quantum Approximate Optimization Algorithm [2.150418646956503]
We propose a new ansatz dubbed as "Shortcuts to QAOA" (S-QAOA) S-QAOA provides shortcuts to the ground state of target Hamiltonian by including more two-body interactions and releasing the parameter freedoms. Considering the MaxCut problem and Sherrington-Kirkpatrick (SK) model, numerically shows the YY interaction has the best performance.
arXiv Detail & Related papers (2021-12-21T02:24:19Z)
Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks. Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
arXiv Detail & Related papers (2021-06-11T18:00:09Z)

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