research-article

Optimal control of traffic signals using quantum annealing

Authors:

Hasham Hussain,

Muhammad Bin Javaid,

Faisal Shah Khan,

Archismita Dalal,

Aeysha KhaliqueAuthors Info & Claims

Quantum Information Processing, Volume 19, Issue 9

https://doi.org/10.1007/s11128-020-02815-1

Published: 24 August 2020 Publication History

Abstract

Quadratic unconstrained binary optimization (QUBO) is the mathematical formalism for phrasing and solving a class of optimization problems that are combinatorial in nature. Due to their natural equivalence with the two-dimensional Ising model for ferromagnetism in statistical mechanics, problems from the QUBO class can be solved on quantum annealing hardware. In this paper, we report a QUBO formatting of the problem of optimal control of time-dependent traffic signals on an artificial grid-structured road network so as to ease the flow of traffic, and the use of D-Wave Systems’ quantum annealer to solve it. Since current-generation D-Wave annealers have a limited number of qubits and limited inter-qubit connectivity, we adopt a hybrid (classical/quantum) approach to this problem. As traffic flow is a continuous and evolving phenomenon, we address this time-dependent problem by adopting a workflow to generate and solve multiple problem instances periodically.

References

[1]

Moore G Cramming more components onto integrated circuits Electronics 1965 38 8

[2]

IDQuantique. Random Numbers Generation using Quantum Physics. https://marketing.idquantique.com/acton/attachment/11868/f-0227/1/-/-/-/-/Quantum%20RNG_White%20Paper.pdf

[3]

Systems, D.W.: Introduction to quantum annealing. https://docs.dwavesys.com/docs/latest/c_gs_2.html

[4]

Arute F, Arya K, Babbush R, et al.Quantum supremacy using a programmable superconducting processorNature2019574505-5102019Natur.574.505A

[5]

Wright K et al.Benchmarking an 11-qubit quantum computerNat. Commun.20191054642019NatCo.10.5464W

[6]

Grover, L.: A fast quantum mechanical algorithm for database search. In: Proceedings, 28th Annual ACM Symposium on the Theory of Computing. p. 212 (1996)

[7]

Shor, P.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc. Press (1994)

[8]

McGeoch CC Adiabatic Quantum Computation and Quantum Annealing: Theory and Practice 2014 San Rafael Morgan & Claypool Publishers

[9]

McGeoch, C.C., Wang, C.: Experimental evaluation of an adiabiatic quantum system for combinatorial optimization. In: Proceedings of the ACM International Conference on Computing Frontiers (CF ’13), pp. 23:1–23:11. ACM, New York (2013). 10.1145/2482767.2482797

[10]

Bian, Z., Chudak, F., Macready, W.G., Rose, G.: The Ising model: teaching an old problem new tricks. D-Wave Syst. 2 (2010)

[11]

Neukart F, Compostella G, Seidel C, von Dollen D, Yarkoni S, and Parney B Traffic flow optimization using a quantum annealer Front. ICT 2017 4 29

[12]

Hernandez M and Aramon MEnhancing quantum annealing performance for the molecular similarity problemQuantum Inf. Process.20171651332017QuIP...16.133H36333971373.81141

[13]

Li RY, Di Felice R, Rohs R, and Lidar DAQuantum annealing versus classical machine learning applied to a simplified computational biology problemNPJ Quantum Inf.20184142018npjQI...4...14L

[14]

Bunyk PI, Hoskinson EM, Johnson MW, Tolkacheva E, Altomare F, Berkley AJ, Harris R, Hilton JP, Lanting T, Przybysz AJ, and Whittaker J Architectural considerations in the design of a superconducting quantum annealing processor IEEE Trans. Appl. Supercond. 2014 24 4 1

[15]

Cai, J. Macready, W.G., Roy, A.: A practical heuristic for finding graph minors (2014). arXiv preprint arXiv:1406.2741

[16]

Booth, M., Reinhardt, S.P., Roy, A.: Partitioning optimization problems forhybrid classical/quantum execution. https://www.dwavesys.com/sites/default/files/partitioning_QUBOs_for_ quantum_acceleration-2.pdf (2017)

[17]

Glover FFuture paths for integer programming and links to artificialComput. Oper. Res.198613533868908

[18]

Systems, D.W.: Hybrid solvers. https://docs.ocean.dwavesys.com/en/latest/overview/hybrid.html

[19]

D-wave: The quantum computing company. www.dwavesys.com/take-leap (2018). Accessed 30 Sept 2018

[20]

