-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathref.bib
126 lines (117 loc) · 8.1 KB
/
ref.bib
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
@article{main,
title = {Noninteracting multiparticle quantum random walks applied to the graph isomorphism problem for strongly regular graphs},
author = {Rudinger, Kenneth and Gamble, John King and Wellons, Mark and Bach, Eric and Friesen, Mark and Joynt, Robert and Coppersmith, S. N.},
journal = {Phys. Rev. A},
volume = {86},
issue = {2},
pages = {022334},
numpages = {10},
year = {2012},
month = {Aug},
publisher = {American Physical Society},
doi = {10.1103/PhysRevA.86.022334},
url = {https://link.aps.org/doi/10.1103/PhysRevA.86.022334}
}
@article{main2,
title = {Two-particle quantum walks applied to the graph isomorphism problem},
author = {Gamble, John King and Friesen, Mark and Zhou, Dong and Joynt, Robert and Coppersmith, S. N.},
journal = {Phys. Rev. A},
volume = {81},
issue = {5},
pages = {052313},
numpages = {11},
year = {2010},
month = {May},
publisher = {American Physical Society},
doi = {10.1103/PhysRevA.81.052313},
url = {https://link.aps.org/doi/10.1103/PhysRevA.81.052313}
}
@ARTICLE{main3,
author = {{Rudinger}, Kenneth and {King Gamble}, John and {Bach}, Eric and {Friesen}, Mark and {Joynt}, Robert and {Coppersmith}, S.~N.},
title = "{Comparing algorithms for graph isomorphism using discrete- and continuous-time quantum random walks}",
journal = {arXiv e-prints},
keywords = {Quantum Physics},
year = 2012,
month = jul,
eid = {arXiv:1207.4535},
pages = {arXiv:1207.4535},
archivePrefix = {arXiv},
eprint = {1207.4535},
primaryClass = {quant-ph},
adsurl = {https://ui.adsabs.harvard.edu/abs/2012arXiv1207.4535R},
adsnote = {Provided by the SAO/NASA Astrophysics Data System}
}
@article{maha,
doi = {10.1088/1751-8113/48/26/265301},
url = {https://dx.doi.org/10.1088/1751-8113/48/26/265301},
year = {2015},
month = {jun},
publisher = {IOP Publishing},
volume = {48},
number = {26},
pages = {265301},
author = {A Mahasinghe and J A Izaac and J B Wang and J K Wijerathna},
title = {Phase-modified CTQW unable to distinguish strongly regular graphs efficiently},
journal = {Journal of Physics A: Mathematical and Theoretical},
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.}
}
@article{tama,
doi = {10.1088/1751-8113/47/32/325302},
url = {https://dx.doi.org/10.1088/1751-8113/47/32/325302},
year = {2014},
month = {jul},
publisher = {IOP Publishing},
volume = {47},
number = {32},
pages = {325302},
author = {Dario Tamascelli and Luca Zanetti},
title = {A quantum-walk-inspired adiabatic algorithm for solving graph isomorphism problems},
journal = {Journal of Physics A: Mathematical and Theoretical},
abstract = {We present a quantum algorithm for solving graph isomorphism problems that is based on an adiabatic protocol. We use a collection of continuous time quantum walks, each one generated by an XY Hamiltonian, to visit the configuration space. In this way we avoid a diffusion over all the possible configurations and significantly reduce the dimensionality of the accessible Hilbert space. Within this restricted space, the graph isomorphism problem can be translated into searching for a satisfying assignment to a 2-SAT (satisfiable) formula and mapped onto a 2-local Hamiltonian without resorting to perturbation gadgets or projective techniques. We present an analysis of the time for execution of the algorithm on small graph isomorphism problem instances and discuss the issue of an implementation of the proposed adiabatic scheme on current quantum computing hardware.}
}
@article{wang,
doi = {10.1088/1751-8113/48/11/115302},
url = {https://dx.doi.org/10.1088/1751-8113/48/11/115302},
year = {2015},
month = {feb},
publisher = {IOP Publishing},
volume = {48},
number = {11},
pages = {115302},
author = {Huiquan Wang and Junjie Wu and Xuejun Yang and Xun Yi},
title = {A graph isomorphism algorithm using signatures computed via quantum walk search model},
journal = {Journal of Physics A: Mathematical and Theoretical},
abstract = {In this paper, we propose a new algorithm based on a quantum walk search model to distinguish strongly similar graphs. Our algorithm computes a signature for each graph via the quantum walk search model and uses signatures to distinguish non-isomorphic graphs. Our method is less complex than those of previous works. In addition, our algorithm can be extended by raising the signature levels. The higher the level adopted, the stronger the distinguishing ability and the higher the complexity of the algorithm. Our algorithm was tested with standard benchmarks from four databases. We note that the weakest signature at level 1 can distinguish all similar graphs, with a time complexity of which that outperforms the previous best work except when it comes to strongly regular graphs (SRGs). Once the signature is raised to level 3, all SRGs tested can be distinguished successfully. In this case, the time complexity is , also better than the previous best work.}
}
@ARTICLE{proof,
author = {{Shiau}, Shiue-yuan and {Joynt}, Robert and {Coppersmith}, S.~N.},
title = "{Physically-motivated dynamical algorithms for the graph isomorphism problem}",
journal = {arXiv e-prints},
keywords = {Quantum Physics},
year = 2003,
month = dec,
eid = {quant-ph/0312170},
pages = {quant-ph/0312170},
archivePrefix = {arXiv},
eprint = {quant-ph/0312170},
primaryClass = {quant-ph},
adsurl = {https://ui.adsabs.harvard.edu/abs/2003quant.ph.12170S},
adsnote = {Provided by the SAO/NASA Astrophysics Data System}
}
@article{vf2,
title = {VF2++—An improved subgraph isomorphism algorithm},
journal = {Discrete Applied Mathematics},
volume = {242},
pages = {69-81},
year = {2018},
note = {Computational Advances in Combinatorial Optimization},
issn = {0166-218X},
doi = {https://doi.org/10.1016/j.dam.2018.02.018},
url = {https://www.sciencedirect.com/science/article/pii/S0166218X18300829},
author = {Alpár Jüttner and Péter Madarasi},
keywords = {Computational biology, Subgraph isomorphism problem},
abstract = {This paper presents a largely improved version of the VF2 algorithm for the Subgraph Isomorphism Problem. The improvements are twofold. Firstly, it is based on a new approach for determining the matching order of the nodes, and secondly, more efficient — nevertheless easier to compute — cutting rules are proposed. They together reduce the search space significantly. In addition to the usual Subgraph Isomorphism Problem, the paper also presents specialized algorithms for the Induced Subgraph Isomorphism and for the Graph Isomorphism Problems. Finally, an extensive experimental evaluation is provided using a wide range of inputs, including both real-life biological and chemical datasets and standard randomly generated graph series. The results show major and consistent running time improvements over the other known methods. The C++ implementations of the algorithms are available open-source as part of the LEMON graph and network optimization library.}
}
% Images
@misc{wiki, title={File:petersen1 tiny.svg}, url={https://en.wikipedia.org/wiki/Petersen_graph#/media/File:Petersen1_tiny.svg}, journal={Wikipedia}, publisher={Wikimedia Foundation}, year={2011}, month={May}}
@misc{wiki2, title={Graph isomorphism}, url={https://en.wikipedia.org/wiki/Graph_isomorphism}, journal={Wikipedia}, publisher={Wikimedia Foundation}, year={2022}, month={Nov}}