Home

@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}

}

@article{PhysRevA.99.032113,

title = {Dirac quantum walks on triangular and honeycomb lattices},

author = {Gareth Jay and Fabrice Debbasch and J B Wang},

url = {https://link.aps.org/doi/10.1103/PhysRevA.99.032113},

doi = {10.1103/PhysRevA.99.032113},

year  = {2019},

date = {2019-03-01},

urldate = {2019-03-01},

journal = {Physical Review A (IF 3.140)},

volume = {99},

pages = {032113},

publisher = {American Physical Society},

abstract = {In this paper, we present a detailed study on discrete-time Dirac quantum walks (DQWs) on triangular and honeycomb lattices. At the continuous limit, these DQWs coincide with the Dirac equation. Their differences in the discrete regime are analyzed through the dispersion relations, with special emphasis on Zitterbewegung. An extension which couples these walks to arbitrary discrete electromagnetic field is also proposed and the resulting Bloch oscillations are discussed.

},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{PhysRevA.99.022301,

title = {Quantum algorithm for visual tracking},

author = {Chao-Hua Yu and Fei Gao and Chenghuan Liu and Du Huynh and Mark Reynolds and Jingbo Wang},

url = {https://link.aps.org/doi/10.1103/PhysRevA.99.022301},

doi = {10.1103/PhysRevA.99.022301},

year  = {2019},

date = {2019-02-01},

urldate = {2019-02-01},

journal = {Physical Review A (IF 3.140)},

volume = {99},

pages = {022301},

publisher = {American Physical Society},

abstract = {Visual tracking (VT) is the process of locating a moving object of interest in a video. It is a fundamental problem in computer vision, with various applications in human-computer interaction, security and surveillance, robot perception, traffic control, etc. In this paper, we address this problem for the first time in the quantum setting, and present a quantum algorithm for VT based on the framework proposed by Henriques et al. [IEEE Trans. Pattern Anal. Mach. Intell., 7, 583 (2015)]. Our algorithm comprises two phases: training and detection. In the training phase, in order to discriminate the object and background, the algorithm trains a ridge regression classifier in the quantum state form where the optimal fitting parameters of ridge regression are encoded in the amplitudes. In the detection phase, the classifier is then employed to generate a quantum state whose amplitudes encode the responses of all the candidate image patches. The algorithm is shown to be polylogarithmic in scaling, when the image data matrices have low condition numbers, and therefore may achieve exponential speedup over the best classical counterpart. However, only quadratic speedup can be achieved when the algorithm is applied to implement the ultimate task of Henriques's framework, i.e., detecting the object position. We also discuss two other important applications related to VT: (1) object disappearance detection and (2) motion behavior matching, where much more significant speedup over the classical methods can be achieved. This work demonstrates the power of quantum computing in solving computer vision problems.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Marsh2019,

title = {A quantum walk-assisted approximate algorithm for bounded NP optimisation problems},

author = {S Marsh and J B Wang},

url = {https://doi.org/10.1007/s11128-019-2171-3},

doi = {10.1007/s11128-019-2171-3},

issn = {1573-1332},

year  = {2019},

date = {2019-01-16},

urldate = {2019-01-16},

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

volume = {18},

number = {3},

pages = {61},

abstract = {This paper describes an application of the quantum approximate optimisation algorithm (QAOA) to efficiently find approximate solutions for computational problems contained in the polynomially bounded NP optimisation complexity class (NPO PB). We consider a generalisation of the QAOA state evolution to alternating quantum walks and solution-quality-dependent phase shifts and use the quantum walks to integrate the problem constraints of NPO problems. We apply the concept of a hybrid quantum-classical variational scheme to attempt finding the highest expectation value, which contains a high-quality solution. We synthesise an efficient quantum circuit for the constrained optimisation algorithm, and we numerically demonstrate the behaviour of the circuit with respect to an illustrative NP optimisation problem with constraints, minimum vertex cover. With examples, this paper demonstrates that the degree of accuracy to which the quantum walks are simulated can be treated as an additional optimisation parameter, leading to improved results.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}