2024
Qu, Dengke; Matwiejew, Edric; Wang, Kunkun; Wang, Jingbo; Xue, Peng
Experimental implementation of quantum-walk-based portfolio optimisation Journal Article
In: Quantum Science and Technology (IF 6.568) , vol. 9, pp. 025014, 2024.
Abstract | Links:
@article{nokey,
title = {Experimental implementation of quantum-walk-based portfolio optimisation},
author = {Dengke Qu and Edric Matwiejew and Kunkun Wang and Jingbo Wang and Peng Xue},
doi = {10.1088/2058-9565/ad27e9},
year = {2024},
date = {2024-02-23},
urldate = {2024-02-01},
journal = {Quantum Science and Technology (IF 6.568) },
volume = {9},
pages = {025014},
abstract = {The application of quantum algorithms has attracted much attention as it holds the promise of solving practical problems that are intractable to classical algorithms. One such application is the recent development of a quantum-walk-based optimization algorithm approach to portfolio optimization under the modern portfolio theory framework. In this paper, we demonstrate an experimental realization of the alternating phase-shift and continuous-time quantum walk unitaries that underpin this quantum algorithm using optical networks and single photons. The experimental analysis confirms that the probability of states corresponding to high-quality solutions is efficiently amplified by increasing the number of phase-shift and quantum walk iterations. This work provides strong evidence for practical applications of quantum-walk-based algorithms such as financial portfolio optimization.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
The application of quantum algorithms has attracted much attention as it holds the promise of solving practical problems that are intractable to classical algorithms. One such application is the recent development of a quantum-walk-based optimization algorithm approach to portfolio optimization under the modern portfolio theory framework. In this paper, we demonstrate an experimental realization of the alternating phase-shift and continuous-time quantum walk unitaries that underpin this quantum algorithm using optical networks and single photons. The experimental analysis confirms that the probability of states corresponding to high-quality solutions is efficiently amplified by increasing the number of phase-shift and quantum walk iterations. This work provides strong evidence for practical applications of quantum-walk-based algorithms such as financial portfolio optimization.
Zhuang, Shengxin; Tanner, John; Wu, Yusen; Huynh, Du Q.; Cadet, Wei Liu Xavier F.; Fontaine, Nicolas; Charton, Philippe; Damour, Cedric; Cadet, Frederic; Wang, Jingbo
Non-Hemolytic Peptide Classification Using A Quantum Support Vector Machine Online
2024, visited: 06.02.2024.
Abstract | Links:
@online{nokey,
title = {Non-Hemolytic Peptide Classification Using A Quantum Support Vector Machine},
author = {Shengxin Zhuang and John Tanner and Yusen Wu and Du Q. Huynh and Wei Liu Xavier F. Cadet and Nicolas Fontaine and Philippe Charton and Cedric Damour and Frederic Cadet and Jingbo Wang},
url = {https://arxiv.org/abs/2402.03847},
year = {2024},
date = {2024-02-06},
urldate = {2024-02-06},
abstract = {Quantum machine learning (QML) is one of the most promising applications of quantum computation. However, it is still unclear whether quantum advantages exist when the data is of a classical nature and the search for practical, real-world applications of QML remains active. In this work, we apply the well-studied quantum support vector machine (QSVM), a powerful QML model, to a binary classification task which classifies peptides as either hemolytic or non-hemolytic. Using three peptide datasets, we apply and contrast the performance of the QSVM, numerous classical SVMs, and the best published results on the same peptide classification task, out of which the QSVM performs best. The contributions of this work include (i) the first application of the QSVM to this specific peptide classification task, (ii) an explicit demonstration of QSVMs outperforming the best published results attained with classical machine learning models on this classification task and (iii) empirical results showing that the QSVM is capable of outperforming many (and possibly all) classical SVMs on this classification task. This foundational work paves the way to verifiable quantum advantages in the field of computational biology and facilitates safer therapeutic development. },
keywords = {},
pubstate = {published},
tppubtype = {online}
}
Quantum machine learning (QML) is one of the most promising applications of quantum computation. However, it is still unclear whether quantum advantages exist when the data is of a classical nature and the search for practical, real-world applications of QML remains active. In this work, we apply the well-studied quantum support vector machine (QSVM), a powerful QML model, to a binary classification task which classifies peptides as either hemolytic or non-hemolytic. Using three peptide datasets, we apply and contrast the performance of the QSVM, numerous classical SVMs, and the best published results on the same peptide classification task, out of which the QSVM performs best. The contributions of this work include (i) the first application of the QSVM to this specific peptide classification task, (ii) an explicit demonstration of QSVMs outperforming the best published results attained with classical machine learning models on this classification task and (iii) empirical results showing that the QSVM is capable of outperforming many (and possibly all) classical SVMs on this classification task. This foundational work paves the way to verifiable quantum advantages in the field of computational biology and facilitates safer therapeutic development.
2023
Wu, Yusen; Huang, Zigeng; Sun, Jinzhao; Yuan, Xiao; Wang, Jingbo; Lv, Dingshun
Orbital Expansion Variational Quantum Eigensolver Journal Article
In: Quantum Science and Technology (Impact Factor 6.568), vol. 8, pp. 045030, 2023.
@article{nokey,
title = {Orbital Expansion Variational Quantum Eigensolver },
author = {Yusen Wu and Zigeng Huang and Jinzhao Sun and Xiao Yuan and Jingbo Wang and Dingshun Lv},
year = {2023},
date = {2023-09-27},
urldate = {2023-01-01},
journal = {Quantum Science and Technology (Impact Factor 6.568)},
volume = {8},
pages = {045030},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Wu, Yusen; Wu, Bujiao; Wang, Jingbo; Yuan, Xiao
Quantum Phase Recognition via Quantum Kernel Methods Journal Article
In: Quantum (Impact Factor 6.777), vol. 7, pp. 981, 2023.
@article{nokey,
title = {Quantum Phase Recognition via Quantum Kernel Methods},
author = {Yusen Wu and Bujiao Wu and Jingbo Wang and Xiao Yuan},
year = {2023},
date = {2023-03-01},
urldate = {2023-03-01},
journal = {Quantum (Impact Factor 6.777)},
volume = {7},
pages = {981},
abstract = {Can we use a quantum computer to speed up classical machine learning in solving problems of practical significance? Here, we study this open question focusing on the quantum phase learning problem, an important task in many-body quantum physics. We prove that, under widely believed complexity theory assumptions, quantum phase learning problem cannot be efficiently solved by machine learning algorithms using classical resources and classical data. Whereas using quantum data, we theoretically prove the universality of quantum kernel Alphatron in efficiently predicting quantum phases, indicating quantum advantages in this learning problem. We numerically benchmark the algorithm for a variety of problems, including recognizing symmetry-protected topological phases and symmetry-broken phases. Our results highlight the capability of quantum machine learning in efficient prediction of quantum phases.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Can we use a quantum computer to speed up classical machine learning in solving problems of practical significance? Here, we study this open question focusing on the quantum phase learning problem, an important task in many-body quantum physics. We prove that, under widely believed complexity theory assumptions, quantum phase learning problem cannot be efficiently solved by machine learning algorithms using classical resources and classical data. Whereas using quantum data, we theoretically prove the universality of quantum kernel Alphatron in efficiently predicting quantum phases, indicating quantum advantages in this learning problem. We numerically benchmark the algorithm for a variety of problems, including recognizing symmetry-protected topological phases and symmetry-broken phases. Our results highlight the capability of quantum machine learning in efficient prediction of quantum phases.
Sotelo, Rafael; Wang, Jingbo; Nakamura, Yuichi; Farouk, Ahmed; Arjona, Rosario; Andraca, Salvador Venegas; James, Alex; Venegas-Gomez, Araceli; Gonzalez, Bill
The first Workshop on Quantum in Consumer Technology at IEEE Quantum Week Journal Article
In: IEEE Consumer Electronics Magazine (Impact Factor 4.135), vol. 2162, pp. 2256, 2023.
@article{nokey,
title = {The first Workshop on Quantum in Consumer Technology at IEEE Quantum Week},
author = {Sotelo, Rafael and Wang, Jingbo and Nakamura, Yuichi and Farouk, Ahmed and Arjona, Rosario and Andraca, Salvador Venegas and James, Alex and Venegas-Gomez, Araceli and Gonzalez, Bill},
doi = {10.1109/MCE.2023.3243380},
year = {2023},
date = {2023-02-01},
urldate = {2023-02-01},
journal = {IEEE Consumer Electronics Magazine (Impact Factor 4.135)},
volume = {2162},
pages = {2256},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Matwiejew, Edric; Pye, Jason; Wang, Jingbo B.
Quantum Optimisation for Continuous Multivariable Functions by a Structured Search Journal Article
In: Quantum Science and Technology (Impact Factor 6.568) - In Press (formally accepted) , vol. 8, pp. 045013, 2023.
Abstract | Links:
@article{nokey,
title = {Quantum Optimisation for Continuous Multivariable Functions by a Structured Search},
author = {Edric Matwiejew and Jason Pye and Jingbo B. Wang},
doi = {10.1088/2058-9565/ace6cc},
year = {2023},
date = {2023-01-10},
urldate = {2023-01-10},
journal = {Quantum Science and Technology (Impact Factor 6.568) - In Press (formally accepted) },
volume = {8},
pages = {045013},
abstract = {Solving optimisation problems is a promising near-term application of quantum computers. Quantum variational algorithms leverage quantum superposition and entanglement to optimise over exponentially large solution spaces using an alternating sequence of classically tunable unitaries. However, prior work has primarily addressed discrete optimisation problems. In addition, these algorithms have been designed generally under the assumption of an unstructured solution space, which constrains their speedup to the theoretical limits for the unstructured Grover's quantum search algorithm. In this paper, we show that quantum variational algorithms can efficiently optimise continuous multivariable functions by exploiting general structural properties of a discretised continuous solution space with a convergence that exceeds the limits of an unstructured quantum search. We introduce the Quantum Multivariable Optimisation Algorithm (QMOA) and demonstrate its advantage over pre-existing methods, particularly when optimising high-dimensional and oscillatory functions.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Solving optimisation problems is a promising near-term application of quantum computers. Quantum variational algorithms leverage quantum superposition and entanglement to optimise over exponentially large solution spaces using an alternating sequence of classically tunable unitaries. However, prior work has primarily addressed discrete optimisation problems. In addition, these algorithms have been designed generally under the assumption of an unstructured solution space, which constrains their speedup to the theoretical limits for the unstructured Grover's quantum search algorithm. In this paper, we show that quantum variational algorithms can efficiently optimise continuous multivariable functions by exploiting general structural properties of a discretised continuous solution space with a convergence that exceeds the limits of an unstructured quantum search. We introduce the Quantum Multivariable Optimisation Algorithm (QMOA) and demonstrate its advantage over pre-existing methods, particularly when optimising high-dimensional and oscillatory functions.
Bennett, Tavis; Wang, Jingbo
Quantum optimisation via maximally amplified states Journal Article Forthcoming
In: arXiv:2111.00796, Forthcoming.
@article{nokey,
title = {Quantum optimisation via maximally amplified states},
author = {Tavis Bennett and Jingbo Wang},
year = {2023},
date = {2023-01-01},
urldate = {2023-01-01},
journal = {arXiv:2111.00796},
keywords = {},
pubstate = {forthcoming},
tppubtype = {article}
}
2022
Qu, Dengke; Marsh, Samuel; Wang, Kunkun; Xiao, Lei; Wang, Jingbo; Xue, Peng
Deterministic Search on Star Graphs via Quantum Walks Journal Article
In: Physical Review Letters (IF 9.161), vol. 128, iss. 5, pp. 050501, 2022.
Abstract | Links:
@article{PhysRevLett.128.050501,
title = {Deterministic Search on Star Graphs via Quantum Walks},
author = {Dengke Qu and Samuel Marsh and Kunkun Wang and Lei Xiao and Jingbo Wang and Peng Xue},
url = {https://link.aps.org/doi/10.1103/PhysRevLett.128.050501},
doi = {10.1103/PhysRevLett.128.050501},
year = {2022},
date = {2022-08-01},
urldate = {2022-08-01},
journal = {Physical Review Letters (IF 9.161)},
volume = {128},
issue = {5},
pages = {050501},
publisher = {American Physical Society},
abstract = {We propose a novel algorithm for quantum spatial search on a star graph using interleaved continuous-time quantum walks and marking oracle queries. Initializing the system in the star’s central vertex, we determine the optimal quantum walk times to reach full overlap with the marked state using ⌈(π/4)√N−(1/2)⌉ oracle queries, matching the well-known lower bound of Grover’s search. We implement the deterministic search in a database of size seven on photonic quantum hardware, and demonstrate the effective scaling of the approach up to size 115. This is the first experimental demonstration of quantum walk-based search on the highly noise-resistant star graph, which provides new evidence for the applications of quantum walk in quantum algorithms and quantum information processing.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
We propose a novel algorithm for quantum spatial search on a star graph using interleaved continuous-time quantum walks and marking oracle queries. Initializing the system in the star’s central vertex, we determine the optimal quantum walk times to reach full overlap with the marked state using ⌈(π/4)√N−(1/2)⌉ oracle queries, matching the well-known lower bound of Grover’s search. We implement the deterministic search in a database of size seven on photonic quantum hardware, and demonstrate the effective scaling of the approach up to size 115. This is the first experimental demonstration of quantum walk-based search on the highly noise-resistant star graph, which provides new evidence for the applications of quantum walk in quantum algorithms and quantum information processing.
Wu, Yusen; Wang, Jingbo
Estimating Gibbs partition function with quantum Clifford sampling Journal Article
In: Quantum Science and Technology (IF 6.568) , vol. 7, pp. 025006, 2022.
@article{nokey,
title = {Estimating Gibbs partition function with quantum Clifford sampling},
author = { Yusen Wu and Jingbo Wang},
year = {2022},
date = {2022-07-01},
urldate = {2022-07-01},
journal = {Quantum Science and Technology (IF 6.568) },
volume = {7},
pages = {025006},
abstract = {The partition function is an essential quantity in statistical mechanics, and its accurate computation is a key component of any statistical analysis of quantum systems and phenomena. However, for interacting many-body quantum systems, its calculation generally involves summing over an exponential number of terms and can thus quickly grow to be intractable. Accurately and efficiently estimating the partition function of its corresponding system Hamiltonian then becomes the key in solving quantum many-body problems. In this paper we develop a hybrid quantum-classical algorithm to estimate the partition function, utilizing a novel Clifford sampling technique. Note that previous works on the estimation of partition functions require $mathcal{O}(1/epsilonsqrt{Delta})$-depth quantum circuits, where $Delta$ is the minimum spectral gap of stochastic matrices and $epsilon$ is the multiplicative error. Our algorithm requires only a shallow $mathcal{O}(1)$-depth quantum circuit, repeated $mathcal{O}(n/epsilon^2)$ times, to provide a comparable $epsilon$ approximation. Shallow-depth quantum circuits are considered vitally important for currently available NISQ (Noisy Intermediate-Scale Quantum) devices.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
The partition function is an essential quantity in statistical mechanics, and its accurate computation is a key component of any statistical analysis of quantum systems and phenomena. However, for interacting many-body quantum systems, its calculation generally involves summing over an exponential number of terms and can thus quickly grow to be intractable. Accurately and efficiently estimating the partition function of its corresponding system Hamiltonian then becomes the key in solving quantum many-body problems. In this paper we develop a hybrid quantum-classical algorithm to estimate the partition function, utilizing a novel Clifford sampling technique. Note that previous works on the estimation of partition functions require $mathcal{O}(1/epsilonsqrt{Delta})$-depth quantum circuits, where $Delta$ is the minimum spectral gap of stochastic matrices and $epsilon$ is the multiplicative error. Our algorithm requires only a shallow $mathcal{O}(1)$-depth quantum circuit, repeated $mathcal{O}(n/epsilon^2)$ times, to provide a comparable $epsilon$ approximation. Shallow-depth quantum circuits are considered vitally important for currently available NISQ (Noisy Intermediate-Scale Quantum) devices.
Matwiejew, Edric; Wang, Jingbo
QuOp_MPI: A framework for parallel simulation of quantum variational algorithms Journal Article
In: Journal of Computational Science (IF 3.817), vol. 62, pp. 101711, 2022.
@article{nokey,
title = {QuOp_MPI: A framework for parallel simulation of quantum variational algorithms},
author = {Edric Matwiejew and Jingbo Wang },
year = {2022},
date = {2022-06-08},
urldate = {2022-06-08},
journal = {Journal of Computational Science (IF 3.817)},
volume = {62},
pages = {101711},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
2021
Bennett, T.; Matwiejew, E.; Marsh, S.; Wang, J. B.
Quantum Walk-Based Vehicle Routing Optimisation Journal Article
In: Frontiers in Physics (IF 3.563), vol. 9, pp. 730856, 2021.
Abstract | Links:
@article{nokey,
title = {Quantum Walk-Based Vehicle Routing Optimisation},
author = {T. Bennett and E. Matwiejew and S. Marsh and J. B. Wang},
url = {https://www.frontiersin.org/articles/10.3389/fphy.2021.730856/full?utm_source=dlvr.it&utm_medium=twitter},
doi = {10.3389/fphy.2021.730856},
year = {2021},
date = {2021-12-20},
urldate = {2021-12-20},
journal = {Frontiers in Physics (IF 3.563)},
volume = {9},
pages = {730856},
abstract = {This paper demonstrates the applicability of the Quantum Walk-based Optimisation Algorithm (QWOA) to the Capacitated Vehicle Routing Problem (CVRP). Efficient algorithms are developed for the indexing and un-indexing of the solution space and for implementing the required alternating phase-walk unitaries, which are the core components of QWOA. Results of numerical simulation demonstrate that the QWOA is capable of producing convergence to near-optimal solutions for a randomly generated eight location CVRP. Preparation of the amplified quantum state in this example problem is demonstrated to produce higher-quality solutions than expected from a classical random sampling of equivalent computational effort.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
This paper demonstrates the applicability of the Quantum Walk-based Optimisation Algorithm (QWOA) to the Capacitated Vehicle Routing Problem (CVRP). Efficient algorithms are developed for the indexing and un-indexing of the solution space and for implementing the required alternating phase-walk unitaries, which are the core components of QWOA. Results of numerical simulation demonstrate that the QWOA is capable of producing convergence to near-optimal solutions for a randomly generated eight location CVRP. Preparation of the amplified quantum state in this example problem is demonstrated to produce higher-quality solutions than expected from a classical random sampling of equivalent computational effort.
Marsh, Samuel; Wang, Jingbo
A framework for optimal quantum spatial search using alternating phase-walks Journal Article
In: Quantum Science and Technology (IF 6.568), vol. 6, no. 4, pp. 045029, 2021.
Abstract | Links:
@article{Marsh_2021,
title = {A framework for optimal quantum spatial search using alternating phase-walks},
author = {Samuel Marsh and Jingbo Wang},
url = {https://iopscience.iop.org/article/10.1088/2058-9565/ac26af},
doi = {10.1088/2058-9565/ac26af},
year = {2021},
date = {2021-09-28},
urldate = {2021-09-28},
journal = {Quantum Science and Technology (IF 6.568)},
volume = {6},
number = {4},
pages = {045029},
publisher = {IOP Publishing},
abstract = {We present a novel methodological framework for quantum spatial search, generalising the Childs & Goldstone () 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 search on a variety of graphs. One important class is the n × n 3 rook graph, which has N = n 4 vertices. On this class of graphs the algorithm performs suboptimally, achieving only overlap after time . Using the new alternating phase-walk framework, we show that overlap is obtained in phase-walk iterations.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
We present a novel methodological framework for quantum spatial search, generalising the Childs & Goldstone () 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 search on a variety of graphs. One important class is the n × n 3 rook graph, which has N = n 4 vertices. On this class of graphs the algorithm performs suboptimally, achieving only overlap after time . Using the new alternating phase-walk framework, we show that overlap is obtained in phase-walk iterations.
Marsh, S.; Wang, J. B.
Deterministic spatial search using alternating quantum walks Journal Article
In: Physical Review A (IF 3.140), vol. 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},
urldate = {2021-08-24},
journal = {Physical Review A (IF 3.140)},
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}
}
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.
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 (IF 3.740), vol. 23, no. 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},
urldate = {2021-08-01},
journal = {New Journal of Physics (IF 3.740)},
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}
}
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.
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 (IF 14.140), vol. 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},
urldate = {2021-02-26},
journal = {Science Advances (IF 14.140)},
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}
}
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.
Matwiejew, Edric; Wang, Jingbo
QSW_MPI: A framework for parallel simulation of quantum stochastic walks Journal Article
In: Computer Physics Communications (IF 4.390), vol. 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},
urldate = {2021-01-01},
journal = {Computer Physics Communications (IF 4.390)},
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}
}
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.
Slate, N; Matwiejew, E; Marsh, S; Wang, J B
Quantum walk-based portfolio optimisation Journal Article
In: Quantum (IF 6.777), vol. 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},
urldate = {2021-01-01},
journal = {Quantum (IF 6.777)},
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}
}
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.
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: Physical Review Letters (IF 9.161), vol. 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},
urldate = {2020-12-01},
journal = {Physical Review Letters (IF 9.161)},
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}
}
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.
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 (IF 11.104), vol. 7, no. 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},
urldate = {2020-11-01},
journal = {Optica (IF 11.104)},
volume = {7},
number = {11},
pages = {1524--1530},
publisher = {OSA},
abstract = {PageRank is an algorithm used by Google Search to rank web pages in their search engine results. An important step for quantum networks is to quantize the classical protocol as quantum mechanics provides computational resources that can be used to outperform classical algorithms. In this paper, we experimentally realize continuous-time quantum walks for directed graphs with non-Hermitian adjacency matrices by using linear optical circuits and single photons. We find that the node classical centrality in a directed graph is correlated with the maximum node probability resulting from a continuous-time quantum walk and then demonstrate PageRank. Our work opens up an avenue of applications of quantum information in real-life tasks.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
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.
Schofield, Callum; Wang, Jingbo B; Li, Yuying
Quantum walk inspired algorithm for graph similarity and isomorphism Journal Article
In: Quantum Information Processing (IF 2.349), vol. 19, no. 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},
urldate = {2020-08-24},
journal = {Quantum Information Processing (IF 2.349)},
volume = {19},
number = {9},
pages = {281},
abstract = {Large-scale complex systems, such as social networks, electrical power grid, database structure, consumption pattern or brain connectivity, are often modelled using network graphs. Valuable insight can be gained by measuring similarity between network graphs in order to make quantitative comparisons. Since these networks can be very large, scalability and efficiency of the algorithm are key concerns. More importantly, for graphs with unknown labelling, this graph similarity problem requires exponential time to solve using existing algorithms. In this paper, we propose a quantum walk inspired algorithm, which provides a solution to the graph similarity problem without prior knowledge on graph labelling. This algorithm is capable of distinguishing between minor structural differences, such as between strongly regular graphs with the same parameters. The algorithm has a polynomial complexity, scaling with $$O(n^9)$$O(n9).},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
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).
Marsh, S; Wang, J B
Combinatorial optimization via highly efficient quantum walks Journal Article
In: Phys. Rev. Research, vol. 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}
}
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.
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 (IF 3.772), vol. 63, no. 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},
urldate = {2020-01-01},
journal = {Computers, Materials & Continua (IF 3.772)},
volume = {63},
number = {3},
pages = {1237--1247},
abstract = {The Quantum Approximate Optimization Algorithm (QAOA) is an
algorithmic framework for finding approximate solutions to combinatorial optimization
problems. It consists of interleaved unitary transformations induced by two operators
labelled the mixing and problem Hamiltonians. To fit this framework, one needs to
transform the original problem into a suitable form and embed it into these two
Hamiltonians. In this paper, for the well-known NP-hard Traveling Salesman Problem
(TSP), we encode its constraints into the mixing Hamiltonian rather than the conventional
approach of adding penalty terms to the problem Hamiltonian. Moreover, we map edges
(routes) connecting each pair of cities to qubits, which decreases the search space
significantly in comparison to other approaches. As a result, our method can achieve a
higher probability for the shortest round-trip route with only half the number of qubits
consumed compared to IBM Q’s approach. We argue the formalization approach
presented in this paper would lead to a generalized framework for finding, in the context
of QAOA, high-quality approximate solutions to NP optimization problems.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
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.
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}
}
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.
Jay, Gareth; Debbasch, Fabrice; Wang, Jingbo
A systematic method to building Dirac quantum walks coupled to electromagnetic fields Journal Article
In: Quantum Information Processing (IF 2.349), vol. 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},
urldate = {2020-01-01},
journal = {Quantum Information Processing (IF 2.349)},
volume = {19},
pages = {422},
abstract = {A quantum walk whose continuous limit coincides with Dirac equation is usually called a Dirac quantum walk (DQW). A new systematic method to build DQWs coupled to electromagnetic (EM) fields is introduced and put to test on several examples of increasing difficulty. It is first used to derive the EM coupling of a 3D walk on the cubic lattice. Recently introduced DQWs on the triangular lattice are then re-derived, showing for the first time that these are the only DQWs that can be defined with spinors living on the vertices of these lattices. As a third example of the method’s effectiveness, a new 3D walk on a parallelepiped lattice is derived. As a fourth, negative example, it is shown that certain lattices like the rhombohedral lattice cannot be used to build DQWs. The effect of changing representation in the Dirac equation is also discussed. Furthermore, we show the simulation of the established DQWs can be efficiently implemented on a quantum computer.
},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
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.
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 (IF 2.349), vol. 18, no. 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},
urldate = {2019-08-20},
journal = {Quantum Information Processing (IF 2.349)},
volume = {18},
number = {10},
pages = {302},
abstract = {Graph comparison is an established NP-hard problem. In this paper, we present an efficiently scaling quantum algorithm which finds the size of the maximum common edge subgraph for any pair of unlabelled graphs and thus provides a meaningful measure of graph similarity. The algorithm makes use of a two-part quantum dynamic process: in the first part, we obtain information crucial for the comparison of two graphs through linear quantum computation. However, this information is hidden in the quantum system with such a vanishingly small amplitude that even quantum algorithms such as Grover's search are not fast enough to distil it efficiently. In order to extract the information, we call upon techniques in nonlinear quantum computing to provide the speed-up necessary for an efficient algorithm. The linear quantum circuit requires $$backslashmathcal O(n^3 backslashlog ^3 (n) backslashlog backslashlog (n))$$O(n3log3(n)loglog(n))elementary quantum gates, and the nonlinear evolution under the Gross--Pitaevskii equation has a time scaling of $$backslashmathcal O(backslashfrac1g n^2 backslashlog ^3 (n) backslashlog backslashlog (n))$$O(1gn2log3(n)loglog(n)), where n is the number of vertices in each graph and g is the strength of the Gross--Pitaevskii nonlinearity. Through this example, we demonstrate the power of nonlinear quantum search techniques to solve a subset of NP-hard problems.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
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.
Yu, Chao-Hua; Gao, Fei; Lin, Song; Wang, Jingbo
Quantum data compression by principal component analysis Journal Article
In: Quantum Information Processing (IF 2.349), vol. 18, no. 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},
urldate = {2019-07-01},
journal = {Quantum Information Processing (IF 2.349)},
volume = {18},
number = {8},
pages = {249},
abstract = {Data compression can be achieved by reducing the dimensionality of high-dimensional but approximately low-rank datasets, which may in fact be described by the variation of a much smaller number of parameters. It often serves as a preprocessing step to surmount the curse of dimensionality and to gain efficiency, and thus it plays an important role in machine learning and data mining. In this paper, we present a quantum algorithm that compresses an exponentially large high-dimensional but approximately low-rank dataset in quantum parallel, by dimensionality reduction (DR) based on principal component analysis (PCA), the most popular classical DR algorithm. We show that the proposed algorithm has a runtime polylogarithmic in the dataset's size and dimensionality, which is exponentially faster than the classical PCA algorithm, when the original dataset is projected onto a polylogarithmically low-dimensional space. The compressed dataset can then be further processed to implement other tasks of interest, with significantly less quantum resources. As examples, we apply this algorithm to reduce data dimensionality for two important quantum machine learning algorithms, quantum support vector machine and quantum linear regression for prediction. This work demonstrates that quantum machine learning can be released from the curse of dimensionality to solve problems of practical importance.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
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.
Sett, A; Pan, H; Falloon, P E; Wang, J B
Zero transfer in continuous-time quantum walks Journal Article
In: Quantum Information Processing (IF 2.349), vol. 18, no. 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},
urldate = {2019-04-10},
journal = {Quantum Information Processing (IF 2.349)},
volume = {18},
number = {5},
pages = {159},
abstract = {In this paper, we show how using complex-valued edge weights in a graph can completely suppress the flow of probability amplitude in a continuous-time quantum walk to specific vertices of the graph when the edge weights, graph topology, and initial state of the quantum walk satisfy certain conditions. The conditions presented in this paper are derived from the so-called chiral quantum walk, a variant of the continuous-time quantum walk which incorporates directional bias with respect to site transfer probabilities between vertices of a graph by using complex edge weights. We examine the necessity to break the time-reversal symmetry in order to achieve zero transfer in continuous-time quantum walks. We also consider the effect of decoherence on zero transfer and suggest that this phenomenon may be used to detect and quantify decoherence in the system.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
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.
Jay, Gareth; Debbasch, Fabrice; Wang, J B
Dirac quantum walks on triangular and honeycomb lattices Journal Article
In: Physical Review A (IF 3.140), vol. 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},
urldate = {2019-03-01},
journal = {Physical Review A (IF 3.140)},
volume = {99},
pages = {032113},
publisher = {American Physical Society},
abstract = {In this paper, we present a detailed study on discrete-time Dirac quantum walks (DQWs) on triangular and honeycomb lattices. At the continuous limit, these DQWs coincide with the Dirac equation. Their differences in the discrete regime are analyzed through the dispersion relations, with special emphasis on Zitterbewegung. An extension which couples these walks to arbitrary discrete electromagnetic field is also proposed and the resulting Bloch oscillations are discussed.
},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
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.
Yu, Chao-Hua; Gao, Fei; Liu, Chenghuan; Huynh, Du; Reynolds, Mark; Wang, Jingbo
Quantum algorithm for visual tracking Journal Article
In: Physical Review A (IF 3.140), vol. 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},
urldate = {2019-02-01},
journal = {Physical Review A (IF 3.140)},
volume = {99},
pages = {022301},
publisher = {American Physical Society},
abstract = {Visual tracking (VT) is the process of locating a moving object of interest in a video. It is a fundamental problem in computer vision, with various applications in human-computer interaction, security and surveillance, robot perception, traffic control, etc. In this paper, we address this problem for the first time in the quantum setting, and present a quantum algorithm for VT based on the framework proposed by Henriques et al. [IEEE Trans. Pattern Anal. Mach. Intell., 7, 583 (2015)]. Our algorithm comprises two phases: training and detection. In the training phase, in order to discriminate the object and background, the algorithm trains a ridge regression classifier in the quantum state form where the optimal fitting parameters of ridge regression are encoded in the amplitudes. In the detection phase, the classifier is then employed to generate a quantum state whose amplitudes encode the responses of all the candidate image patches. The algorithm is shown to be polylogarithmic in scaling, when the image data matrices have low condition numbers, and therefore may achieve exponential speedup over the best classical counterpart. However, only quadratic speedup can be achieved when the algorithm is applied to implement the ultimate task of Henriques's framework, i.e., detecting the object position. We also discuss two other important applications related to VT: (1) object disappearance detection and (2) motion behavior matching, where much more significant speedup over the classical methods can be achieved. This work demonstrates the power of quantum computing in solving computer vision problems.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
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.
Marsh, S; Wang, J B
A quantum walk-assisted approximate algorithm for bounded NP optimisation problems Journal Article
In: Quantum Information Processing (IF 2.349), vol. 18, no. 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},
urldate = {2019-01-16},
journal = {Quantum Information Processing (IF 2.349)},
volume = {18},
number = {3},
pages = {61},
abstract = {This paper describes an application of the quantum approximate optimisation algorithm (QAOA) to efficiently find approximate solutions for computational problems contained in the polynomially bounded NP optimisation complexity class (NPO PB). We consider a generalisation of the QAOA state evolution to alternating quantum walks and solution-quality-dependent phase shifts and use the quantum walks to integrate the problem constraints of NPO problems. We apply the concept of a hybrid quantum-classical variational scheme to attempt finding the highest expectation value, which contains a high-quality solution. We synthesise an efficient quantum circuit for the constrained optimisation algorithm, and we numerically demonstrate the behaviour of the circuit with respect to an illustrative NP optimisation problem with constraints, minimum vertex cover. With examples, this paper demonstrates that the degree of accuracy to which the quantum walks are simulated can be treated as an additional optimisation parameter, leading to improved results.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
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.
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 (IF 38.770), vol. 12, no. 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},
urldate = {2018-09-01},
journal = {Nature Photonics (IF 38.770)},
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}
}
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.
de Lacy, K; Noakes, L; Twamley, J; Wang, J B
Controlled quantum search Journal Article
In: Quantum Information Processing (IF 2.349), vol. 17, no. 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},
urldate = {2018-08-28},
journal = {Quantum Information Processing (IF 2.349)},
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}
}
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.
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 Proceedings Article
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}
}
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.
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: Physical Review A (IF 3.140), vol. 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},
urldate = {2017-09-01},
journal = {Physical Review A (IF 3.140)},
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}
}
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.
Izaac, J A; Wang, J B
Systematic dimensionality reduction for continuous-time quantum walks of interacting fermions Journal Article
In: Physical Review E (IF 2.529), vol. 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},
urldate = {2017-09-01},
journal = {Physical Review E (IF 2.529)},
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}
}
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.
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: Physical Review A (IF 3.140), vol. 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},
urldate = {2017-03-01},
journal = {Physical Review A (IF 3.140)},
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}
}
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.
Zhou, S S; Loke, T; Izaac, J A; Wang, J B
Quantum Fourier transform in computational basis Journal Article
In: Quantum Information Processing (IF 2.349), vol. 16, no. 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},
urldate = {2017-02-10},
journal = {Quantum Information Processing (IF 2.349)},
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}
}
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.
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 (IF 4.390), vol. 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},
urldate = {2017-01-01},
journal = {Computer Physics Communications (IF 4.390)},
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}
}
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.
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 (IF 14.920), vol. 7, no. 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},
urldate = {2017-01-01},
journal = {Nature communications (IF 14.920)},
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}
}
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.
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 (IF 2.066), vol. 381, no. 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},
urldate = {2017-01-01},
journal = {Physics Letters A (IF 2.066)},
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.
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 (IF 2.132), vol. 50, no. 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},
urldate = {2017-01-01},
journal = {Journal of Physics A: Mathematical and Theoretical (IF 2.132)},
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}
}
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.
Zhou, S S; Wang, J B
Efficient quantum circuits for dense circulant and circulant like operators Journal Article
In: Royal Society Open Science, vol. 4, no. 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}
}
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.
Loke, T; Wang, J B
Efficient quantum circuits for Szegedy quantum walks Journal Article
In: Annals of Physics (IF 2.730), vol. 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},
urldate = {2017-01-01},
journal = {Annals of Physics (IF 2.730)},
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}
}
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.