Studer, L., Ketabdari, M., Marchionni, G.: Analysis of adaptive traffic control systems design of a decision support system for better choices. J. Civil Environ. Eng. 05 (2015). 10.4172/2165-784X.1000195

[21]

Code available at: https://github.com/mbinjavaid/traffic-signals-qubo

[22]

Systems, D.W.: D-Wave hybrid solver service: an overview. https://www.dwavesys.com/sites/default/files/14-1039A-A_D-Wave_ Hybrid_ Solver_Service_ An_ Overview.pdf

[23]

Shaydulin R, Ushijima-Mwesigwa H, Negre C, Safro I, Mniszewski S, and Alexeev Y A hybrid approach for solving optimization problems on small quantum computers Computer 2019 52 18

[24]

Venegas-Andraca SE, Cruz-Santos W, McGeoch C, and Lanzagorta MA cross-disciplinary introduction to quantum annealing-based algorithmsContemp. Phys.20185921742018ConPh.59.174V

[25]

D-wave previews next-generation quantum computing platform-d-wave systems. www.dwavesys.com/press-releases/d-wave-previews-next-generation-quantum-computing-platform (2018). Accessed 30 Sept 2018

Cited By

Gomes CFernandes JFalcao GKar STayur S(2024)A Systematic Mapping Study on Quantum and Quantum-inspired Algorithms in Operations ResearchACM Computing Surveys10.1145/370087457:3(1-35)Online publication date: 11-Nov-2024
https://dl.acm.org/doi/10.1145/3700874
Chitty DCharles JMoraglio AKeedwell ELi XHandl J(2024)Applying a Quantum Annealer to the Traffic Assignment ProblemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654131(814-822)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654131
Gemeinhardt FGarmendia AWimmer MWeder BLeymann F(2023)Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping StudyACM Computing Surveys10.1145/362066856:3(1-36)Online publication date: 5-Oct-2023
https://dl.acm.org/doi/10.1145/3620668
Show More Cited By

Index Terms

Optimal control of traffic signals using quantum annealing

Index terms have been assigned to the content through auto-classification.

Recommendations

Do multipartite correlations speed up adiabatic quantum computation or quantum annealing?

Quantum correlations are thought to be the reason why certain quantum algorithms overcome their classical counterparts. Since the nature of this resource is still not fully understood, we shall investigate how multipartite entanglement and non-locality ...
Searching B-Smooth Numbers Using Quantum Annealing: Applications to Factorization and Discrete Logarithm Problem
Computational Science – ICCS 2023
Abstract
Integer factorization and discrete logarithm problem, two problems of classical public-key cryptography, are vulnerable to quantum attacks, especially polynomial-time Shor’s algorithm, which has to be run on the general-purpose quantum computer. ...
Non-Hermitian quantum annealing in the antiferromagnetic Ising chain

A non-Hermitian quantum optimization algorithm is created and used to find the ground state of an antiferromagnetic Ising chain. We demonstrate analytically and numerically (for up to $$N=1,024$$N=1,024 spins) that our approach leads to a significant ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Quantum Information Processing

Quantum Information Processing Volume 19, Issue 9

Sep 2020

1112 pages

ISSN:1570-0755

Issue’s Table of Contents

© Springer Science+Business Media, LLC, part of Springer Nature 2020.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 24 August 2020

Accepted: 12 August 2020

Received: 26 March 2020

Author Tags

Qualifiers

Research-article

Funding Sources

Major Innovation Fund, Government of Alberta, Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gomes CFernandes JFalcao GKar STayur S(2024)A Systematic Mapping Study on Quantum and Quantum-inspired Algorithms in Operations ResearchACM Computing Surveys10.1145/370087457:3(1-35)Online publication date: 11-Nov-2024
https://dl.acm.org/doi/10.1145/3700874
Chitty DCharles JMoraglio AKeedwell ELi XHandl J(2024)Applying a Quantum Annealer to the Traffic Assignment ProblemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654131(814-822)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654131
Gemeinhardt FGarmendia AWimmer MWeder BLeymann F(2023)Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping StudyACM Computing Surveys10.1145/362066856:3(1-36)Online publication date: 5-Oct-2023
https://dl.acm.org/doi/10.1145/3620668
Osaba EVillar-Rodriguez EOregi IMoreno-Fernandez-de-Leceta AKrawiec K(2021)Focusing on the hybrid quantum computing - Tabu search algorithmProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3463123(1476-1482)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3463123
Silva CAguiar ALima PDutra I(2021)Mapping a logical representation of TSP to quantum annealingQuantum Information Processing10.1007/s11128-021-03321-820:12Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1007/s11128-021-03321-8

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents