量子近似最佳化演算法（Quantum Approximate Optimization Algorithm, QAOA）透過混合量子－古典框架，正迅速發展成為現階段求解組合最佳化的一種可行手段。在無號誌交叉路口下的聯網自動駕駛汽車 (Connected and Automated Vehicles, CAVs）協同調度可被視為一個組合最佳化問題，其目標是在避免衝突的前提下最小化整體車輛等待時間。然而，在高密度連續車流情境中，若將每台車輛或車隊直接編碼，則所需 qubits 會隨車輛數快速成長，會使得傳統 QAOA 難以直接應用於路口即時調度。
為解決此問題，我們提出一個基於時間分段的組合最佳化量子計算框架，用於無號誌交叉路口下的 CAV 調度。透過將路口的通行狀態編碼建構 Quadratic Unconstrained Binary Optimization (QUBO) 模型，並透過將連續車流切分為一系列不重疊的time windows 依序執行QAOA最佳化。透過此設計，qubit 需求由與車輛數相關的平方級別降低為由路口狀態數以及window大小決定的常數級別，因而能在有限 qubit 資源下維持與個別車輛編碼方法相同的總等待時間解品質。
本論文在四向單車道路口情境下進行評估，並以古典貪婪與既有個別車輛編碼的方式作為比較對象。實驗結果顯示，在40輛車且符合即時計算需求的設定下，對比基準古典貪婪最多可降低14.2%的總等待時間。同時，相較於個別車輛編碼所需的 O(V^2) qubit複雜度，tsQAOA能將qubit需求固定在常數，且能夠與前述方法保持相同的解品質。顯示tsQAOA能夠在維持排程品質的同時，大幅降低量子計算資源需求，並具備應用於連續CAV車流協作的潛力。

The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising hybrid quantum-classical approach to solving combinatorial optimization problems. Vehicle coordination for Connected and Automated Vehicles (CAVs) at unsignalized intersections can also be formulated as a combinatorial optimization problem, aiming to minimize total vehicle waiting time while avoiding traffic conflicts. However, directly encoding individual vehicles or vehicle platoons causes the required number of qubits to grow rapidly with traffic volume, making the standard QAOA difficult to apply to real time intersection scheduling.
To overcome these limitations, we present Time-Segmented QAOA (tsQAOA), a time-segmented combinatorial optimization framework for CAV coordination at unsignalized intersections. Instead of encoding vehicles, tsQAOA encodes intersection traffic states as decision variables and formulates the scheduling problem as a Quadratic Unconstrained Binary Optimization (QUBO) model. Continuous traffic flow is divided into non-overlapping time windows, and QAOA is executed sequentially for each window. This design bounds the qubit requirement by the number of traffic states and the window size, rather than the number of vehicles.
Experimental results on a four way single-lane unsignalized intersection show that tsQAOA reduces total waiting time by up to 14.2% compared with a classical greedy baseline under a 40-vehicle real time setting. Compared with individual-vehicle encoding, tsQAOA reduces the qubit complexity from O(V^2) to O(1) with respect to the number of vehicles V. For a fixed intersection configuration, the same fixed-size quantum circuit can be repeatedly used to perform intersection scheduling under varying traffic conditions while maintaining comparable solution quality.

[1] Kostas Blekos, Dean Brand, Andrea Ceschini, Chiao-Hui Chou, Rui-Hao Li, Komal Pandya, and Alessandro Summer. A review on quantum approximate optimization algorithm and its variants. Physics Reports, 1068:1–66, 2024.
[2] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. Variational quantum algorithms. Nature Reviews Physics, 3(9):625–644, 2021.
[3] Kurt Dresner and Peter Stone. A multiagent approach to autonomous intersection management. Journal of Artificial Intelligence Research, 31(1):591–656, March 2008.
[4] Abyad Enan, M Sabbir Salek, Mashrur Chowdhury, Gurcan Comert, Sakib M Khan, and Reek Majumder. Optimal traffic flow in quantum annealing-supported virtual traffic lights. arXiv e-prints, pages arXiv–2412, 2024.
[5] Michael Evans, Marcial Machado, Rickey Johnson, Anna Vadella, Luis Escamilla, Beñat Froemming-Aldanondo, Tatiana Rastoskueva, Milan Jostes, Devson Butani, Ryan Kaddis, et al. A roadside unit for infrastructure assisted intersection control of autonomous vehicles. In 2025 IEEE International Conference on Electro Information Technology (eIT), pages 201–206. IEEE, 2025.
[6] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014.
[7] Muhammad Faris, Mario Zanon, and Paolo Falcone. An optimization-based dynamic reordering heuristic for coordination of vehicles in mixed traffic intersections. IEEE Transactions on Control Systems Technology, 33(4):1387–1402, 2025.
[8] FastestLaps. Tesla model y performance specifications and braking performance. https://fastestlaps.com/models/tesla-model-y-performance, 2024. Accessed: 2026-06-01.
[9] Fred Glover, Gary Kochenberger, and Yu Du. A tutorial on formulating and using qubo models. arXiv preprint arXiv:1811.11538, 2018.
[10] Robert Hult, Mario Zanon, Sébastien Gros, Henk Wymeersch, and Paolo Falcone. Optimisation-based coordination of connected, automated vehicles at intersections. Vehicle System Dynamics, 58(5):726–747, 2020.
[11] Hasham Hussain, Muhammad Bin Javaid, Faisal Shah Khan, Archismita Dalal, and Aeysha Khalique. Optimal control of traffic signals using quantum annealing: H. hussain et al. Quantum Information Processing, 19(9):312, 2020.
[12] IBM Quantum. Introduction to transpilation. https://quantum.cloud.ibm.com/docs/guides/transpile, 2026. Accessed: 2026-06-01.
[13] IBM Quantum. Parameter class. https://quantum.cloud.ibm.com/docs/api/qiskit/qiskit.circuit.Parameter, 2026. Accessed: 2026-06-01.
[14] Aws Khalil and Jaerock Kwon. Plm-net: Perception latency mitigation network for vision-based lateral control of autonomous vehicles. Sensors, 26(6):1798, 2026.
[15] Mohammad Khayatian, Mohammadreza Mehrabian, Edward Andert, Rachel Dedinsky, Sarthake Choudhary, Yingyan Lou, and Aviral Shirvastava. A survey on intersection management of connected autonomous vehicles. ACM Transactions on Cyber-Physical Systems, 4(4), August 2020.
[16] Matti Kutila, Kimmo Kauvo, Pasi Pyykönen, Xiaoyun Zhang, Victor Garrido-Martinez, Yinxiang Zheng, and Shen Xu. A C-V2X/5G field study for supporting automated driving. In 32nd IEEE Intelligent Vehicles Symposium (IV 2021), pages 315–320. IEEE, 2021.
[17] Joyoung Lee and Byungkyu Park. Development and evaluation of a cooperative vehicle intersection control algorithm under the connected vehicles environment. IEEE Transactions on Intelligent Transportation Systems, 13(1):81–90, 2012.
[18] Shaoyu Liu, Chaoyi Chen, Qing Xu, Chen Sun, Tao Cui, Zhaoyu Zhang, Mengchi Cai, Jianqiang Wang, and Keqiang Li. Coordination of connected and automated vehicles at unsignalized intersections using hybrid quantum annealing. In 2024 IEEE International Conference on Unmanned Systems (ICUS), pages 1460–1466. IEEE, 2024.
[19] Andrew Lucas. Ising formulations of many NP problems. Frontiers in Physics, 2, 2014.
[20] Naeimeh Mohseni, Peter L. McMahon, and Tim Byrnes. Ising machines as hardware solvers of combinatorial optimization problems. Nature Reviews Physics, 4(6):363–379, 2022.
[21] Gaurang Naik, Biplav Choudhury, and Jung-Min Jerry Park. IEEE 802.11bd & 5G NR V2X: Evolution of radio access technologies for V2X communications. IEEE Access, 7:70169–70184, 2019.
[22] S. John Older and Brian R. Spicer. Traffic conflicts—a development in accident research. Human Factors, 18(4):335–350, 1976.
[23] Bo Qian, Haibo Zhou, Feng Lyu, Jinglin Li, Ting Ma, and Fen Hou. Toward collision-free and efficient coordination for automated vehicles at unsignalized intersection. IEEE Internet of Things Journal, 6(6):10408–10420, December 2019.
[24] Shree Hari Sureshbabu, Dylan Herman, Ruslan Shaydulin, Joao Basso, Shouvanik Chakrabarti, Yue Sun, and Marco Pistoia. Parameter setting in quantum approximate optimization of weighted problems. Quantum, 8:1231, 2024.
[25] Jules Tilly, Hongxiang Chen, Shuxiang Cao, Dario Picozzi, Kanav Setia, Ying Li, Edward Grant, Leonard Wossnig, Ivan Rungger, George H. Booth, et al. The variational quantum eigensolver: A review of methods and best practices. Physics Reports, 986:1–128, 2022.
[26] Chun Ting Wu, Yung-Jen Hsu, Chia-Heng Tu, and Shaohua Wang. Traffic signal preemption and prioritization for high-density road networks. In Proceedings of the 39th ACM/SIGAPP Symposium on Applied Computing, pages 410–419, 2024.
[27] Yunting Xu, Haibo Zhou, Bo Qian, Hanlin Wu, Ting Ma, and Xuemin Sherman Shen. V2X enabled non-signalized intersections management: A function approximation approach. In GLOBECOM 2020 - 2020 IEEE Global Communications Conference, pages 1–5, 2020.
[28] Zijia Zhong, Mark Nejad, and Earl E. Lee. Autonomous and semiautonomous intersection management: A survey. IEEE Intelligent Transportation Systems Magazine, 13(2):53–70, 2021.
[29] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Physical Review X, 10(2):021067, 2020.