.png){kind=icon}
返回
Expansion Testing using Quantum Fast-Forwarding and Seed Sets
.png){kind=icon}
OA
AI
DOI：10.22331/q-2020-09-16-323.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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 (O) over tilde (n(1/3)Phi(-1)). This accelerates the (O) over tilde (n(1/2)Phi(-2)) classical tester by Goldreich and Ron [Algorithmica '02], and combines the (O) over tilde (n(1/3)Phi(-2)) and (O) over tilde (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 use a so-called evolving set process from the graph clustering literature, which allows to grow an appropriately local seed set.
期刊
IF:
5.4
论文数:
974
被引数:
1.0W
机构
引用论文
.png){kind=icon}
分享收藏分享收藏
查看更多内容