Resource-efficient variational quantum solver for the travelling salesman problem and its silicon photonics implementation

• URL: http://arxiv.org/abs/2511.02696v1
• Date: Tue, 04 Nov 2025 16:18:48 GMT
• Title: Resource-efficient variational quantum solver for the travelling salesman problem and its silicon photonics implementation
• Authors: Alessio Baldazzi, Stefano Azzini, Lorenzo Pavesi,
• Abstract summary: We propose a novel variational quantum algorithm to solve the travelling salesman problem.<n>For $N$ cities, this encoding requires $2 lceillog Nrceil$ qubits.<n>As a proof-of-concept, we implement this algorithm for generic problems with four cities on a reconfigurable room-temperature silicon photonic circuit.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The travelling salesman problem is a well-known example of computationally-hard combinatorial problem for classical machines. Here, we propose a novel variational quantum algorithm to solve it. The method is based on the preparation of two maximally entangled quantum registers whose correlations are assigned to different paths between pairs of cities. For $N$ cities, this encoding requires $2 \lceil\log_2 N\rceil$ qubits and the solution to the problem is directly found in the correlation matrix of the two registers composing the overall trial state. As a proof-of-concept experiment, we implement this algorithm for generic problems with four cities on a reconfigurable room-temperature silicon photonic circuit with integrated photon-pair sources, used to initialize maximally entangled path-encoded single-photon states.

Related papers

• Data Complexity Measures for Quantum Circuits Architecture Recommendation [55.74527632797241]
  Quantum Parametric Circuits are constructed as an alternative to reduce the size of quantum circuits.<n> determining the optimal circuit for a given problem remains an open question.<n>In this work, a quantum circuit recommendation architecture for classification problems is proposed using database complexity measures.
  arXiv  Detail & Related papers  (2025-02-21T01:17:24Z)
• Four-Qubit Variational Algorithms in Silicon Photonics with Integrated Entangled Photon Sources [0.0]
  We execute two variational quantum algorithms on a silicon photonic integrated circuit at room temperature.<n>This marks a first demonstration of variational quantum algorithms on a photonic quantum simulator with integrated photon pair sources.
  arXiv  Detail & Related papers  (2025-01-02T15:29:47Z)
• Solving The Travelling Salesman Problem Using A Single Qubit [0.0]
  The travelling salesman problem (TSP) is a popular NP-hard-combinatorial optimization problem.<n>We present an algorithm that solves an arbitrary TSP using a single qubit by invoking the principle of quantum parallelism.<n>The underlying framework of our algorithm is a quantum version of the classical Brachistochrone approach.
  arXiv  Detail & Related papers  (2024-07-24T12:06:37Z)
• Recursive Quantum Relaxation for Combinatorial Optimization Problems [3.3053321430025258]
  We show that some existing quantum optimization methods can be unified into a solver to find the binary solution.<n>Experiments on standard benchmark graphs with several hundred nodes in the MAX-CUT problem, conducted in a fully classical manner.
  arXiv  Detail & Related papers  (2024-03-04T13:48:21Z)
• A Quantum Approach to solve N-Queens Problem [0.7373617024876725]
  We have introduced two innovative quantum algorithms to solve N-Queens problem. N-Queens problem involves the arrangement of $N$ queens on a $N times N$ chessboard such that they are not under attack from each other on the same row, column and diagonal. The algorithms utilize Controlled W-states and dynamic circuits, to efficiently address this NP-Complete computational problem.
  arXiv  Detail & Related papers  (2023-12-26T19:42:05Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  We propose a variational quantum algorithm for performing quantum dynamics in first quantization. Our simulations exhibit the previously observed numerical instabilities of variational time propagation approaches.
  arXiv  Detail & Related papers  (2022-03-04T19:00:45Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• Quantum Annealing Approaches to the Phase-Unwrapping Problem in Synthetic-Aperture Radar Imaging [0.32622301272834525]
  We explore the use of quantum annealing solvers for the problem of phase unwrapping of synthetic aperture radar (SAR) images. Our approach involves formulating the problem as a quadratic unconstrained binary optimization (QUBO) problem, which can be solved using a quantum annealer. We test our approach with a variety of software-based QUBO solvers and on a variety of images, both synthetic and real.
  arXiv  Detail & Related papers  (2020-10-01T07:04:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.