### 2021

Marsh, S.; Wang, J. B.

Deterministic spatial search using alternating quantum walks Journal Article

In: Phys. Rev. A, 104 , pp. 022216, 2021.

Abstract | Links:

@article{PhysRevA.104.022216,

title = {Deterministic spatial search using alternating quantum walks},

author = {S. Marsh and J. B. Wang},

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

doi = {10.1103/PhysRevA.104.022216},

year = {2021},

date = {2021-08-24},

journal = {Phys. Rev. A},

volume = {104},

pages = {022216},

publisher = {American Physical Society},

abstract = {This paper examines the performance of spatial search where the Grover diffusion operator is replaced by continuous-time quantum walks on a class of interdependent networks. We prove that, for a set of optimal quantum walk times and marked vertex phase shifts, a deterministic algorithm for structured spatial search is established that finds the marked vertex with 100% probability. This improves on the Childs and Goldstone spatial search algorithm on the same class of graphs, which we show can only amplify to 50% probability. Our method uses ⌈(π/2√2)√N⌉ marked vertex phase shifts for an N-vertex graph, making it comparable to Grover's algorithm for an unstructured search. It is expected that this framework can be readily extended to deterministic spatial search on other families of graph structures.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

Khalique, A; Sett, A; Wang, J B; Twamley, J

Controlled information transfer in continuous-time chiral quantum walks Journal Article

In: New Journal of Physics, 23 (8), pp. 083005, 2021.

Abstract | Links:

@article{Khalique_2021,

title = {Controlled information transfer in continuous-time chiral quantum walks},

author = {A Khalique and A Sett and J B Wang and J Twamley},

url = {https://doi.org/10.1088/1367-2630/ac1551},

doi = {10.1088/1367-2630/ac1551},

year = {2021},

date = {2021-08-01},

journal = {New Journal of Physics},

volume = {23},

number = {8},

pages = {083005},

publisher = {IOP Publishing},

abstract = {In this paper we investigate properties of continuous time chiral quantum walks, which possess complex valued edge weights in the underlying graph structure, together with an initial Gaussian wavefunction spread over a number of vertices. We demonstrate that, for certain graph topology and phase matching conditions, we are able to direct the flow of probability amplitudes in a specific direction inside the graph network. We design a quantum walk graph analogue of an optical circulator which is a combination of a cycle and semi-infinite chain graphs. Excitations input into the circulator from a semi-infinite chain are routed in a directionally biased fashion to output to a different semi-infinite chain. We examine in detail a two port circulator graph which spatially separates excitations flowing back in forth between the two semi-finite chains to directionally occupy the top or bottom half of the cycle portion of the circulator. This setup can be used, for example, to detect non-Markovian processes, which leads to information and energy back-flow from the bath back into the system.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

Qiang, X.; Wang, Y.; Xue, Y.; Ge, R.; Chen, L.; Liu, Y.; Huang, A.; Fu, X.; Xu, P.; Yi, T.; Xu, F.; Deng, M.; Wang, J.; Meinecke, J.; Matthews, J.; Cai, X.; Yang, X.; Wu, J.

Implementing graph-theoretic quantum algorithms on a silicon photonic quantum walk processor Journal Article

In: Science Advances, 7 , pp. eabb8375, 2021.

Abstract | Links:

@article{Qiang2021,

title = {Implementing graph-theoretic quantum algorithms on a silicon photonic quantum walk processor},

author = {X. Qiang and Y. Wang and Y. Xue and R. Ge and L. Chen and Y. Liu and A. Huang and X. Fu and P. Xu and T. Yi and F. Xu and M. Deng and J. Wang and J. Meinecke and J. Matthews and X. Cai and X. Yang and J. Wu},

url = {https://advances.sciencemag.org/content/7/9/eabb8375},

doi = {10.1126/sciadv.abb8375},

year = {2021},

date = {2021-02-26},

journal = {Science Advances},

volume = {7},

pages = {eabb8375},

abstract = {Applications of quantum walks can depend on the number, exchange symmetry and indistinguishability of the particles involved, and the underlying graph structures where they move. Here, we show that silicon photonics, by exploiting an entanglement-driven scheme, can realize quantum walks with full control over all these properties in one device. The device we realize implements entangled two-photon quantum walks on any five-vertex graph, with continuously tunable particle exchange symmetry and indistinguishability. We show how this simulates single-particle walks on larger graphs, with size and geometry controlled by tuning the properties of the composite quantum walkers. We apply the device to quantum walk algorithms for searching vertices in graphs and testing for graph isomorphisms. In doing so, we implement up to 100 sampled time steps of quantum walk evolution on each of 292 different graphs. This opens the way to large-scale, programmable quantum walk processors for classically intractable applications.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

Marsh, Samuel; Wang, Jingbo

A framework for optimal quantum spatial search using alternating phase-walks Journal Article Forthcoming

In: Quantum Science and Technology, Forthcoming, (formally accepted).

Abstract | Links:

@article{Marsh2021newsearchframework,

title = {A framework for optimal quantum spatial search using alternating phase-walks},

author = {Samuel Marsh and Jingbo Wang},

url = {http://iopscience.iop.org/article/10.1088/2058-9565/ac26af},

doi = {10.1088/2058-9565/ac26af},

year = {2021},

date = {2021-01-01},

urldate = {2021-01-01},

journal = {Quantum Science and Technology},

abstract = {We present a novel methodological framework for quantum spatial search, generalising the Childs & Goldstone (CG) algorithm via alternating applications of marked-vertex phase shifts and continuous-time quantum walks. We determine closed form expressions for the optimal walk time and phase shift parameters for periodic graphs. These parameters are chosen to rotate the system about subsets of the graph Laplacian eigenstates, amplifying the probability of measuring the marked vertex. The state evolution is asymptotically optimal for any class of periodic graphs having a fixed number of unique eigenvalues. We demonstrate the effectiveness of the algorithm by applying it to obtain O(√N) search on a variety of graphs. One important class is the n by n3 Rook graph, which has N=n4 vertices. On this class of graphs the CG algorithm performs suboptimally, achieving only O(N-1/8) overlap after time O(N5/8). Using the new alternating phase-walk framework, we show that O(1) overlap is obtained in O(√N) phase-walk iterations.},

note = {formally accepted},

keywords = {},

pubstate = {forthcoming},

tppubtype = {article}

}

Matwiejew, Edric; Wang, Jingbo

QSW_MPI: A framework for parallel simulation of quantum stochastic walks Journal Article

In: Computer Physics Communications, 260 , pp. 107724, 2021, ISSN: 0010-4655.

Abstract | Links:

@article{MATWIEJEW2021107724,

title = {QSW_MPI: A framework for parallel simulation of quantum stochastic walks},

author = {Edric Matwiejew and Jingbo Wang},

url = {http://www.sciencedirect.com/science/article/pii/S0010465520303581},

doi = {https://doi.org/10.1016/j.cpc.2020.107724},

issn = {0010-4655},

year = {2021},

date = {2021-01-01},

journal = {Computer Physics Communications},

volume = {260},

pages = {107724},

abstract = {QSW_MPI is a Python package developed for time-series simulation of continuous-time quantum stochastic walks. This model allows for the study of Markovian open quantum systems in the Lindblad formalism, including a generalisation of the continuous-time random walk and continuous-time quantum walk. Consisting of a Python interface accessing parallelised Fortran libraries utilising sparse data structures, QSW_MPI is scalable to massively parallel computers, which makes possible the simulation of a wide range of walk dynamics on directed and undirected graphs of arbitrary complexity. },

keywords = {},

pubstate = {published},

tppubtype = {article}

}

Slate, N; Matwiejew, E; Marsh, S; Wang, J B

Quantum walk-based portfolio optimisation Journal Article

In: Quantum, 5 , pp. 513, 2021, ISSN: 2521-327X.

Abstract | Links:

@article{Slate2021quantumwalkbased,

title = {Quantum walk-based portfolio optimisation},

author = {N Slate and E Matwiejew and S Marsh and J B Wang},

url = {https://doi.org/10.22331/q-2021-07-28-513},

doi = {10.22331/q-2021-07-28-513},

issn = {2521-327X},

year = {2021},

date = {2021-01-01},

journal = {Quantum},

volume = {5},

pages = {513},

publisher = {Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften},

abstract = {This paper proposes a highly efficient quantum algorithm for portfolio optimisation targeted at near-term noisy intermediate-scale quantum computers. Recent work by Hodson et al. (2019) explored potential application of hybrid quantum-classical algorithms to the problem of financial portfolio rebalancing. In particular, they deal with the portfolio optimisation problem using the Quantum Approximate Optimisation Algorithm and the Quantum Alternating Operator Ansatz. In this paper, we demonstrate substantially better performance using a newly developed Quantum Walk Optimisation Algorithm in finding high-quality solutions to the portfolio optimisation problem.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

### 2020

Wu, Tong; Izaac, J A; Li, Zi-Xi; Wang, Kai; Chen, Zhao-Zhong; Zhu, Shining; Wang, J B; Ma, Xiao-Song

Experimental Parity-Time Symmetric Quantum Walks for Centrality Ranking on Directed Graphs Journal Article

In: Phys. Rev. Lett., 125 , pp. 240501, 2020.

Abstract | Links:

@article{PhysRevLett.125.240501,

title = {Experimental Parity-Time Symmetric Quantum Walks for Centrality Ranking on Directed Graphs},

author = {Tong Wu and J A Izaac and Zi-Xi Li and Kai Wang and Zhao-Zhong Chen and Shining Zhu and J B Wang and Xiao-Song Ma},

url = {https://link.aps.org/doi/10.1103/PhysRevLett.125.240501},

doi = {10.1103/PhysRevLett.125.240501},

year = {2020},

date = {2020-12-01},

journal = {Phys. Rev. Lett.},

volume = {125},

pages = {240501},

publisher = {American Physical Society},

abstract = {Quantum walks (QW) are of crucial importance in the development of quantum information processing algorithms. Recently, several quantum algorithms have been proposed to implement network analysis, in particular to rank the centrality of nodes in networks represented by graphs. Employing QW in centrality ranking is advantageous comparing to certain widely used classical algorithms (e.g. PageRank) because QW approach can lift the vertex rank degeneracy in certain graphs. However, it is challenging to implement a directed graph via QW, since it corresponds to a non-Hermitian Hamiltonian and thus cannot be accomplished by conventional QW. Here we report the realizations of centrality rankings of both a three-vertex and four-vertex directed graphs with parity-time (PT) symmetric quantum walks. To achieve this, we use high-dimensional photonic quantum states, optical circuitries consisting of multiple concatenated interferometers and dimension dependent loss. Importantly, we demonstrate the advantage of QW approach experimentally by breaking the vertex rank degeneracy in a four-vertex graph. Our work shows that PT-symmetric quantum walks may be useful for realizing advanced algorithm in a quantum network.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

Wang, Kunkun; Shi, Yuhao; Xiao, Lei; Wang, Jingbo; Joglekar, Yogesh N; Xue, Peng

Experimental realization of continuous-time quantum walks on directed graphs and their application in PageRank Journal Article

In: Optica, 7 (11), pp. 1524–1530, 2020.

Abstract | Links:

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

journal = {Optica},

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}

}

Schofield, Callum; Wang, Jingbo B; Li, Yuying

Quantum walk inspired algorithm for graph similarity and isomorphism Journal Article

In: Quantum Information Processing, 19 (9), pp. 281, 2020, ISSN: 1573-1332.

Abstract | Links:

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

journal = {Quantum Information Processing},

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}

}

Marsh, S; Wang, J B

Combinatorial optimization via highly efficient quantum walks Journal Article

In: Phys. Rev. Research, 2 , pp. 023302, 2020.

Abstract | Links:

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

}

Ruan, Yue; Marsh, Samuel; Xue, Xilin; Liu, Zhihao; Wang, Jingbo

The Quantum Approximate Algorithm for Solving Traveling Salesman Problem Journal Article

In: Computers, Materials & Continua, 63 (3), pp. 1237–1247, 2020, ISSN: 1546-2226.

Abstract | Links:

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

journal = {Computers, Materials & Continua},

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}

}

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.

Slate, N; Matwiejew, E; Marsh, S; Wang, J B

Quantum walk-based portfolio optimisation Miscellaneous

2020.

Abstract | Links:

@misc{slate2020quantum,

title = {Quantum walk-based portfolio optimisation},

author = {N Slate and E Matwiejew and S Marsh and J B Wang},

url = {https://arxiv.org/abs/2011.08057},

year = {2020},

date = {2020-01-01},

abstract = {This paper proposes a highly efficient quantum algorithm for portfolio optimisation targeted at near-term noisy intermediate-scale quantum computers. Recent work by Hodson et. al (2019) explored potential application of hybrid quantum-classical algorithms to the problem of financial portfolio rebalancing. In particular, they deal with the portfolio optimisation problem using the Quantum Approximate Optimisation Algorithm and the Quantum Alternating Operator Ansatz. In this paper, we demonstrate substantially better performance using a newly developed Quantum Walk-based Optimisation Algorithm in finding high-quality solutions to the portfolio optimisation problem.

},

keywords = {},

pubstate = {published},

tppubtype = {misc}

}

Jay, Gareth; Debbasch, Fabrice; Wang, Jingbo

A systematic method to building Dirac quantum walks coupled to electromagnetic fields Journal Article

In: Quantum Information Processing , 19 , pp. 422, 2020.

Abstract | Links:

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

journal = {Quantum Information Processing },

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}

}

### 2019

Chiew, M; de Lacy, K; Yu, C H; Marsh, S; Wang, J B

Graph comparison via nonlinear quantum search Journal Article

In: Quantum Information Processing, 18 (10), pp. 302, 2019, ISSN: 1573-1332.

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/s11128-019-2407-2},

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

issn = {1573-1332},

year = {2019},

date = {2019-08-20},

journal = {Quantum Information Processing},

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}

}

Yu, Chao-Hua; Gao, Fei; Lin, Song; Wang, Jingbo

Quantum data compression by principal component analysis Journal Article

In: Quantum Information Processing, 18 (8), pp. 249, 2019, ISSN: 1573-1332.

Abstract | Links:

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

journal = {Quantum Information Processing},

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}

}

Sett, A; Pan, H; Falloon, P E; Wang, J B

Zero transfer in continuous-time quantum walks Journal Article

In: Quantum Information Processing, 18 (5), pp. 159, 2019, ISSN: 1573-1332.

Abstract | Links:

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

journal = {Quantum Information Processing},

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}

}

Jay, Gareth; Debbasch, Fabrice; Wang, J B

Dirac quantum walks on triangular and honeycomb lattices Journal Article

In: 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 = {2019-03-01},

journal = {Phys. Rev. A},

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}

}

