Abstract
Various quantum walk-based algorithms have been developed, aiming to distinguish non-isomorphic graphs with polynomial scaling, within both the discrete-time quantum walk (DTQW) and continuous-time quantum walk (CTQW) frameworks. Whilst both the single-particle DTQW and CTQW have failed to distinguish non-isomorphic strongly regular graph families (prompting the move to multi-particle graph isomorphism (GI) algorithms), the single-particle DTQW has been successfully modified by the introduction of a phase factor to distinguish a wide range of graphs in polynomial time. In this paper, we prove that an analogous phase modification to the single particle CTQW does not have the same distinguishing power as its discrete-time counterpart, in particular it cannot distinguish strongly regular graphs with the same family parameters with the same efficiency.
Original language | English |
---|---|
Article number | 265301 |
Pages (from-to) | 1-13 |
Number of pages | 13 |
Journal | Journal of Physics A: Mathematical and Theoretical |
Volume | 48 |
Issue number | 26 |
DOIs | |
Publication status | Published - 3 Jul 2015 |
Externally published | Yes |
Keywords
- graph isomorphism
- phase addition
- quantum walk