Chiew, M; de Lacy, K; Yu, C H; Marsh, S; Wang, J B Graph comparison via nonlinear quantum search Journal Article Quantum Information Processing, 18 (10), pp. 302, 2019, ISSN: 15731332. Abstract  Links: @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/s1112801924072},
doi = {10.1007/s1112801924072},
issn = {15731332},
year = {2019},
date = {20190820},
journal = {Quantum Information Processing},
volume = {18},
number = {10},
pages = {302},
abstract = {Graph comparison is an established NPhard 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 twopart 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 speedup 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 GrossPitaevskii 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 GrossPitaevskii nonlinearity. Through this example, we demonstrate the power of nonlinear quantum search techniques to solve a subset of NPhard problems.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Graph comparison is an established NPhard 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 twopart 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 speedup 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 GrossPitaevskii 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 GrossPitaevskii nonlinearity. Through this example, we demonstrate the power of nonlinear quantum search techniques to solve a subset of NPhard problems. 
Yu, ChaoHua; Gao, Fei; Lin, Song; Wang, Jingbo Quantum data compression by principal component analysis Journal Article Quantum Information Processing, 18 (8), pp. 249, 2019, ISSN: 15731332. Abstract  Links: @article{Yu2019,
title = {Quantum data compression by principal component analysis},
author = {ChaoHua Yu and Fei Gao and Song Lin and Jingbo Wang},
url = {https://doi.org/10.1007/s1112801923649},
doi = {10.1007/s1112801923649},
issn = {15731332},
year = {2019},
date = {20190701},
journal = {Quantum Information Processing},
volume = {18},
number = {8},
pages = {249},
abstract = {Data compression can be achieved by reducing the dimensionality of highdimensional but approximately lowrank 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 highdimensional but approximately lowrank 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 lowdimensional 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}
}
Data compression can be achieved by reducing the dimensionality of highdimensional but approximately lowrank 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 highdimensional but approximately lowrank 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 lowdimensional 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. 
Sett, A; Pan, H; Falloon, P E; Wang, J B Zero transfer in continuoustime quantum walks Journal Article Quantum Information Processing, 18 (5), pp. 159, 2019, ISSN: 15731332. Abstract  Links: @article{Sett2019,
title = {Zero transfer in continuoustime quantum walks},
author = {A Sett and H Pan and P E Falloon and J B Wang},
url = {https://doi.org/10.1007/s1112801922679},
doi = {10.1007/s1112801922679},
issn = {15731332},
year = {2019},
date = {20190410},
journal = {Quantum Information Processing},
volume = {18},
number = {5},
pages = {159},
abstract = {In this paper, we show how using complexvalued edge weights in a graph can completely suppress the flow of probability amplitude in a continuoustime 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 socalled chiral quantum walk, a variant of the continuoustime 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 timereversal symmetry in order to achieve zero transfer in continuoustime 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}
}
In this paper, we show how using complexvalued edge weights in a graph can completely suppress the flow of probability amplitude in a continuoustime 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 socalled chiral quantum walk, a variant of the continuoustime 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 timereversal symmetry in order to achieve zero transfer in continuoustime 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. 
Jay, Gareth; Debbasch, Fabrice; Wang, J B Dirac quantum walks on triangular and honeycomb lattices Journal Article Phys. Rev. A, 99 , pp. 032113, 2019. Abstract  Links: @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 = {20190301},
journal = {Phys. Rev. A},
volume = {99},
pages = {032113},
publisher = {American Physical Society},
abstract = {In this paper, we present a detailed study on discretetime 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}
}
In this paper, we present a detailed study on discretetime 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.

Yu, ChaoHua; Gao, Fei; Liu, Chenghuan; Huynh, Du; Reynolds, Mark; Wang, Jingbo Quantum algorithm for visual tracking Journal Article Phys. Rev. A, 99 , pp. 022301, 2019. Abstract  Links: @article{PhysRevA.99.022301,
title = {Quantum algorithm for visual tracking},
author = {ChaoHua 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 = {20190201},
journal = {Phys. Rev. A},
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 humancomputer 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}
}
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 humancomputer 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. 
Marsh, S; Wang, J B A quantum walkassisted approximate algorithm for bounded NP optimisation problems Journal Article Quantum Information Processing, 18 (3), pp. 61, 2019, ISSN: 15731332. Abstract  Links: @article{Marsh2019,
title = {A quantum walkassisted approximate algorithm for bounded NP optimisation problems},
author = {S Marsh and J B Wang},
url = {https://doi.org/10.1007/s1112801921713},
doi = {10.1007/s1112801921713},
issn = {15731332},
year = {2019},
date = {20190116},
journal = {Quantum Information Processing},
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 solutionqualitydependent phase shifts and use the quantum walks to integrate the problem constraints of NPO problems. We apply the concept of a hybrid quantumclassical variational scheme to attempt finding the highest expectation value, which contains a highquality 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}
}
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 solutionqualitydependent phase shifts and use the quantum walks to integrate the problem constraints of NPO problems. We apply the concept of a hybrid quantumclassical variational scheme to attempt finding the highest expectation value, which contains a highquality 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. 
Qiang, Xiaogang; Zhou, Xiaoqi; Wang, Jianwei; Wilkes, Callum M; Loke, Thomas; O'Gara, Sean; Kling, Laurent; Marshall, Graham D; Santagati, Raffaele; Ralph, Timothy C; Wang, Jingbo B; O'Brien, Jeremy L; Thompson, Mark G; Matthews, Jonathan C F Largescale silicon quantum photonics implementing arbitrary twoqubit processing Journal Article Nature Photonics, 12 (9), pp. 534539, 2018, ISSN: 17494893. Abstract  Links: @article{Qiang2018,
title = {Largescale silicon quantum photonics implementing arbitrary twoqubit processing},
author = {Xiaogang Qiang and Xiaoqi Zhou and Jianwei Wang and Callum M Wilkes and Thomas Loke and Sean O'Gara and Laurent Kling and Graham D Marshall and Raffaele Santagati and Timothy C Ralph and Jingbo B Wang and Jeremy L O'Brien and Mark G Thompson and Jonathan C F Matthews},
url = {https://doi.org/10.1038/s415660180236y},
doi = {10.1038/s415660180236y},
issn = {17494893},
year = {2018},
date = {20180901},
journal = {Nature Photonics},
volume = {12},
number = {9},
pages = {534539},
abstract = {Photonics is a promising platform for implementing universal quantum information processing. Its main challenges include precise control of massive circuits of linear optical components and effective implementation of entangling operations on photons. By using largescale silicon photonic circuits to implement an extension of the linear combination of quantum operators scheme, we realize a fully programmable twoqubit quantum processor, enabling universal twoqubit quantum information processing in optics. The quantum processor is fabricated with mature CMOScompatible processing and comprises more than 200 photonic components. We programmed the device to implement 98 different twoqubit unitary operations (with an average quantum process fidelity of 93.2thinspacetextpmthinspace4.5%), a twoqubit quantum approximate optimization algorithm, and efficient simulation of Szegedy directed quantum walks. This fosters further use of the linearcombination architecture with silicon photonics for future photonic quantum processors.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Photonics is a promising platform for implementing universal quantum information processing. Its main challenges include precise control of massive circuits of linear optical components and effective implementation of entangling operations on photons. By using largescale silicon photonic circuits to implement an extension of the linear combination of quantum operators scheme, we realize a fully programmable twoqubit quantum processor, enabling universal twoqubit quantum information processing in optics. The quantum processor is fabricated with mature CMOScompatible processing and comprises more than 200 photonic components. We programmed the device to implement 98 different twoqubit unitary operations (with an average quantum process fidelity of 93.2thinspacetextpmthinspace4.5%), a twoqubit quantum approximate optimization algorithm, and efficient simulation of Szegedy directed quantum walks. This fosters further use of the linearcombination architecture with silicon photonics for future photonic quantum processors. 
de Lacy, K; Noakes, L; Twamley, J; Wang, J B Controlled quantum search Journal Article Quantum Information Processing, 17 (10), pp. 266, 2018, ISSN: 15731332. Abstract  Links: @article{deLacy2018,
title = {Controlled quantum search},
author = {K de Lacy and L Noakes and J Twamley and J B Wang},
url = {https://doi.org/10.1007/s1112801820316},
doi = {10.1007/s1112801820316},
issn = {15731332},
year = {2018},
date = {20180828},
journal = {Quantum Information Processing},
volume = {17},
number = {10},
pages = {266},
abstract = {Quantum searching for one of N marked items in an unsorted database of n items is solved in $$backslashmathcal O(backslashsqrtn/N)$$O(n/N)steps using Grover's algorithm. Using nonlinear quantum dynamics with a GrossPitaevskiitype quadratic nonlinearity, Childs and Young (Phys Rev A 93:022314, 2016, https://doi.org/10.1103/PhysRevA.93.022314) discovered an unstructured quantum search algorithm with a complexity $$backslashmathcal O( backslashmin backslash 1/g backslash, backslashlog (g n), backslashsqrtn backslash) $$O(min1/glog(gn),n), which can be used to find a marked item after $$o(backslashlog (n))$$o(log(n))repetitions, where g is the nonlinearity strength. In this work we develop an quantum search on a complete graph using a timedependent nonlinearity which obtains one of the N marked items with certainty. The protocol has runtime $$backslashmathcal O(n /(g backslashsqrtN(nN)))$$O(n/(gN(nN))), where g is related to the timedependent nonlinearity. We also extend the analysis to a quantum search on general symmetric graphs and can greatly simplify the resulting equations when the graph diameter is less than 4.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Quantum searching for one of N marked items in an unsorted database of n items is solved in $$backslashmathcal O(backslashsqrtn/N)$$O(n/N)steps using Grover's algorithm. Using nonlinear quantum dynamics with a GrossPitaevskiitype quadratic nonlinearity, Childs and Young (Phys Rev A 93:022314, 2016, https://doi.org/10.1103/PhysRevA.93.022314) discovered an unstructured quantum search algorithm with a complexity $$backslashmathcal O( backslashmin backslash 1/g backslash, backslashlog (g n), backslashsqrtn backslash) $$O(min1/glog(gn),n), which can be used to find a marked item after $$o(backslashlog (n))$$o(log(n))repetitions, where g is the nonlinearity strength. In this work we develop an quantum search on a complete graph using a timedependent nonlinearity which obtains one of the N marked items with certainty. The protocol has runtime $$backslashmathcal O(n /(g backslashsqrtN(nN)))$$O(n/(gN(nN))), where g is related to the timedependent nonlinearity. We also extend the analysis to a quantum search on general symmetric graphs and can greatly simplify the resulting equations when the graph diameter is less than 4. 
Qiang, X; Zhou, X; Wang, J; Wilkes, C; Loke, T; O'Gara, S; Kling, L; Marshall, G; Santagati, R; Wang, J B; O'Brien, J L; Thompson, M G; Matthews, J C F A universal twoqubit photonic quantum processor Inproceedings Conference on Lasers and ElectroOptics, pp. FM1G.1, Optical Society of America, 2018. Abstract  Links: @inproceedings{Qiang:18,
title = {A universal twoqubit photonic quantum processor},
author = {X Qiang and X Zhou and J Wang and C Wilkes and T Loke and S O'Gara and L Kling and G Marshall and R Santagati and J B Wang and J L O'Brien and M G Thompson and J C F Matthews},
url = {http://www.osapublishing.org/abstract.cfm?URI=CLEO_QELS2018FM1G.1},
doi = {10.1364/CLEO_QELS.2018.FM1G.1},
year = {2018},
date = {20180101},
booktitle = {Conference on Lasers and ElectroOptics},
journal = {Conference on Lasers and ElectroOptics},
pages = {FM1G.1},
publisher = {Optical Society of America},
abstract = {We report a universal twoqubit silicon photonic quantum processor, able to initialise, operate and analyze arbitrary twoqubit states and processes applications in quantum information processing.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We report a universal twoqubit silicon photonic quantum processor, able to initialise, operate and analyze arbitrary twoqubit states and processes applications in quantum information processing. 