Yu, Chao-Hua; Gao, Fei; Liu, Chenghuan; Huynh, Du; Reynolds, Mark; Wang, Jingbo

Quantum algorithm for visual tracking Journal Article

In: Phys. Rev. A, 99 , pp. 022301, 2019.

Abstract | Links:

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

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

}

Marsh, S; Wang, J B

A quantum walk-assisted approximate algorithm for bounded NP optimisation problems Journal Article

In: Quantum Information Processing, 18 (3), pp. 61, 2019, ISSN: 1573-1332.

Abstract | Links:

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

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

}

### 2018

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

Large-scale silicon quantum photonics implementing arbitrary two-qubit processing Journal Article

In: Nature Photonics, 12 (9), pp. 534-539, 2018, ISSN: 1749-4893.

Abstract | Links:

@article{Qiang2018,

title = {Large-scale silicon quantum photonics implementing arbitrary two-qubit 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/s41566-018-0236-y},

doi = {10.1038/s41566-018-0236-y},

issn = {1749-4893},

year = {2018},

date = {2018-09-01},

journal = {Nature Photonics},

volume = {12},

number = {9},

pages = {534-539},

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 large-scale silicon photonic circuits to implement an extension of the linear combination of quantum operators scheme, we realize a fully programmable two-qubit quantum processor, enabling universal two-qubit quantum information processing in optics. The quantum processor is fabricated with mature CMOS-compatible processing and comprises more than 200 photonic components. We programmed the device to implement 98 different two-qubit unitary operations (with an average quantum process fidelity of 93.2thinspacetextpmthinspace4.5%), a two-qubit quantum approximate optimization algorithm, and efficient simulation of Szegedy directed quantum walks. This fosters further use of the linear-combination architecture with silicon photonics for future photonic quantum processors.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

de Lacy, K; Noakes, L; Twamley, J; Wang, J B

Controlled quantum search Journal Article

In: Quantum Information Processing, 17 (10), pp. 266, 2018, ISSN: 1573-1332.

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/s11128-018-2031-6},

