An Adiabatic Quantum Algorithm for Determining Gracefulness of A Graph
arXiv:1602.08860 · doi:10.1515/zna-2017-0011
Abstract
Graph labelling is one of the noticed contexts in combinatorics and graph theory. Graceful labelling for a graph with edges, is to label the vertices of with such that, if we specify to each edge the difference value between its two ends, then any of appears exactly once as an edge label. For a given graph, there is still few efficient classical algorithms that determines either it is graceful or not, even for trees - as a well-known class of graphs. In this paper, we introduce an adiabatic quantum algorithm, which for a graceful graph finds a graceful labelling. Also, this algorithm can determine if is not graceful. Numerical simulations of the algorithm reveal that its time complexity has a polynomial behaviour with the problem size up to the range of 15 qubits.
arXiv comment13 pages, 6 figures, 3 tables
References in corpus (11)
- Quantum Computing
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Robustness of adiabatic quantum computation
- A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation
- How Powerful is Adiabatic Quantum Computation?
- Quantitative conditions do not guarantee the validity of the adiabatic approximation
- Experimental determination of Ramsey numbers
- Ramsey numbers and adiabatic quantum computing
- Does Adiabatic Quantum Optimization Truly Fail for NP-complete problems?
- MAX 2-SAT with up to 108 qubits
- Graph isomorphism and adiabatic quantum computing