Comment résoudre les problèmes QUBO en Q #?
Version courte:
J'essaie de résoudre un problème de voyageur de commerce très similaire à l'exemple du Père Noël en voyage ici: http://quantumalgorithmzoo.org/traveling_santa/, qui est également inclus dans les exemples des exemples Microsoft Quantum ici: https://github.com/microsoft/Quantum/tree/main/samples/simulation. Dans cet exemple, ils supposent certains paramètres bêta et gamma qui donnent des chances favorables de trouver la route optimale. Le problème est: comment obtenir ces paramètres? Mais une question plus générale que je me pose est: comment résoudriez-vous un problème QUBO (avec un hamiltonien de la forme$H = -\sum_i h_i \sigma_i^z -\sum_{i,j} J_{i,j} \sigma_i^z \sigma_j^z$) dans qsharp?
Ce que j'ai essayé:
En me basant sur l'exemple QAOA, la première chose que j'ai faite a été de tricher: j'ai utilisé un optimiseur classique pour trouver des valeurs optimales pour bêta et gamma, minimisant ainsi l'énergie. Et j'ai calculé l'énergie en vidant le registre quantique dans un fichier. Avec les probabilités pour chaque état, la valeur estimée de l'énergie est simplement$\sum_{states} p_{state} E_{state}$.
Bien sûr, sur Azure Quantum / sur du matériel quantique réel, vous n'avez pas accès aux probabilités. J'ai donc essayé de trouver des moyens d'obtenir des estimations précises de l'énergie. C'est là que j'ai du mal compte tenu des échantillons et de la documentation. J'ai un registre de qubits et une équation hamiltonienne que je voudrais brancher, mais la fonction EstimateEnergy dans Q # prend
JordanWignerEncodingDataou astatePrepUnitaryetqpeUnitary. Dans les deux cas, je ne comprends pas vraiment comment je les construirais et ce qu'ils font / pourquoi j'en ai besoin. Les efforts pour estimer l'énergie à partir de l'estimation de phase ont échoué, mais cela pourrait être dû à mon manque de compréhension. Si c'est effectivement un bon moyen de résoudre les problèmes d'optimisation, existe-t-il de bonnes ressources pour mieux comprendre cela?La dernière chose que j'ai essayée était le principe de changer lentement l'hamiltonien de celui qui a un état de base facile à préparer, à l'hamiltonien correspondant au problème d'optimisation que vous voulez résoudre. L'exemple et l'explication sont ici:https://github.com/microsoft/Quantum/blob/main/samples/simulation/ising/adiabatic/AdiabaticIsing.qs#L14. Malheureusement, je semble rester coincé dans différents minima locaux en fonction du taux, et aucun d'entre eux ne se rapproche réellement de la vraie solution. J'ai donc trouvé cette méthode peu fiable non plus.
Je comprends que la question est très similaire à celle-ci , mais même après avoir lu la réponse, je ne sais toujours pas si ce que j'essaie a du sens et comment le faire fonctionner en Q #. J'espère donc une réponse plus concrète, ou une littérature adaptée aux développeurs qui ont suivi un cours de physique quantique il y a de nombreuses années.
Réponses
Pour répondre à votre première question, QAOA est une application d'un algorithme hybride classique-quantique, donc utiliser un optimiseur classique est une solution parfaitement valable ici. Je suggérerais d'utiliser par exemple scipy.optimizen'importe quel autre de vos outils d'optimisation préférés.
Votre deuxième question concerne la mesure de l'énergie de l'état quantique. En effet, Q # ne permet pas l'inspection de l'état quantique, car comme vous l'avez noté cela n'est pas possible non plus sur du matériel physique.
Cependant, il existe plusieurs façons de récupérer ces informations.
Dans une expérience sur du matériel réel, ce que vous feriez est simplement de mesurer tous les qubits encore et encore, disons les Ntemps, ce qui vous donne une liste de Nchaînes de bits. Si Nest grand, cela vous donnera une distribution de probabilité fiable de tous les états de qubit. En simulation, cela peut être fait en mesurant tous les qubits dans le registre des qubits dans une boucle for, et en comptant les occurrences de chaque itération possible. Cela devrait être simple à mettre en œuvre, mais je suggérerai ci-dessous une solution qui utilise les fonctionnalités de bibliothèque existantes que vous pourriez trouver utiles.
Au lieu de mesurer les résultats de chaque qubit, nous allons implémenter une opération pratique qui nous permet de mesurer la probabilité de chaque état valide et la probabilité d'obtenir un état invalide.
Tout d'abord, comme expliqué dans l'article du blog, il y a les probabilités d'obtenir l'un des 3 états valides, et il y a la probabilité d'obtenir un état invalide:
// Allowed states
let state1 = [One, One, One, One, Zero, Zero];
let state2 = [Zero, One, Zero, One, One, One];
let state3 = [One, Zero, One, Zero, One, One];
let states = [state1, state2, state3];
mutable result = new Double[Length(states) + 1];
Nous garderons une trace de la probabilité d'obtenir un état invalide au fur et à mesure que les résultats arrivent en soustrayant ces valeurs de 1.0.
mutable otherProb = 1.0; // Probability of any invalid state
Nous allons donc faire une boucle sur tous les états valides, puis mesurer la probabilité de chacun, et les renvoyer ainsi que la probabilité d'obtenir un état invalide dans un tableau result.
for ((index, state) in Enumerated(states)) {
let prob = MeasureProbabilityForState(state, numSegments, weights, couplings, timeX, timeZ, numMeasurements);
set result w/= index <- prob;
set otherProb -= prob;
}
set result w/= Length(states) <- otherProb;
L'énergie, ou le coût que nous voulons minimiser, peut alors être calculé en multipliant les probabilités par le coût de chaque état.
(Évidemment, pour cet exemple, c'est un peu idiot, car nous pouvons simplement calculer le coût de chacun des états autorisés ci-dessus, puis choisir la valeur la plus basse. Cependant, dans d'autres applications quantiques, l'espace des états valides pourrait par exemple être beaucoup plus grand, et dans ce cas, nous n'aurions besoin d'évaluer la fonction de coût que pour les états qui ont une probabilité non nulle.)
Alors, comment mettre en œuvre MeasureProbabilityForState?
Nous pouvons utiliser l'opération EstimateFrequencypour cela. Cette opération mesure la probabilité d'obtenir un Zerorésultat pour des opérations de préparation et de mesure d'état donné. Voir la documentation ici:https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.characterization.estimatefrequency.
L'implémentation peut ressembler à ceci:
operation MeasureProbabilityForState(
state : Result[],
numSegments: Int,
weights : Double[],
couplings : Double[],
timeX : Double[],
timeZ : Double[],
numMeasurements: Int
) : Double {
return EstimateFrequency(
ApplyQAOA(_, numSegments, weights, couplings, timeX, timeZ),
MeasureRegisterIsInState(_, state),
numSegments,
numMeasurements
);
}
où il faut vérifier si le registre est dans l'état souhaité et retourner Zeros'il est:
operation MeasureRegisterIsInState(register : Qubit[], state : Result[]) : Result {
let result = MultiM(register);
if (All<(Result, Result)>(EqualR, Zipped(result, state))) {
return Zero;
} else {
return One;
}
}
et
operation ApplyQAOA(
x: Qubit[],
numSegments: Int,
weights : Double[],
couplings : Double[],
timeX : Double[],
timeZ : Double[]
) : Unit {
ApplyToEach(H, x); // prepare the uniform distribution
for ((tz, tx) in Zipped(timeZ, timeX))
{
ApplyInstanceHamiltonian(numSegments, tz, weights, couplings, x); // do Exp(-i H_C tz)
ApplyDriverHamiltonian(tx, x); // do Exp(-i H_0 tx)
}
}
Ce n'est qu'une manière d'utiliser EstimateFrequencypour résoudre ce problème; J'espère que cet exemple vous aidera à trouver la meilleure façon de fonctionner pour votre application quantique.