doi = {10.1007/s11128-018-2031-6},

issn = {1573-1332},

year = {2018},

date = {2018-08-28},

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 Gross--Pitaevskii-type 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 time-dependent nonlinearity which obtains one of the N marked items with certainty. The protocol has runtime $$backslashmathcal O(n /(g backslashsqrtN(n-N)))$$O(n/(gN(n-N))), where g is related to the time-dependent 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}

}

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 two-qubit photonic quantum processor Inproceedings

In: Conference on Lasers and Electro-Optics, pp. FM1G.1, Optical Society of America, 2018.

Abstract | Links:

@inproceedings{Qiang:18,

title = {A universal two-qubit 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_QELS-2018-FM1G.1},

doi = {10.1364/CLEO_QELS.2018.FM1G.1},

year = {2018},

date = {2018-01-01},

booktitle = {Conference on Lasers and Electro-Optics},

journal = {Conference on Lasers and Electro-Optics},

pages = {FM1G.1},

publisher = {Optical Society of America},

abstract = {We report a universal two-qubit silicon photonic quantum processor, able to initialise, operate and analyze arbitrary two-qubit states and processes applications in quantum information processing.},

keywords = {},

pubstate = {published},

tppubtype = {inproceedings}

}

### 2017

Izaac, J A; Wang, J B; Abbott, P C; Ma, X S

