Solving the traveling salesman problem on 2 (N-1)! qubits with a variational quantum Kolmogorov--Arnold network: exact-gradient CVaR training and generalization over time-dependent graphs

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "Solving the traveling salesman problem on 2 (N-1)! qubits with a variational quantum Kolmogorov--Arnold network".

Mira: The gist The Variational Quantum Kolmogorov-Arnold Network (VQKAN) provides a novel framework to solve the Traveling Salesman Problem (TSP) by emulating transformer matrices with variational quantum circuits,

Kai: First, who's behind it and why it matters.

Title and authors: Kai: Moving on to the summary of this work, we’re looking at how they frame this entire VQKAN method for solving TSP. They emphasize that it’s a variational quantum version of KAN, which is a novel multi-layer neuromorphic network.

Mira: They explain that VQKAN emulates transformer matrices by using the ansatz of VQA and the state vector by quantum states. This links classical neural network concepts directly to the quantum circuit design.

Lev: So they're using existing, proven architectures from machine learning—the transformer structure—and trying to translate that into a quantum circuit setup where expectation values map to those transformer functions.

Kai: They detail the initial state preparation, ini(one times m), involving rotation gates R yj(theta) for each qubit j and input m <ref:2509.22752#pg2>.

Mira: They show how the final state is built by applying a sequence of layers, Nl(one times m) = sum n one n (product n n) ini(one times m) <ref:2509.22752#pg2>.

Lev: And they define the loss function l m using expectation values of Z operators and that specific taboo term f tab(one times m) <ref:2509.22752#pg2,expectation values of Z operators>.

Kai: That taboo term is defined as f tab(one times m) = sum n=zero Nl-one sum k not equal to n Q Nq-one j (product j (one - nZ jn)(one - kZ jk)) <ref:2509.22752#pg2>.

Mira: So they are using this loss function, which includes the taboo term, to guide the variational optimization process on the quantum hardware.

Lev: The whole point of this setup is that it allows for an exact-gradient training method for these quantum circuits, which is usually something you only get in classical optimization.

Kai: Which brings us back to the comparison with VQE; they show that VQKAN can solve TSP with the number of qubits same as the number of sites and its calculation time is far shorter than the VQE approach.

Mira: It’s an important distinction because it suggests a hardware efficiency gain when solving these combinatorial optimization problems on quantum hardware.

Lev: If we were building this on real hardware, that reduction in required qubit count really translates into less noise accumulation and potentially faster execution times for the training loops.

The paper's summary: Kai: Now let’s talk about the improvements they suggest in this work. They focus on how this VQKAN approach handles different types of graph structures.

Mira: They tested it on four-point graphs and six-point graphs, showing optimization results for both structures. For the square shape, they noted that energy and path derived for t=zero through t=zero point five coincided exactly <ref:2509.22752#pg2>.

Lev: That stability over time in the square graph is a good sign; it means the method isn't completely lost when we introduce temporal variations in the graph structure.

Kai: They also showed that for finding the root by sum, their approach converges when only two terms are considered, while for finding the root by product, it converges even though only two terms are involved.

Mira: This is interesting because it shows different convergence behaviors depending on whether they use a sum or a product method to find the solution.

Lev: That kind of dependency on the convergence method suggests that we need to be careful about which optimization path we choose when implementing this on hardware.

Kai: They also presented results for six graphs with random path lengths, and they found that "Energy has the room to lower more for all attempts."

Mira: That phrasing implies that even with many tries, the energy landscape still has significant room to be explored further across different graph configurations.

Lev: It means we aren't getting stuck in a local minimum too early when dealing with these varied path lengths and topologies.

The paper's improvements: Kai: So wrapping up this discussion on "Solving the traveling salesman problem on two(N-one) <ref:2509.22752#pg2>! qubits with a variational quantum Kolmogorov--Arnold network: exact-gradient CVaR training and generalization over time-dependent graphs," the main implication is that VQKAN provides a way to solve TSP using fewer qubits than some other methods.

Mira: They’ve shown it can handle time-dependent graphs, allowing for partial derivation of shortest paths at each time step. This is a capability they highlight as important for dynamic routing problems.

Lev: From an engineering standpoint, the fact that it can solve TSP with the number of qubits equal to the number of sites and has a shorter calculation time than VQE is where we see real potential for NISQ applications.

Kai: The authors also pointed out their limitation: they say that although accuracy is low, the successful derivation of shortest paths on not all graphs establishes a milestone in applying quantum computers to real-world problems.

Mira: They explicitly state that they suggest establishing a method to improve the accuracy of solving the TSP by VQKAN is needed.

Lev: For me, it’s clear that this work shows a promising direction for using quantum networks not just for theoretical puzzles, but for tackling complex optimization problems with varying constraints over time.

Kai: We’ve looked at this paper now. It's a lot of work to build and test these kinds of things, but the idea is that this framework could be useful down the line if we can get better accuracy.

Mira: We’ll keep an eye on how they suggest improving the accuracy next.

Lev: Yeah, for us, it’s about whether this concept can translate from a successful simulation to something that actually runs reliably on physical quantum hardware with low error rates.

Conclusion: Kai: So we’ve been looking at "Solving the traveling salesman problem on two(N-one)! qubits with a variational quantum Kolmogorov--Arnold network: exact-gradient CVaR training and generalization over time-dependent graphs." Essentially, they’ve used this VQKAN to tackle the Traveling Salesman Problem.

Mira: Right, so they framed it like a variational quantum version of KAN, which lets them use transformer matrices as the circuit structure. The big takeaway is that they got an exact-gradient training method working for these quantum circuits.

Lev: From my side, what’s interesting is that this approach claims you can solve TSP with the number of qubits equal to the number of sites. That’s a real hardware win if it holds up under real noise.

Kai: They showed results on four-point and six-point graphs, where they found that the energy and path derived for time t=zero through t=zero point five actually matched up perfectly on the square graph.

Mira: That stability over time in those small examples is important because it suggests the VQKAN structure can handle some of that temporal variation without completely breaking down.

Lev: But we need to think about running this on actual hardware, and that’s where things get tricky with overhead, right?

Kai: They also showed they can derive shortest paths for multiple cases, even when the path lengths change over time in those six-site graphs.

Mira: That means they aren't just solving a single static problem; they can handle situations where the constraints are shifting partially over time.

Lev: If we were to run this on a real device, that partial derivation is key because you’d be constantly retraining or updating based on the new time-dependent data.

Kai: The authors noted that although accuracy is low, getting those shortest paths for different graphs at once is still a significant step in applying quantum computers to these kinds of combinatorial problems.

Mira: They did flag their limitation clearly: they say that they need a method to improve the accuracy of solving the TSP by VQKAN.

Lev: That’s fair, because low accuracy means real-world logistics applications wouldn't trust those solutions yet.

Kai: So, to wrap up on "Solving the traveling salesman problem on two(N-one)! qubits with a variational quantum Kolmogorov--Arnold network: exact-gradient CVaR training and generalization over time-dependent graphs," it’s a solid proof of concept for using VQKAN in this domain.

Mira: It proves that you can map complex graph optimization structures onto quantum circuits effectively.

Lev: And it shows the potential for reducing the qubit count compared to other approaches, which is what we need to get things running on current hardware platforms.