Traveling Salesman Problem Upscaling Issue

[LeaBaumann]

Hi, I was trying to run the Traveling Salesman problem from your tutorial for more than 4 cities.

I have encountered a problem when using the version with the Quantum Phase Estimation algorithm, more precisely with this method:

@as_hamiltonian
def trip_distance(i, j, iter = 1):
    return distance_matrix[i, j]*2*np.pi*iter

The indices that are entered here are the QuantumFloats from the itinerary. If I have a 5-city problem, the i, j should classically only be able to take the values 0, 1, 2, 3, 4.

I found out that the as_hamiltonian decorator processes the method for all possible values for i and j, not only the ones that were entered as parameters. For example, when I enter a QuantumFloat of size 3 (so that it could in theory contain values from 0 to 7), the as_hamiltonian tries to evaluate the method also for the values 5, 6, 7.

This makes sense insofar as the quantum float can also have the value 7 with a non-vanishing probability due to its quantum character. My main problem now is that a problem with 5 cities scales in the same way as with 8 cities, which leads to a significantly increased runtime.

Here is a smaller example (with 3 cities) which shows the issue I was describing:

import numpy as np
from qrisp import *

matrix = np.array([[0.25,   0.125,  0.5],
                    [0.25,  0,      0.625],
                    [0.5,   0.375,  0.75]])

test_qarray = QuantumArray(qtype = QuantumFloat(2))
test_qarray[:] = [0,1,1]
@as_hamiltonian
def as_phase(i, j):
    return matrix[i, j] * 2 * np.pi

for i in range(len(test_qarray)-1):
    as_phase(test_qarray[i], test_qarray[i + 1])

print(np.max(matrix, axis=0))

I can prevent the method from trying to access uncomputable values (which prevents the error), but the problem still scales as with 4 cities instead of 3 in this example.

Do you have any idea what I can do to make the algorithm more effective and only consider the exact problem size?

[positr0nium]

Hi, what you are experiencing is something that we call the compilation bottleneck, which is in most cases happening due to Python being to slow. This is a problem that most likely any Python quantum framework will face. We are actively working on a restructuring of the core elements of Qrisp to outsorce all the "hard work" to established classical compilation infrastructure (i.e. LLVM). You can monitor our progress here: https://github.com/eclipse-qrisp/Qrisp/tree/catalyst_integration but it will most likely still take some time until we are at a stage where it can be used.