Quantum centrality testing on directed graphs via PT-symmetric quantum walks Journal Article

In: Phys. Rev. A, 96 , pp. 032305, 2017.

Abstract | Links:

@article{PhysRevA.96.032305,

title = {Quantum centrality testing on directed graphs via PT-symmetric quantum walks},

author = {J A Izaac and J B Wang and P C Abbott and X S Ma},

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

doi = {10.1103/PhysRevA.96.032305},

year = {2017},

date = {2017-09-01},

journal = {Phys. Rev. A},

volume = {96},

pages = {032305},

publisher = {American Physical Society},

abstract = {Various quantum-walk based algorithms have been proposed to analyse and rank the centrality of graph vertices. However, issues arise when working with directed graphs --- the resulting non-Hermitian Hamiltonian leads to non-unitary dynamics, and the total probability of the quantum walker is no longer conserved. In this paper, we discuss a method for simulating directed graphs using PT-symmetric quantum walks, allowing probability conserving non-unitary evolution. This method is equivalent to mapping the directed graph to an undirected, yet weighted, complete graph over the same vertex set, and can be extended to cover interdependent networks of directed graphs. Previous work has shown centrality measures based on the CTQW provide an eigenvector-like quantum centrality; using the PT-symmetric framework, we extend these centrality algorithms to directed graphs with a significantly reduced Hilbert space compared to previous proposals. In certain cases, this centrality measure provides an advantage over classical algorithms used in network analysis, for example by breaking vertex rank degeneracy. Finally, we perform a statistical analysis over ensembles of random graphs, and show strong agreement with the classical PageRank measure on directed acyclic graphs.

},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

Izaac, J A; Wang, J B

Systematic dimensionality reduction for continuous-time quantum walks of interacting fermions Journal Article

In: Phys. Rev. E, 96 , pp. 032136, 2017.

Abstract | Links:

@article{PhysRevE.96.032136,

title = {Systematic dimensionality reduction for continuous-time quantum walks of interacting fermions},

author = {J A Izaac and J B Wang},

url = {https://link.aps.org/doi/10.1103/PhysRevE.96.032136},

doi = {10.1103/PhysRevE.96.032136},

year = {2017},

date = {2017-09-01},

journal = {Phys. Rev. E},

volume = {96},

pages = {032136},

publisher = {American Physical Society},

abstract = {To extend the continuous-time quantum walk (CTQW) to simulate P distinguishable particles on a graph G composed of N vertices, the Hamiltonian of the system is expanded to act on an NP -dimensional Hilbert space, in effect, simulating the multiparticle CTQW on graph G via a single-particle CTQW propagating on the Cartesian graph product GP . The properties of the Cartesian graph product have been well studied, and classical simulation of multiparticle CTQWs are common in the literature. However, the above approach is generally applied as is when simulating indistinguishable particles, with the particle statistics then applied to the propagated NP state vector to determine walker probabilities. We address the following question: How can we modify the underlying graph structure GP in order to simulate multiple interacting fermionic CTQWs with a reduction in the size of the state space? In this paper, we present an algorithm for systematically removing “redundant” and forbidden quantum states from consideration, which provides a significant reduction in the effective dimension of the Hilbert space of the fermionic CTQW. As a result, as the number of interacting fermions in the system increases, the classical computational resources required no longer increases exponentially for fixed N.

},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

Izaac, Josh A; Zhan, Xiang; Bian, Zhihao; Wang, Kunkun; Li, Jian; Wang, Jingbo B; Xue, Peng

Centrality measure based on continuous-time quantum walks and experimental realization Journal Article

In: Phys. Rev. A, 95 , pp. 032318, 2017.

Abstract | Links:

@article{PhysRevA.95.032318,

title = {Centrality measure based on continuous-time quantum walks and experimental realization},

author = {Josh A Izaac and Xiang Zhan and Zhihao Bian and Kunkun Wang and Jian Li and Jingbo B Wang and Peng Xue},

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

doi = {10.1103/PhysRevA.95.032318},

year = {2017},

date = {2017-03-01},

journal = {Phys. Rev. A},

volume = {95},

pages = {032318},

publisher = {American Physical Society},

abstract = {Network centrality has important implications well beyond its role in physical and information transport analysis; as such, various quantum walk-based algorithms have been proposed for measuring network vertex centrality. In this work, we propose a continuous-time quantum walk algorithm for determining vertex centrality, and show that it generalizes to arbitrary graphs via a statistical analysis of randomly generated scale-free and Erdős-Rényi networks. As a proof of concept, the algorithm is detailed on a 4-vertex star graph and physically implemented via linear optics, using spatial and polarization degrees of freedoms of single photons. This paper reports the first successful physical demonstration of a quantum centrality algorithm.

},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

Zhou, S S; Loke, T; Izaac, J A; Wang, J B

Quantum Fourier transform in computational basis Journal Article

In: Quantum Information Processing, 16 (3), pp. 82, 2017, ISSN: 1573-1332.

Abstract | Links:

@article{Zhou2017,

title = {Quantum Fourier transform in computational basis},

author = {S S Zhou and T Loke and J A Izaac and J B Wang},

url = {https://doi.org/10.1007/s11128-017-1515-0},

doi = {10.1007/s11128-017-1515-0},

issn = {1573-1332},

year = {2017},

date = {2017-02-10},

journal = {Quantum Information Processing},

volume = {16},

number = {3},

pages = {82},

abstract = {The quantum Fourier transform, with exponential speed-up compared to the classical fast Fourier transform, has played an important role in quantum computation as a vital part of many quantum algorithms (most prominently, Shor's factoring algorithm). However, situations arise where it is not sufficient to encode the Fourier coefficients within the quantum amplitudes, for example in the implementation of control operations that depend on Fourier coefficients. In this paper, we detail a new quantum scheme to encode Fourier coefficients in the computational basis, with fidelity $$1 - backslashdelta $$1-$delta$and digit accuracy $$backslashepsilon $$ϵfor each Fourier coefficient. Its time complexity depends polynomially on $$backslashlog (N)$$log(N), where N is the problem size, and linearly on $$1/backslashdelta $$1/$delta$and $$1/backslashepsilon $$1/ϵ. We also discuss an application of potential practical importance, namely the simulation of circulant Hamiltonians.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

Qiang, Xiaogang; Loke, Thomas; Montanaro, Ashley; Aungskunsiri, Kanin; Zhou, Xiaoqi; O’Brien, Jeremy L; Wang, Jingbo B; Matthews, Jonathan CF

Efficient quantum walk on a quantum processor Journal Article

In: Nature communications, 7 (1), pp. 1–6, 2017.

Abstract | Links:

@article{qiang2016efficientb,

title = {Efficient quantum walk on a quantum processor},

author = {Xiaogang Qiang and Thomas Loke and Ashley Montanaro and Kanin Aungskunsiri and Xiaoqi Zhou and Jeremy L O’Brien and Jingbo B Wang and Jonathan CF Matthews},

url = {https://www.nature.com/articles/ncomms11511.pdf?origin=ppub},

doi = {10.1038/ncomms11511},

year = {2017},

date = {2017-01-01},

journal = {Nature communications},

volume = {7},

number = {1},

pages = {1--6},

publisher = {Nature Publishing Group},

abstract = {The random walk formalism is used across a wide range of applications, from modelling share

prices to predicting population genetics. Likewise, quantum walks have shown much potential

as a framework for developing new quantum algorithms. Here we present explicit efficient

quantum circuits for implementing continuous-time quantum walks on the circulant class of

graphs. These circuits allow us to sample from the output probability distributions of quantum

walks on circulant graphs efficiently. We also show that solving the same sampling problem

for arbitrary circulant quantum circuits is intractable for a classical computer, assuming

conjectures from computational complexity theory. This is a new link between

continuous-time quantum walks and computational complexity theory and it indicates a

family of tasks that could ultimately demonstrate quantum supremacy over classical

computers. As a proof of principle, we experimentally implement the proposed quantum

circuit on an example circulant graph using a two-qubit photonics quantum processor.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

prices to predicting population genetics. Likewise, quantum walks have shown much potential

as a framework for developing new quantum algorithms. Here we present explicit efficient

quantum circuits for implementing continuous-time quantum walks on the circulant class of

graphs. These circuits allow us to sample from the output probability distributions of quantum

walks on circulant graphs efficiently. We also show that solving the same sampling problem

for arbitrary circulant quantum circuits is intractable for a classical computer, assuming

conjectures from computational complexity theory. This is a new link between

continuous-time quantum walks and computational complexity theory and it indicates a

family of tasks that could ultimately demonstrate quantum supremacy over classical

computers. As a proof of principle, we experimentally implement the proposed quantum

circuit on an example circulant graph using a two-qubit photonics quantum processor.

Swaddle, Michael; Noakes, Lyle; Smallbone, Harry; Salter, Liam; Wang, Jingbo

Generating three-qubit quantum circuits with neural networks Journal Article

In: Physics Letters A, 381 (39), pp. 3391 - 3395, 2017, ISSN: 0375-9601.

Abstract | Links:

@article{SWADDLE20173391,

title = {Generating three-qubit quantum circuits with neural networks},

author = {Michael Swaddle and Lyle Noakes and Harry Smallbone and Liam Salter and Jingbo Wang},

url = {http://www.sciencedirect.com/science/article/pii/S0375960117308009},

doi = {https://doi.org/10.1016/j.physleta.2017.08.043},

issn = {0375-9601},

year = {2017},

date = {2017-01-01},

journal = {Physics Letters A},

volume = {381},

number = {39},

pages = {3391 - 3395},

abstract = {A new method for compiling quantum algorithms is proposed and tested for a three qubit system. The proposed method is to decompose a unitary matrix U, into a product of simpler Uj via a neural network. These Uj can then be decomposed into product of known quantum gates. Key to the effectiveness of this approach is the restriction of the set of training data generated to paths which approximate minimal normal subRiemannian geodesics, as this removes unnecessary redundancy and ensures the products are unique. The two neural networks are shown to work effectively, each individually returning low loss values on validation data after relatively short training periods. The two networks are able to return coefficients that are sufficiently close to the true coefficient values to validate this method as an approach for generating quantum circuits. There is scope for more work in scaling this approach for larger quantum systems.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

Loke, T; Wang, J B

Efficient quantum circuits for continuous-time quantum walks on composite graphs Journal Article

In: Journal of Physics A: Mathematical and Theoretical, 50 (5), pp. 055303, 2017.

Abstract | Links:

@article{Loke_2017,

title = {Efficient quantum circuits for continuous-time quantum walks on composite graphs},

author = {T Loke and J B Wang},

url = {https://doi.org/10.1088/1751-8121/aa53a9},

doi = {10.1088/1751-8121/aa53a9},

year = {2017},

date = {2017-01-01},

journal = {Journal of Physics A: Mathematical and Theoretical},

volume = {50},

number = {5},

pages = {055303},

publisher = {IOP Publishing},

abstract = {In this paper, we investigate the simulation of continuous-time quantum walks on specific classes of graphs, for which it is possible to fast-forward the time-evolution operator to achieve constant-time simulation complexity and to perform the simulation exactly, i.e. , while maintaining efficiency. In particular, we discuss two classes of composite graphs, commuting graphs and Cartesian product of graphs, that contain classes of graphs which can be simulated in this fashion. This allows us to identify new families of graphs that we can efficiently simulate in a quantum circuit framework, providing practical and explicit means to explore quantum-walk based algorithms in laboratories.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

Zhou, S S; Wang, J B

Efficient quantum circuits for dense circulant and circulant like operators Journal Article

In: Royal Society Open Science, 4 (5), pp. 160906, 2017.

Abstract | Links:

@article{doi:10.1098/rsos.160906,

title = {Efficient quantum circuits for dense circulant and circulant like operators},

author = {S S Zhou and J B Wang},

url = {https://royalsocietypublishing.org/doi/abs/10.1098/rsos.160906},

doi = {10.1098/rsos.160906},

year = {2017},

date = {2017-01-01},

journal = {Royal Society Open Science},

volume = {4},

number = {5},

pages = {160906},

abstract = {Circulant matrices are an important family of operators, which have a wide range of applications in science and engineering-related fields. They are, in general, non-sparse and non-unitary. In this paper, we present efficient quantum circuits to implement circulant operators using fewer resources and with lower complexity than existing methods. Moreover, our quantum circuits can be readily extended to the implementation of Toeplitz, Hankel and block circulant matrices. Efficient quantum algorithms to implement the inverses and products of circulant operators are also provided, and an example application in solving the equation of motion for cyclic systems is discussed.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

Loke, T; Wang, J B

Efficient quantum circuits for Szegedy quantum walks Journal Article

In: 382 , pp. 64 - 84, 2017, ISSN: 0003-4916.

Abstract | Links:

@article{LOKE201764,

title = {Efficient quantum circuits for Szegedy quantum walks},

author = {T Loke and J B Wang},

url = {http://www.sciencedirect.com/science/article/pii/S0003491617301124},

doi = {https://doi.org/10.1016/j.aop.2017.04.006},

issn = {0003-4916},

year = {2017},

date = {2017-01-01},

volume = {382},

pages = {64 - 84},

abstract = {A major advantage in using Szegedy’s formalism over discrete-time and continuous-time quantum walks lies in its ability to define a unitary quantum walk by quantizing a Markov chain on a directed or weighted graph. In this paper, we present a general scheme to construct efficient quantum circuits for Szegedy quantum walks that correspond to classical Markov chains possessing transformational symmetry in the columns of the transition matrix. In particular, the transformational symmetry criteria do not necessarily depend on the sparsity of the transition matrix, so this scheme can be applied to non-sparse Markov chains. Two classes of Markov chains that are amenable to this construction are cyclic permutations and complete bipartite graphs, for which we provide explicit efficient quantum circuit implementations. We also prove that our scheme can be applied to Markov chains formed by a tensor product. We also briefly discuss the implementation of Markov chains based on weighted interdependent networks. In addition, we apply this scheme to construct efficient quantum circuits simulating the Szegedy walks used in the quantum Pagerank algorithm for some classes of non-trivial graphs, providing a necessary tool for experimental demonstration of the quantum Pagerank algorithm.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

Falloon, Peter E; Rodriguez, Jeremy; Wang, Jingbo B

QSWalk: A Mathematica package for quantum stochastic walks on arbitrary graphs Journal Article

In: Computer Physics Communications, 217 , pp. 162 - 170, 2017, ISSN: 0010-4655.

Abstract | Links:

@article{FALLOON2017162,

title = {QSWalk: A Mathematica package for quantum stochastic walks on arbitrary graphs},

author = {Peter E Falloon and Jeremy Rodriguez and Jingbo B Wang},

url = {http://www.sciencedirect.com/science/article/pii/S0010465517301029},

doi = {https://doi.org/10.1016/j.cpc.2017.03.014},

issn = {0010-4655},

year = {2017},

date = {2017-01-01},

journal = {Computer Physics Communications},

volume = {217},

pages = {162 - 170},

abstract = {We present a Mathematica package, QSWalk, to simulate the time evaluation of Quantum Stochastic Walks (QSWs) on arbitrary directed and weighted graphs. QSWs are a generalization of continuous time quantum walks that incorporate both coherent and incoherent dynamics and as such, include both quantum walks and classical random walks as special cases. The incoherent component allows for quantum walks along directed graph edges. The dynamics of QSWs are expressed using the Lindblad formalism, originally developed for open quantum systems, which frames the problem in the language of density matrices. For a QSW on a graph of N vertices, we have a sparse superoperator in an N2-dimensional space, which can be solved efficiently using the built-in MatrixExp function in Mathematica. We illustrate the use of the QSWalk package through several example case studies. Program summary Program Title: QSWalk.m Program Files doi: http://dx.doi.org/10.17632/8rwd3j9zhk.1 Licensing provisions: GNU General Public License 3 (GPL) Programming language: Mathematica. Nature of problem: The QSWalk package provides a method for simulating quantum stochastic walks on arbitrary (directed/undirected, weighted/unweighted) graphs. Solution method: For an N-vertex graph, the solution of a quantum stochastic walk can be expressed as an N2×N2 sparse matrix exponential. The QSWalk package makes use of Mathematica’s sparse linear algebra routines to solve this efficiently. Restrictions: The size of graphs that can be treated is constrained by available memory.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}