Home

@article{Wang:20,

title = {Experimental realization of continuous-time quantum walks on directed graphs and their application in PageRank},

author = {Kunkun Wang and Yuhao Shi and Lei Xiao and Jingbo Wang and Yogesh N Joglekar and Peng Xue},

url = {http://www.osapublishing.org/optica/abstract.cfm?URI=optica-7-11-1524},

doi = {10.1364/OPTICA.396228},

year  = {2020},

date = {2020-11-01},

urldate = {2020-11-01},

journal = {Optica (IF 11.104)},

volume = {7},

number = {11},

pages = {1524--1530},

publisher = {OSA},

abstract = {PageRank is an algorithm used by Google Search to rank web pages in their search engine results. An important step for quantum networks is to quantize the classical protocol as quantum mechanics provides computational resources that can be used to outperform classical algorithms. In this paper, we experimentally realize continuous-time quantum walks for directed graphs with non-Hermitian adjacency matrices by using linear optical circuits and single photons. We find that the node classical centrality in a directed graph is correlated with the maximum node probability resulting from a continuous-time quantum walk and then demonstrate PageRank. Our work opens up an avenue of applications of quantum information in real-life tasks.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Schofield2020,

title = {Quantum walk inspired algorithm for graph similarity and isomorphism},

author = {Callum Schofield and Jingbo B Wang and Yuying Li},

url = {https://doi.org/10.1007/s11128-020-02758-7},

doi = {10.1007/s11128-020-02758-7},

issn = {1573-1332},

year  = {2020},

date = {2020-08-24},

urldate = {2020-08-24},

journal = {Quantum Information Processing (IF 2.349)},

volume = {19},

number = {9},

pages = {281},

abstract = {Large-scale complex systems, such as social networks, electrical power grid, database structure, consumption pattern or brain connectivity, are often modelled using network graphs. Valuable insight can be gained by measuring similarity between network graphs in order to make quantitative comparisons. Since these networks can be very large, scalability and efficiency of the algorithm are key concerns. More importantly, for graphs with unknown labelling, this graph similarity problem requires exponential time to solve using existing algorithms. In this paper, we propose a quantum walk inspired algorithm, which provides a solution to the graph similarity problem without prior knowledge on graph labelling. This algorithm is capable of distinguishing between minor structural differences, such as between strongly regular graphs with the same parameters. The algorithm has a polynomial complexity, scaling with $$O(n^9)$$O(n9).},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{PhysRevResearch.2.023302,

title = {Combinatorial optimization via highly efficient quantum walks},

author = {S Marsh and J B Wang},

url = {https://link.aps.org/doi/10.1103/PhysRevResearch.2.023302},

doi = {10.1103/PhysRevResearch.2.023302},

year  = {2020},

date = {2020-06-01},

journal = {Phys. Rev. Research},

volume = {2},

pages = {023302},

publisher = {American Physical Society},

abstract = {We present a highly efficient quantum circuit for performing continuous time quantum walks (CTQWs) over an exponentially large set of combinatorial objects, provided that the objects can be indexed efficiently. CTQWs form the core mixing operation of a generalized version of the quantum approximate optimization algorithm, which works by “steering” the quantum amplitude into high-quality solutions. The efficient quantum circuit holds the promise of finding high-quality solutions to certain classes of NP-hard combinatorial problems such as the Travelling Salesman Problem, maximum set splitting, graph partitioning, and lattice path optimization.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{cmc.2020.010001,

title = {The Quantum Approximate Algorithm for Solving Traveling Salesman Problem},

author = {Yue Ruan and Samuel Marsh and Xilin Xue and Zhihao Liu and Jingbo Wang},

url = {http://www.techscience.com/cmc/v63n3/38872},

doi = {10.32604/cmc.2020.010001},

issn = {1546-2226},

year  = {2020},

date = {2020-01-01},

urldate = {2020-01-01},

journal = {Computers, Materials & Continua (IF 3.772)},

volume = {63},

number = {3},

pages = {1237--1247},

abstract = {The Quantum Approximate Optimization Algorithm (QAOA) is an 

algorithmic framework for finding approximate solutions to combinatorial optimization 

problems. It consists of interleaved unitary transformations induced by two operators 

labelled the mixing and problem Hamiltonians. To fit this framework, one needs to 

transform the original problem into a suitable form and embed it into these two 

Hamiltonians. In this paper, for the well-known NP-hard Traveling Salesman Problem 

(TSP), we encode its constraints into the mixing Hamiltonian rather than the conventional 

approach of adding penalty terms to the problem Hamiltonian. Moreover, we map edges 

(routes) connecting each pair of cities to qubits, which decreases the search space 

significantly in comparison to other approaches. As a result, our method can achieve a 

higher probability for the shortest round-trip route with only half the number of qubits 

consumed compared to IBM Q’s approach. We argue the formalization approach 

presented in this paper would lead to a generalized framework for finding, in the context 

of QAOA, high-quality approximate solutions to NP optimization problems.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Jay2020,

title = {A systematic method to building Dirac quantum walks coupled to electromagnetic fields},

author = {Gareth Jay and Fabrice Debbasch and Jingbo Wang},

doi = {10.1007/s11128-020-02933-w},

year  = {2020},

date = {2020-01-01},

urldate = {2020-01-01},

journal = {Quantum Information Processing (IF 2.349)},

volume = {19},

pages = {422},

abstract = {A quantum walk whose continuous limit coincides with Dirac equation is usually called a Dirac quantum walk (DQW). A new systematic method to build DQWs coupled to electromagnetic (EM) fields is introduced and put to test on several examples of increasing difficulty. It is first used to derive the EM coupling of a 3D walk on the cubic lattice. Recently introduced DQWs on the triangular lattice are then re-derived, showing for the first time that these are the only DQWs that can be defined with spinors living on the vertices of these lattices. As a third example of the method’s effectiveness, a new 3D walk on a parallelepiped lattice is derived. As a fourth, negative example, it is shown that certain lattices like the rhombohedral lattice cannot be used to build DQWs. The effect of changing representation in the Dirac equation is also discussed. Furthermore, we show the simulation of the established DQWs can be efficiently implemented on a quantum computer.

},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Chiew2019,

title = {Graph comparison via nonlinear quantum search},

author = {M Chiew and K de Lacy and C H Yu and S Marsh and J B Wang},

url = {https://doi.org/10.1007/s11128-019-2407-2},

doi = {10.1007/s11128-019-2407-2},

issn = {1573-1332},

year  = {2019},

date = {2019-08-20},

urldate = {2019-08-20},

journal = {Quantum Information Processing (IF 2.349)},

volume = {18},

number = {10},

pages = {302},

abstract = {Graph comparison is an established NP-hard problem. In this paper, we present an efficiently scaling quantum algorithm which finds the size of the maximum common edge subgraph for any pair of unlabelled graphs and thus provides a meaningful measure of graph similarity. The algorithm makes use of a two-part quantum dynamic process: in the first part, we obtain information crucial for the comparison of two graphs through linear quantum computation. However, this information is hidden in the quantum system with such a vanishingly small amplitude that even quantum algorithms such as Grover's search are not fast enough to distil it efficiently. In order to extract the information, we call upon techniques in nonlinear quantum computing to provide the speed-up necessary for an efficient algorithm. The linear quantum circuit requires $$backslashmathcal O(n^3 backslashlog ^3 (n) backslashlog backslashlog (n))$$O(n3log3(n)loglog(n))elementary quantum gates, and the nonlinear evolution under the Gross--Pitaevskii equation has a time scaling of $$backslashmathcal O(backslashfrac1g n^2 backslashlog ^3 (n) backslashlog backslashlog (n))$$O(1gn2log3(n)loglog(n)), where n is the number of vertices in each graph and g is the strength of the Gross--Pitaevskii nonlinearity. Through this example, we demonstrate the power of nonlinear quantum search techniques to solve a subset of NP-hard problems.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Yu2019,

title = {Quantum data compression by principal component analysis},

author = {Chao-Hua Yu and Fei Gao and Song Lin and Jingbo Wang},

url = {https://doi.org/10.1007/s11128-019-2364-9},

doi = {10.1007/s11128-019-2364-9},

issn = {1573-1332},

year  = {2019},

date = {2019-07-01},

urldate = {2019-07-01},

journal = {Quantum Information Processing (IF 2.349)},

volume = {18},

number = {8},

pages = {249},

abstract = {Data compression can be achieved by reducing the dimensionality of high-dimensional but approximately low-rank datasets, which may in fact be described by the variation of a much smaller number of parameters. It often serves as a preprocessing step to surmount the curse of dimensionality and to gain efficiency, and thus it plays an important role in machine learning and data mining. In this paper, we present a quantum algorithm that compresses an exponentially large high-dimensional but approximately low-rank dataset in quantum parallel, by dimensionality reduction (DR) based on principal component analysis (PCA), the most popular classical DR algorithm. We show that the proposed algorithm has a runtime polylogarithmic in the dataset's size and dimensionality, which is exponentially faster than the classical PCA algorithm, when the original dataset is projected onto a polylogarithmically low-dimensional space. The compressed dataset can then be further processed to implement other tasks of interest, with significantly less quantum resources. As examples, we apply this algorithm to reduce data dimensionality for two important quantum machine learning algorithms, quantum support vector machine and quantum linear regression for prediction. This work demonstrates that quantum machine learning can be released from the curse of dimensionality to solve problems of practical importance.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Sett2019,

title = {Zero transfer in continuous-time quantum walks},

author = {A Sett and H Pan and P E Falloon and J B Wang},

url = {https://doi.org/10.1007/s11128-019-2267-9},

doi = {10.1007/s11128-019-2267-9},

issn = {1573-1332},

year  = {2019},

date = {2019-04-10},

urldate = {2019-04-10},

journal = {Quantum Information Processing (IF 2.349)},

volume = {18},

number = {5},

pages = {159},

abstract = {In this paper, we show how using complex-valued edge weights in a graph can completely suppress the flow of probability amplitude in a continuous-time quantum walk to specific vertices of the graph when the edge weights, graph topology, and initial state of the quantum walk satisfy certain conditions. The conditions presented in this paper are derived from the so-called chiral quantum walk, a variant of the continuous-time quantum walk which incorporates directional bias with respect to site transfer probabilities between vertices of a graph by using complex edge weights. We examine the necessity to break the time-reversal symmetry in order to achieve zero transfer in continuous-time quantum walks. We also consider the effect of decoherence on zero transfer and suggest that this phenomenon may be used to detect and quantify decoherence in the system.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}