Como resolver problemas QUBO em Q #?
Versão curta:
Estou tentando resolver um problema de caixeiro viajante muito semelhante ao exemplo do Papai Noel viajante aqui: http://quantumalgorithmzoo.org/traveling_santa/, que também está incluído nas amostras das amostras do Microsoft Quantum aqui: https://github.com/microsoft/Quantum/tree/main/samples/simulation. Nesse exemplo, eles assumem alguns parâmetros beta e gama que geram chances favoráveis de encontrar a rota ideal. O problema é: como você obtém esses parâmetros? Mas uma pergunta mais geral que eu tenho é: como você resolveria um problema QUBO (com um hamiltoniano da forma$H = -\sum_i h_i \sigma_i^z -\sum_{i,j} J_{i,j} \sigma_i^z \sigma_j^z$) no qsharp?
O que eu tentei:
Com base no exemplo QAOA, a primeira coisa que fiz foi trapacear: usei um otimizador clássico para resolver os valores ideais para beta e gama, minimizando a energia. E calculei a energia despejando o registro quântico em um arquivo. Com as probabilidades para cada estado, o valor estimado para a energia é simplesmente$\sum_{states} p_{state} E_{state}$.
Claro, no Azure Quantum / em hardware quântico real você não tem acesso às probabilidades. Portanto, tentei encontrar maneiras de obter estimativas precisas da energia. É aqui que estou tendo dificuldades com as amostras e a documentação. Eu tenho um registro de qubits e uma equação hamiltoniana que gostaria de inserir, mas a função EstimateEnergy em Q # leva
JordanWignerEncodingDataou astatePrepUnitaryeqpeUnitary. Em ambos os casos, não entendo realmente como os construiria e o que fazem / por que preciso deles. Os esforços para estimar a energia da estimativa de fase falharam, mas isso pode ser devido à minha falta de compreensão. Se esta for realmente uma boa maneira de resolver problemas de otimização, existem bons recursos para entendê-la melhor?A última coisa que tentei foi alterar lentamente o hamiltoniano de um que tenha um estado fundamental fácil de preparar para o hamiltoniano correspondente ao problema de otimização que você deseja resolver. O exemplo e a explicação estão aqui:https://github.com/microsoft/Quantum/blob/main/samples/simulation/ising/adiabatic/AdiabaticIsing.qs#L14. Infelizmente, pareço ficar preso em diferentes mínimos locais dependendo da taxa, e nenhum deles chega perto da solução real. Portanto, descobri que esse método também não era muito confiável.
Eu entendo que a pergunta é muito semelhante a esta , mas mesmo depois de ler a resposta lá, ainda não tenho certeza se o que estou tentando fazer faz sentido e como fazer funcionar no Q #. Portanto, espero uma resposta mais concreta, ou literatura adequada para desenvolvedores que seguiram um curso de física quântica há muitos anos.
Respostas
Para responder à sua primeira pergunta, QAOA é uma aplicação de um algoritmo híbrido clássico-quântico, portanto, usar um otimizador clássico é uma solução perfeitamente válida aqui. Eu sugeriria usar, por exemplo, scipy.optimizequalquer outra de suas ferramentas de otimização favoritas.
Sua segunda pergunta é com relação à medição da energia do estado quântico. Na verdade, Q # não permite a inspeção do estado quântico, porque, como você observou, isso também não é possível no hardware físico.
No entanto, existem algumas maneiras de recuperar essas informações.
Em um experimento em hardware real, o que você faria é simplesmente medir todos os qubits repetidamente, digamos, Nvezes, o que fornece uma lista de Nbitstrings. Se Nfor grande, isso dará a você uma distribuição de probabilidade confiável de todos os estados qubit. Na simulação, isso pode ser feito medindo todos os qubits no registrador de qubit em um loop for e contando as ocorrências de cada iteração possível. Isso deve ser simples de implementar, mas vou sugerir uma solução abaixo que usa a funcionalidade de biblioteca existente que pode ser útil para você.
Em vez de medir os resultados de cada qubit, vamos implementar uma operação útil que nos permite medir a probabilidade de cada estado válido e a probabilidade de obter um estado inválido.
Em primeiro lugar, conforme explicado na postagem do blog, existem probabilidades de obter um dos 3 estados válidos e existe a probabilidade de obter um estado inválido:
// 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];
Controlaremos a probabilidade de obter um estado inválido à medida que os resultados forem chegando, subtraindo esses valores de 1,0.
mutable otherProb = 1.0; // Probability of any invalid state
Portanto, o que faremos é percorrer todos os estados válidos e medir a probabilidade de cada um e retorná-los com a probabilidade de obter qualquer estado inválido em uma matriz 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;
A energia, ou custo que queremos minimizar, pode então ser calculado multiplicando as probabilidades pelo custo de cada estado.
(Obviamente, para este exemplo, isso é um pouco bobo, pois podemos simplesmente calcular o custo de cada um dos estados permitidos acima e, em seguida, escolher o valor mais baixo. No entanto, em outras aplicações quânticas, o espaço de estados válidos pode, por exemplo, ser muito maior, e, nesse caso, precisaríamos apenas avaliar a função de custo para os estados que têm uma probabilidade diferente de zero.)
Então, como implementar MeasureProbabilityForState?
Podemos usar a operação EstimateFrequencypara isso. Esta operação mede a probabilidade de obter um Zeroresultado para determinadas operações de preparação e medição de estado. Veja a documentação aqui:https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.characterization.estimatefrequency.
A implementação pode ser semelhante a esta:
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
);
}
onde temos que verificar se o cadastro está no estado desejado e retornar Zerose estiver:
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)
}
}
Esta é apenas uma forma de EstimateFrequencyresolver o problema; Espero que este exemplo ajude você a descobrir a melhor maneira que funciona para sua aplicação quântica.