Come risolvere i problemi QUBO in Q #?
Versione breve:
Sto cercando di risolvere un problema di venditore ambulante molto simile all'esempio di Babbo Natale in viaggio qui: http://quantumalgorithmzoo.org/traveling_santa/, che è anche incluso negli esempi degli esempi Microsoft Quantum qui: https://github.com/microsoft/Quantum/tree/main/samples/simulation. In quell'esempio, assumono alcuni parametri beta e gamma che danno probabilità favorevoli di trovare il percorso ottimale. Il problema è: come si ottengono questi parametri? Ma una domanda più generale che ho è: come risolveresti un problema QUBO (con un hamiltoniano della forma$H = -\sum_i h_i \sigma_i^z -\sum_{i,j} J_{i,j} \sigma_i^z \sigma_j^z$) in qsharp?
Quello che ho provato:
Basandomi sul campione QAOA, la prima cosa che ho fatto è stato imbrogliare: ho usato un ottimizzatore classico per risolvere i valori ottimali per beta e gamma, riducendo al minimo l'energia. E ho calcolato l'energia scaricando il registro quantistico in un file. Con le probabilità per ogni stato, il valore stimato per l'energia è semplicemente$\sum_{states} p_{state} E_{state}$.
Ovviamente, su Azure Quantum / su hardware quantistico reale non hai accesso alle probabilità. Quindi ho cercato di trovare modi per ottenere stime precise dell'energia. È qui che sto lottando con gli esempi e la documentazione. Ho un registro di qubit e un'equazione hamiltoniana che vorrei inserire, ma la funzione stima energia in Q # richiede
JordanWignerEncodingDatao unstatePrepUnitaryeqpeUnitary. In entrambi i casi non capisco davvero come li costruirò e cosa fanno / perché ne ho bisogno. Gli sforzi per stimare l'energia dalla stima di fase fallirono, ma ciò potrebbe essere dovuto alla mia mancanza di comprensione. Se questo è davvero un buon modo per risolvere i problemi di ottimizzazione, ci sono buone risorse per capirlo meglio?L'ultima cosa che ho provato è stata il principio di cambiare lentamente l'Hamiltoniano da uno che ha uno stato di base facile da preparare, all'Hamiltoniano corrispondente al problema di ottimizzazione che vuoi risolvere. L'esempio e la spiegazione sono qui:https://github.com/microsoft/Quantum/blob/main/samples/simulation/ising/adiabatic/AdiabaticIsing.qs#L14. Sfortunatamente, mi sembra di rimanere bloccato in diversi minimi locali a seconda della velocità, e nessuno di loro si avvicina effettivamente alla soluzione reale. Quindi ho trovato anche questo metodo non molto affidabile.
Capisco che la domanda sia molto simile a questa , ma anche dopo aver letto la risposta lì, non sono ancora sicuro che quello che sto provando abbia senso e come farlo funzionare in Q #. Quindi spero in una risposta più concreta, o una letteratura adatta agli sviluppatori che hanno seguito un corso di fisica quantistica molti anni fa.
Risposte
Per rispondere alla tua prima domanda, QAOA è un'applicazione di un algoritmo ibrido classico-quantistico, quindi l'utilizzo di un ottimizzatore classico è una soluzione perfettamente valida qui. Suggerirei di utilizzare, ad esempio, scipy.optimizequalsiasi altro dei tuoi strumenti di ottimizzazione preferiti.
La tua seconda domanda riguarda la misurazione dell'energia dello stato quantistico. In effetti, Q # non consente l'ispezione dello stato quantistico, perché come hai notato questo non è possibile nemmeno sull'hardware fisico.
Tuttavia, ci sono alcuni modi per recuperare queste informazioni.
In un esperimento su hardware reale, quello che faresti è semplicemente misurare tutti i qubit più e più volte, diciamo Nvolte, il che ti dà un elenco di Nstringhe di bit. Se Nè grande, otterrai una distribuzione di probabilità affidabile di tutti gli stati dei qubit. Nella simulazione questo può essere fatto misurando tutti i qubit nel registro dei qubit in un ciclo for e contando le occorrenze di ogni possibile iterazione. Dovrebbe essere semplice da implementare, ma suggerirò di seguito una soluzione che utilizzi la funzionalità di libreria esistente che potresti trovare utile.
Invece di misurare i risultati di ogni qubit, implementeremo una pratica operazione che ci consente di misurare la probabilità di ogni stato valido e la probabilità di ottenere uno stato non valido.
Prima di tutto, come spiegato nel post del blog, ci sono le probabilità di ottenere uno dei 3 stati validi e c'è la probabilità di ottenere uno stato non valido:
// 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];
Terremo traccia della probabilità di ottenere uno stato non valido man mano che i risultati arrivano sottraendo questi valori da 1.0.
mutable otherProb = 1.0; // Probability of any invalid state
Quindi quello che faremo è eseguire un ciclo su tutti gli stati validi, quindi misurare la probabilità di ciascuno e restituirli e la probabilità di ottenere uno stato non valido in un array 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'energia, o il costo che vogliamo minimizzare, può quindi essere calcolato moltiplicando le probabilità per il costo di ogni stato.
(Ovviamente per questo esempio questo è un po 'sciocco, poiché possiamo semplicemente calcolare il costo di ciascuno degli stati consentiti sopra e quindi scegliere il valore più basso. Tuttavia, in altre applicazioni quantistiche lo spazio degli stati validi potrebbe ad esempio essere molto più grande, e in quel caso dovremmo solo valutare la funzione di costo per gli stati che hanno una probabilità diversa da zero.)
Quindi, come implementare MeasureProbabilityForState?
Possiamo usare l'operazione EstimateFrequencyper questo. Questa operazione misura la probabilità di ottenere un Zerorisultato per determinate operazioni di preparazione e misurazione dello stato. Vedi i documenti qui:https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.characterization.estimatefrequency.
L'implementazione può essere simile a questa:
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
);
}
dove dobbiamo controllare se il registro è nello stato desiderato e restituire Zerose è:
operation MeasureRegisterIsInState(register : Qubit[], state : Result[]) : Result {
let result = MultiM(register);
if (All<(Result, Result)>(EqualR, Zipped(result, state))) {
return Zero;
} else {
return One;
}
}
e
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)
}
}
Questo è solo un modo di utilizzare EstimateFrequencyper risolvere questo problema; Spero che questo esempio ti aiuti a capire il modo migliore che funziona per la tua applicazione quantistica.