Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Expansion Testing using Quantum Fast-Forwarding and Seed Sets

Abstract : Expansion testing aims to decide whether an $n$-node graph has expansion at least $\Phi$, or is far from any such graph. We propose a quantum expansion tester with complexity $\widetilde{O}(n^{1/3}\Phi^{-1})$. This accelerates the $\widetilde{O}(n^{1/2}\Phi^{-2})$ classical tester by Goldreich and Ron [Algorithmica '02], and combines the $\widetilde{O}(n^{1/3}\Phi^{-2})$ and $\widetilde{O}(n^{1/2}\Phi^{-1})$ quantum speedups by Ambainis, Childs and Liu [RANDOM '11] and Apers and Sarlette [QIC '19], respectively. The latter approach builds on a quantum fast-forwarding scheme, which we improve upon by initially growing a seed set in the graph. To grow this seed set we borrow a so-called evolving set process from the graph clustering literature, which allows to grow an appropriately local seed set.
Complete list of metadata

https://hal.inria.fr/hal-02436647
Contributor : Simon Apers Connect in order to contact the contributor
Submitted on : Monday, January 13, 2020 - 11:43:23 AM
Last modification on : Wednesday, June 8, 2022 - 12:50:07 PM

Links full text

Identifiers

  • HAL Id : hal-02436647, version 1
  • ARXIV : 1907.02369

Collections

Citation

Simon Apers. Expansion Testing using Quantum Fast-Forwarding and Seed Sets. 2020. ⟨hal-02436647⟩

Share

Metrics

Record views

13