Speaker
Description
In our work, we formulate a novel variational quantum approach to solve the travelling salesman problem (TSP), and we demonstrate it through a silicon photonic circuit (Si-PIC). The TSP [1] is a well-known combinatorial classical problem which is NP-hard. The aim consists of finding the shortest route among N cities, passing through each city once and ending at the initial city. Today, there is no classical algorithm able to solve this problem without an exponential growth of resources and time instances. For this reason, researchers are investigating the possibility of achieving a better behaviour with hybrid-quantum- classical architectures and associated variational quantum algorithms (VQAs) [2, 3]. The most famous formulation is given by the quadratic unconstrained binary optimization with Ising-like Hamiltonians, implemented on superconducting platforms [4].
Our variational approach outmatches the known methods in terms of the number of qubits and two-qubit gates. In particular, the first feature scales logarithmically and the latter quadratically with respect to N. The procedure is based on the preparation of trial states in the form of two maximally entangled quantum registers, one for the departing cities and one for the arriving ones. Then, the cost function of the problem is calculated by utilizing the correlation matrix between the two quantum registers and the values of distances among the different city pairs. As in any VQA, the classical hardware updates the preparation set- ting of the trial states through a classical minimization routine for the cost function until the convergence to an extremal value is reached.
On the same Si-PIC used to solve a quantum chemistry problem and factorization tasks [5], we implemented the proposed VQA for the generic TSP with four cities. The circuit allows for the generation of entangled photon pairs, whose spatial modes encode the two quantum registers for the desired TSP. The solution can be read directly from the twin-photon cor- relation matrix after the classical optimization convergence. Contrary to other variational approaches, the solution is not written in the state itself but in one of its observables: thus, no state tomography is needed.
Our method shows how future entanglement-based specific-purpose quantum hardware could reach quantum utility even in the noisy intermediate quantum era [6].
References
[1] Beardwood,J.,et al.”Theshortestpaththroughmanypoints.”Mathematical proceedings of the Cambridge philosophical society. (1959).
[2] Peruzzo, A.,et al. ”A variational eigenvalue solver on a photonic quantum processor."Nature Comm.5.1(2014).
[3] Cerezo,M.,etal.”Variational quantum algorithms.” Nature Reviews Physics 3.9 (2021).
[4] McGeoch, C. C., et al. “Experimental evaluation of an adiabiatic quantum system for combinatorial optimization.” Proceedings of the ACM International Conference on Computing Frontiers (2013).
[5] Baldazzi, A., et al. ”Four-qubit variational algorithms in silicon photonics with integrated entangled photon sources.”npj Quantum Information 11.1 (2025): 107..
[6] Moody,G.,etal.”2022 Roadmap on integrated quantum photonics.” Journal of Physics: Photonics 4.1 (2022).