Search algorithm on strongly regular graphs based on scattering quantum walk
- Publication Type:
- Journal Article
- Citation:
- Chinese Physics B, 2017, 26 (1)
- Issue Date:
- 2017-01-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| Xue_2017_Chinese_Phys._B_26_010301.pdf | Published Version | 713.55 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
© 2017 Chinese Physical Society and IOP Publishing Ltd. Janmark, Meyer, and Wong showed that continuous-time quantum walk search on known families of strongly regular graphs (SRGs) with parameters (N,k,λ,m) achieves full quantum speedup. The problem is reconsidered in terms of scattering quantum walk, a type of discrete-time quantum walks. Here, the search space is confined to a low-dimensional subspace corresponding to the collapsed graph of SRGs. To quantify the algorithms performance, we leverage the fundamental pairing theorem, a general theory developed by Cottrell for quantum search of structural anomalies in star graphs. The search algorithm on the SRGs with k scales as N satisfies the theorem, and results can be immediately obtained, while search on the SRGs with k scales as √N does not satisfy the theorem, and matrix perturbation theory is used to provide an analysis. Both these cases can be solved in O(√N) time steps with a success probability close to 1. The analytical conclusions are verified by simulation results on two SRGs. These examples show that the formalism on star graphs can be applied more generally.
Please use this identifier to cite or link to this item: