Short version:
I'm trying to solve a traveling salesman problem very similar to the traveling Santa example here: http://quantumalgorithmzoo.org/traveling_santa/, which is also included in the samples of the Microsoft Quantum samples here: https://github.com/microsoft/Quantum/tree/main/samples/simulation. In that example, they assume some parameters beta and gamma that yield favorable odds of finding the optimal route. The problem is: how do you get these parameters? But a more general question that I have is: How would you solve a QUBO problem (with a Hamiltonian of the form $H = -\sum_i h_i \sigma_i^z -\sum_{i,j} J_{i,j} \sigma_i^z \sigma_j^z$) in qsharp?
What I've tried:
Building upon the QAOA sample, the first thing I did was cheat: I used a classical optimizer to solve for optimal values for beta and gamma, minimizing the energy. And I calculated the energy by dumping the quantum registry to a file. With the probabilities for each state, the estimated value for the energy is simply $\sum_{states} p_{state} E_{state}$.
Of course, on Azure Quantum / on real quantum hardware you don't have access to the probabilities. So I tried to find ways to get precise estimates of the energy. This is where I'm struggling given the samples and documentation. I have a registry of qubits and a Hamiltonian equation that I would like to plug in, but the EstimateEnergy function in Q# either takes
JordanWignerEncodingData
or astatePrepUnitary
andqpeUnitary
. In both cases I don't really understand how I would construct them and what they do/why I need them. Efforts to estimate the energy from the phase estimation failed, but that might be due to my lack of understanding. If this is indeed a good way to solve optimization problems, are there any good resources to understand this better?The final thing I tried was the principal of slowly changing the Hamiltonian from one that has an easy to prepare groundstate, to the Hamiltonian corresponding to the optimization problem you want to solve. The example and explanation are here: https://github.com/microsoft/Quantum/blob/main/samples/simulation/ising/adiabatic/AdiabaticIsing.qs#L14. Unfortunately, I seem to get stuck in different local minima depending on the rate, and none of them actually come close to the real solution. So I found this method to be not very reliable either.
I understand the question is very similar to this one, but even after reading the answer there, I'm still not sure if what I'm trying makes sense, and how to make it work in Q#. So I am hoping for more concrete answer, or literature suited for developers who followed a quantum physics course many many years ago.