Izaac, J A; Wang, J B; Abbott, P C; Ma, X S Quantum centrality testing on directed graphs via PTsymmetric quantum walks Journal Article Phys. Rev. A, 96 , pp. 032305, 2017. Abstract  Links: @article{PhysRevA.96.032305,
title = {Quantum centrality testing on directed graphs via PTsymmetric 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 = {20170901},
journal = {Phys. Rev. A},
volume = {96},
pages = {032305},
publisher = {American Physical Society},
abstract = {Various quantumwalk based algorithms have been proposed to analyse and rank the centrality of graph vertices. However, issues arise when working with directed graphs  the resulting nonHermitian Hamiltonian leads to nonunitary 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 PTsymmetric quantum walks, allowing probability conserving nonunitary 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 eigenvectorlike quantum centrality; using the PTsymmetric 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}
}
Various quantumwalk based algorithms have been proposed to analyse and rank the centrality of graph vertices. However, issues arise when working with directed graphs  the resulting nonHermitian Hamiltonian leads to nonunitary 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 PTsymmetric quantum walks, allowing probability conserving nonunitary 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 eigenvectorlike quantum centrality; using the PTsymmetric 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.

Izaac, J A; Wang, J B Systematic dimensionality reduction for continuoustime quantum walks of interacting fermions Journal Article Phys. Rev. E, 96 , pp. 032136, 2017. Abstract  Links: @article{PhysRevE.96.032136,
title = {Systematic dimensionality reduction for continuoustime 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 = {20170901},
journal = {Phys. Rev. E},
volume = {96},
pages = {032136},
publisher = {American Physical Society},
abstract = {To extend the continuoustime 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 singleparticle 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}
}
To extend the continuoustime 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 singleparticle 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.

Izaac, Josh A; Zhan, Xiang; Bian, Zhihao; Wang, Kunkun; Li, Jian; Wang, Jingbo B; Xue, Peng Centrality measure based on continuoustime quantum walks and experimental realization Journal Article Phys. Rev. A, 95 , pp. 032318, 2017. Abstract  Links: @article{PhysRevA.95.032318,
title = {Centrality measure based on continuoustime 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 = {20170301},
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 walkbased algorithms have been proposed for measuring network vertex centrality. In this work, we propose a continuoustime quantum walk algorithm for determining vertex centrality, and show that it generalizes to arbitrary graphs via a statistical analysis of randomly generated scalefree and ErdősRényi networks. As a proof of concept, the algorithm is detailed on a 4vertex 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}
}
Network centrality has important implications well beyond its role in physical and information transport analysis; as such, various quantum walkbased algorithms have been proposed for measuring network vertex centrality. In this work, we propose a continuoustime quantum walk algorithm for determining vertex centrality, and show that it generalizes to arbitrary graphs via a statistical analysis of randomly generated scalefree and ErdősRényi networks. As a proof of concept, the algorithm is detailed on a 4vertex 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.

Zhou, S S; Loke, T; Izaac, J A; Wang, J B Quantum Fourier transform in computational basis Journal Article Quantum Information Processing, 16 (3), pp. 82, 2017, ISSN: 15731332. 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/s1112801715150},
doi = {10.1007/s1112801715150},
issn = {15731332},
year = {2017},
date = {20170210},
journal = {Quantum Information Processing},
volume = {16},
number = {3},
pages = {82},
abstract = {The quantum Fourier transform, with exponential speedup 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}
}
The quantum Fourier transform, with exponential speedup 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. 
Falloon, Peter E; Rodriguez, Jeremy; Wang, Jingbo B QSWalk: A Mathematica package for quantum stochastic walks on arbitrary graphs Journal Article Computer Physics Communications, 217 , pp. 162  170, 2017, ISSN: 00104655. 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 = {00104655},
year = {2017},
date = {20170101},
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 N2dimensional space, which can be solved efficiently using the builtin 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 Nvertex 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}
}
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 N2dimensional space, which can be solved efficiently using the builtin 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 Nvertex 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. 
Loke, T; Wang, J B Efficient quantum circuits for Szegedy quantum walks Journal Article 382 , pp. 64  84, 2017, ISSN: 00034916. 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 = {00034916},
year = {2017},
date = {20170101},
volume = {382},
pages = {64  84},
abstract = {A major advantage in using Szegedy’s formalism over discretetime and continuoustime 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 nonsparse 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 nontrivial graphs, providing a necessary tool for experimental demonstration of the quantum Pagerank algorithm.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
A major advantage in using Szegedy’s formalism over discretetime and continuoustime 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 nonsparse 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 nontrivial graphs, providing a necessary tool for experimental demonstration of the quantum Pagerank algorithm. 
Zhou, S S; Wang, J B Efficient quantum circuits for dense circulant and circulant like operators Journal Article 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 = {20170101},
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 engineeringrelated fields. They are, in general, nonsparse and nonunitary. 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}
}
Circulant matrices are an important family of operators, which have a wide range of applications in science and engineeringrelated fields. They are, in general, nonsparse and nonunitary. 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. 
Loke, T; Wang, J B Efficient quantum circuits for continuoustime quantum walks on composite graphs Journal Article Journal of Physics A: Mathematical and Theoretical, 50 (5), pp. 055303, 2017. Abstract  Links: @article{Loke_2017,
title = {Efficient quantum circuits for continuoustime quantum walks on composite graphs},
author = {T Loke and J B Wang},
url = {https://doi.org/10.1088/17518121/aa53a9},
doi = {10.1088/17518121/aa53a9},
year = {2017},
date = {20170101},
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 continuoustime quantum walks on specific classes of graphs, for which it is possible to fastforward the timeevolution operator to achieve constanttime 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 quantumwalk based algorithms in laboratories.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
In this paper, we investigate the simulation of continuoustime quantum walks on specific classes of graphs, for which it is possible to fastforward the timeevolution operator to achieve constanttime 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 quantumwalk based algorithms in laboratories. 
Swaddle, Michael; Noakes, Lyle; Smallbone, Harry; Salter, Liam; Wang, Jingbo Generating threequbit quantum circuits with neural networks Journal Article Physics Letters A, 381 (39), pp. 3391  3395, 2017, ISSN: 03759601. Abstract  Links: @article{SWADDLE20173391,
title = {Generating threequbit 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 = {03759601},
year = {2017},
date = {20170101},
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}
}
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. 