¿Cómo resolver los problemas de QUBO en Q #?

Question

Version corta:

Estoy tratando de resolver un problema de vendedor ambulante muy similar al ejemplo de Papá Noel que viaja aquí: http://quantumalgorithmzoo.org/traveling_santa/, que también se incluye en las muestras de las muestras de Microsoft Quantum aquí: https://github.com/microsoft/Quantum/tree/main/samples/simulation. En ese ejemplo, asumen algunos parámetros beta y gamma que producen probabilidades favorables de encontrar la ruta óptima. El problema es: ¿cómo se obtienen estos parámetros? Pero una pregunta más general que tengo es: ¿Cómo resolvería un problema QUBO (con un hamiltoniano de la forma$H = -\sum_i h_i \sigma_i^z -\sum_{i,j} J_{i,j} \sigma_i^z \sigma_j^z$) en qsharp?

Lo que he probado:

1. Sobre la base de la muestra de QAOA, lo primero que hice fue hacer trampa: utilicé un optimizador clásico para resolver los valores óptimos de beta y gamma, minimizando la energía. Y calculé la energía volcando el registro cuántico en un archivo. Con las probabilidades para cada estado, el valor estimado de la energía es simplemente$\sum_{states} p_{state} E_{state}$.

2. Por supuesto, en Azure Quantum / en hardware cuántico real, no tiene acceso a las probabilidades. Así que intenté encontrar formas de obtener estimaciones precisas de la energía. Aquí es donde estoy luchando dadas las muestras y la documentación. Tengo un registro de qubits y una ecuación hamiltoniana que me gustaría conectar, pero la función EstimateEnergy en Q # toma JordanWignerEncodingDatao un statePrepUnitaryy qpeUnitary. En ambos casos, no entiendo realmente cómo los construiría y qué hacen / por qué los necesito. Los esfuerzos para estimar la energía de la estimación de fase fallaron, pero eso podría deberse a mi falta de comprensión. Si esta es realmente una buena manera de resolver problemas de optimización, ¿existen buenos recursos para comprender esto mejor?

3. Lo último que intenté fue el principio de cambiar lentamente el hamiltoniano de uno que tiene un estado de base fácil de preparar, al hamiltoniano correspondiente al problema de optimización que desea resolver. El ejemplo y la explicación están aquí:https://github.com/microsoft/Quantum/blob/main/samples/simulation/ising/adiabatic/AdiabaticIsing.qs#L14. Desafortunadamente, parece que me quedo atascado en diferentes mínimos locales dependiendo de la tasa, y ninguno de ellos realmente se acerca a la solución real. Entonces encontré que este método tampoco es muy confiable.

Entiendo que la pregunta es muy similar a esta , pero incluso después de leer la respuesta allí, todavía no estoy seguro de si lo que estoy intentando tiene sentido y cómo hacer que funcione en Q #. Así que espero una respuesta más concreta o literatura adecuada para los desarrolladores que siguieron un curso de física cuántica hace muchos años.

Answer 1

Para responder a su primera pregunta, QAOA es una aplicación de un algoritmo híbrido cuántico clásico, por lo que utilizar un optimizador clásico es una solución perfectamente válida aquí. Sugeriría usar, por ejemplo, scipy.optimizecualquier otra de sus herramientas de optimización favoritas.

Su segunda pregunta tiene que ver con medir la energía del estado cuántico. De hecho, Q # no permite la inspección del estado cuántico porque, como señaló, esto tampoco es posible en hardware físico.

Sin embargo, hay algunas formas de recuperar esta información.

En un experimento en hardware real, lo que haría es simplemente medir todos los qubits una y otra vez, digamos Nveces, lo que le da una lista de Ncadenas de bits. Si Nes grande, esto le dará una distribución de probabilidad confiable de todos los estados del qubit. En la simulación, esto se puede hacer midiendo todos los qubits en el registro de qubit en un ciclo for y contando las ocurrencias de cada posible iteración. Esto debería ser sencillo de implementar, pero sugeriré una solución a continuación que utiliza la funcionalidad de biblioteca existente que puede resultarle útil.

En lugar de medir los resultados de cada qubit, vamos a implementar una práctica operación que nos permitirá medir la probabilidad de cada estado válido y la probabilidad de obtener un estado no válido.

En primer lugar, como se explica en la publicación del blog, existen las probabilidades de obtener uno de los 3 estados válidos y existe la probabilidad de obtener un estado no vá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];

Realizaremos un seguimiento de la probabilidad de obtener un estado no válido a medida que los resultados se obtengan restando estos valores de 1.0.

mutable otherProb = 1.0; // Probability of any invalid state

Entonces, lo que haremos es recorrer todos los estados válidos, y luego medir la probabilidad de cada uno, y devolverlos y la probabilidad de obtener cualquier estado no válido en una 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;

La energía, o el costo que queremos minimizar, se puede calcular multiplicando las probabilidades por el costo de cada estado.

(Obviamente, para este ejemplo esto es un poco tonto, ya que simplemente podemos calcular el costo de cada uno de los estados permitidos anteriores y luego elegir el valor más bajo. Sin embargo, en otras aplicaciones cuánticas, el espacio de estados válidos podría ser, por ejemplo, mucho mayor, y en ese caso solo necesitaríamos evaluar la función de costo para los estados que tienen una probabilidad distinta de cero.)

Entonces, ¿cómo implementar MeasureProbabilityForState?

Podemos usar la operación EstimateFrequencypara esto. Esta operación mide la probabilidad de obtener un Zeroresultado para operaciones de medición y preparación de estado determinadas. Consulte los documentos aquí:https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.characterization.estimatefrequency.

La implementación puede verse así:

    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
        );
    }

donde tenemos que comprobar si el registro se encuentra en el estado deseado y devolver Zerosi 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;
        }
    }

y

    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 es solo una forma de utilizar EstimateFrequencypara resolver este problema; Espero que este ejemplo le ayude a descubrir la mejor forma que funcione para su aplicación cuántica.