Квантовое программирование: Реализуем первый алгоритм на Q#

namespace QuantumRNG {
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Measurement;
    
    @EntryPoint()
    operation GenerateRandomBit() : Result {
        // Выделяем кубит
        use q = Qubit();
        
        // Приводим кубит в суперпозицию с помощью гейта Адамара
        H(q);
        
        // Измеряем кубит, заставляя его "схлопнуться" в 0 или 1
        let result = M(q);
        
        // Возвращаем кубит в исходное состояние |0⟩
        if (result == One) {
            X(q);
        }
        
        // Возвращаем результат
        return result;
    }
}

// Создание кубита в состоянии |0⟩
use q = Qubit();
 
// Приведение кубита в суперпозицию
H(q);  // Теперь q находится в состоянии (|0⟩ + |1⟩)/√2
 
// Измерение разрушает суперпозицию!
let result = M(q);  // Коллапс в |0⟩ или |1⟩

// В классическом программировании мы можем сделать так:
var x = 5;
Console.WriteLine(x);  // Выводит 5, x остаётся равным 5
 
// В квантовом мире:
use q = Qubit();
H(q);  // Кубит в суперпозиции
let result = M(q);  // Измерение ИЗМЕНЯЕТ состояние q!

// Создаём два кубита
use (q1, q2) = (Qubit(), Qubit());
 
// Приводим первый кубит в суперпозицию
H(q1);
 
// Запутываем кубиты с помощью CNOT
CNOT(q1, q2);
 
// Теперь q1 и q2 запутаны!
// Если измерить q1 и получить 0, то q2 тоже будет в состоянии 0
// Если измерить q1 и получить 1, то q2 тоже будет в состоянии 1

operation DeutschAlgorithm(oracle : ((Qubit, Qubit) => Unit)) : Bool {
    use (input, output) = (Qubit(), Qubit());
    
    // Инициализация
    X(output);
    H(input);
    H(output);
    
    // Применение оракула
    oracle(input, output);
    
    // Создание интерференции
    H(input);
    
    // Измерение результата
    let result = M(input) == Zero;
    
    // Очистка кубитов
    Reset(input);
    Reset(output);
    
    return result;  // True = постоянная, False = сбалансированная
}

operation BadApproach() : Result {
    use q = Qubit();
    H(q);
    let intermediateResult = M(q);  // Ошибка! Измерение разрушает суперпозицию
    // Дальнейшие квантовые операции бессмысленны
    return intermediateResult;
}
 
operation GoodApproach() : Result {
    use q = Qubit();
    H(q);
    // Выполняем все квантовые операции до измерения
    return M(q);  // Измеряем только в конце
}

use qubit = Qubit();

// Создание массива из 3 кубитов
use qubits = Qubit[3];
 
// Или можно использовать кортеж
use (q1, q2) = (Qubit(), Qubit());

use q = Qubit();
 
// X-гейт (аналог классического NOT)
X(q);  // |0⟩ -> |1⟩ или |1⟩ -> |0⟩
 
// H-гейт (гейт Адамара) - создаёт суперпозицию
H(q);  // |0⟩ -> (|0⟩ + |1⟩)/√2 или |1⟩ -> (|0⟩ - |1⟩)/√2
 
// Z-гейт (фазовый сдвиг)
Z(q);  // |0⟩ -> |0⟩, |1⟩ -> -|1⟩
 
// T-гейт (π/8 фазовый сдвиг)
T(q);  // |0⟩ -> |0⟩, |1⟩ -> e^(iπ/4)|1⟩
 
// S-гейт (фазовый сдвиг на π/2)
S(q);  // |0⟩ -> |0⟩, |1⟩ -> i|1⟩

use (control, target) = (Qubit(), Qubit());
 
// CNOT (Controlled-NOT) - классический XOR в квантовом мире
CNOT(control, target);  // Инвертирует target, если control в состоянии |1⟩
 
// SWAP - меняет состояния двух кубитов местами
SWAP(q1, q2);
 
// Controlled-Z - применяет Z к target, если control в состоянии |1⟩
Controlled Z([control], target);

operation CreateSuperposition() : Result {
    use q = Qubit();
    
    // Создаём суперпозицию с равными вероятностями
    H(q);
    
    // В этой точке q находится в состоянии (|0⟩ + |1⟩)/√2
    
    // Измеряем и получаем либо 0, либо 1 с вероятностью 50%
    let result = M(q);
    
    // Возвращаем кубит в исходное состояние |0⟩
    if (result == One) {
        X(q);
    }
    
    return result;
}

operation CreateEntanglement() : (Result, Result) {
    use (q1, q2) = (Qubit(), Qubit());
    
    // Шаг 1: Создаём суперпозицию первого кубита
    H(q1);
    
    // Шаг 2: Запутываем кубиты с помощью CNOT
    CNOT(q1, q2);
    
    // Теперь кубиты находятся в состоянии (|00⟩ + |11⟩)/√2
    // Это значит, что при измерении мы получим либо оба 0, либо оба 1
    
    // Измеряем оба кубита
    let result1 = M(q1);
    let result2 = M(q2);
    
    // Возвращаем кубиты в исходное состояние
    if (result1 == One) { X(q1); }
    if (result2 == One) { X(q2); }
    
    return (result1, result2);
}

// Условие на основе классического значения
if (classicalValue) {
    X(q);
}
 
// Применение операции, контролируемой состоянием кубита
use (control, target) = (Qubit(), Qubit());
Controlled X([control], target);  // X применяется к target только если control в состоянии |1⟩

// Применение произвольной операции под управлением кубита
operation ApplyControlledOperation(control : Qubit, target : Qubit, op : (Qubit => Unit)) : Unit {
    Controlled op([control], target);
}
 
// Использование:
ApplyControlledOperation(controlQubit, targetQubit, X);

// Операция, создающая состояние |+⟩
operation PrepareXPlus(q : Qubit) : Unit {
    H(q);
}
 
// Операция, создающая состояние |−⟩
operation PrepareXMinus(q : Qubit) : Unit {
    X(q);
    H(q);
}
 
// Операция, создающая состояние |i⟩
operation PrepareYPlus(q : Qubit) : Unit {
    H(q);
    S(q);
}
 
// Операция, создающая состояние |−i⟩
operation PrepareYMinus(q : Qubit) : Unit {
    H(q);
    S(q);
    Z(q);
}

operation PrepareGHZ(qubits : Qubit[]) : Unit {
    if (Length(qubits) == 0) {
        fail "Массив кубитов не может быть пустым";
    }
    
    // Создаём суперпозицию первого кубита
    H(qubits[0]);
    
    // Запутываем первый кубит со всеми остальными
    for (i in 1 .. Length(qubits) - 1) {
        CNOT(qubits[0], qubits[i]);
    }
    
    // Теперь кубиты находятся в состоянии (|000...0⟩ + |111...1⟩)/√2
}

// X-гейт (Паули-X) - вращение вокруг оси X на Блох-сфере
X(q);  // Меняет |0⟩ на |1⟩ и наоборот
 
// Y-гейт (Паули-Y) - вращение вокруг оси Y
Y(q);  // |0⟩ -> i|1⟩, |1⟩ -> -i|0⟩
 
// Z-гейт (Паули-Z) - вращение вокруг оси Z
Z(q);  // |0⟩ -> |0⟩, |1⟩ -> -|1⟩

operation CorrectBitFlipError(q : Qubit, errorType : Pauli) : Unit {
    // Исправление ошибки зависит от её типа
    if (errorType == PauliX) {
        X(q);  // Исправляем X-ошибку
    }
    elif (errorType == PauliY) {
        Y(q);  // Исправляем Y-ошибку
    }
    elif (errorType == PauliZ) {
        Z(q);  // Исправляем Z-ошибку
    }
}

operation PrepareAllZeros(qubits : Qubit[]) : Unit {
    // Сбрасываем все кубиты в состояние |0⟩
    ApplyToEach(Reset, qubits);
}
 
operation PrepareAllOnes(qubits : Qubit[]) : Unit {
    // Переводим все кубиты в состояние |1⟩
    ApplyToEach(X, qubits);
}
 
operation PrepareUniformSuperposition(qubits : Qubit[]) : Unit {
    // Создаём равную суперпозицию всех возможных состояний
    ApplyToEach(H, qubits);
    // Результат: равномерная суперпозиция 2^n базисных состояний
}

// Применение X к первым трём кубитам в регистре
ApplyToEachIndex(X, qubits[0..2]);
 
// Применение H к нечётным кубитам
ApplyToEachIndex(
    (idx, q) => { if (idx % 2 == 1) { H(q); } },
    qubits
);

// Базовое измерение в стандартном базисе
let result = M(qubit);  // Возвращает Zero или One
 
// Измерение в базисе X (Адамара)
let resultX = Measure([PauliX], [qubit]);
 
// Измерение в базисе Y
let resultY = Measure([PauliY], [qubit]);
 
// Измерение в базисе Z (эквивалентно M())
let resultZ = Measure([PauliZ], [qubit]);
 
// Измерение набора кубитов в разных базисах
let multiResult = Measure([PauliX, PauliZ, PauliY], [qubit1, qubit2, qubit3]);

use q = Qubit();
H(q);  // Создаём суперпозицию
 
// Измеряем кубит, он коллапсирует в |0⟩ или |1⟩
let result = M(q);
 
// После этой точки q больше не в суперпозиции!
// Мы можем использовать результат измерения для принятия классических решений
if (result == One) {
    // Делаем что-то, если результат 1
    Message("Измерен 1");
} else {
    // Делаем что-то, если результат 0
    Message("Измерен 0");
}

operation InspectState(q : Qubit) : Unit {
    // Функция DumpMachine выводит полное квантовое состояние
    // Она доступна только в симуляторе!
    DumpMachine();
    
    // Вывод вероятностей для конкретного кубита
    let prob = Prob([PauliZ], [q]);
    Message($"Вероятность измерить |0⟩: {prob}");
}

// Вывод информации о конкретном подмножестве кубитов
DumpRegister((), qubits);

// Для полноценной симуляции с небольшим числом кубитов
using (sim = new QuantumSimulator()) {
    RunQuantumAlgorithm.Run(sim);
}
 
// Для оценки ресурсов крупного алгоритма
using (estimator = new ResourcesEstimator()) {
    RunQuantumAlgorithm.Run(estimator);
}

operation ReflectAboutUniform(qubits : Qubit[]) : Unit {
    // Применяем H ко всем кубитам
    ApplyToEach(H, qubits);
    
    // Инвертируем фазу для всех состояний кроме |00...0⟩
    // Сначала переводим все кубиты в состояние |1⟩
    ApplyToEach(X, qubits);
    
    // Применяем многокубитную Z под контролем всех кубитов
    Controlled Z(qubits[1...], qubits[0]);
    
    // Возвращаем кубиты в исходное состояние
    ApplyToEach(X, qubits);
    
    // Применяем H ко всем кубитам
    ApplyToEach(H, qubits);
}

// Определение типа для оракула
operation Oracle (input : Qubit[], output : Qubit) : Unit is Adj+Ctl {
// Реализация будет подставлена позже
}

operation DeutschJozsaAlgorithm(n : Int, oracle : ((Qubit[], Qubit) => Unit is Adj+Ctl)) : Bool {
// Выделяем n входных кубитов и 1 выходной
use (input, output) = (Qubit[n], Qubit());
 
// Шаг 1: Инициализация выходного кубита в состояние |1⟩
X(output);
 
// Шаг 2: Применяем H ко всем кубитам
ApplyToEach(H, input);
H(output);
 
// Шаг 3: Применяем оракул
oracle(input, output);
 
// Шаг 4: Снова применяем H к входным кубитам
ApplyToEach(H, input);
 
// Шаг 5: Измеряем и проверяем, все ли кубиты в состоянии |0⟩
mutable allZeros = true;
for (i in 0 .. n - 1) {
    if (M(input[i]) == One) {
        set allZeros = false;
    }
}
 
// Сбрасываем все кубиты в |0⟩
ResetAll(input);
Reset(output);
 
// Возвращаем результат: true = константная, false = сбалансированая
return allZeros;
}

// Константная функция, всегда возвращающая 0
operation ConstantZeroOracle(input : Qubit[], output : Qubit) : Unit is Adj+Ctl {
// Ничего не делаем - output остаётся в исходном состоянии
}
 
// Константная функция, всегда возвращающая 1
operation ConstantOneOracle(input : Qubit[], output : Qubit) : Unit is Adj+Ctl {
// Инвертируем выходной кубит
X(output);
}
 
// Сбалансированная функция: f(x) = x₀ ⊕ x₁ ⊕ ... ⊕ xₙ₋₁
operation BalancedOracle(input : Qubit[], output : Qubit) : Unit is Adj+Ctl {
// XOR всех входных битов
for (i in 0 .. Length(input) - 1) {
    CNOT(input[i], output);
}
}

@EntryPoint()
operation RunDeutschJozsa() : Unit {
let n = 3;  // Число входных кубитов
    
Message("Тестирование константного оракула (всегда 0):");
let isConstant1 = DeutschJozsaAlgorithm(n, ConstantZeroOracle);
Message($"Функция константная: {isConstant1}");
    
Message("Тестирование константного оракула (всегда 1):");
let isConstant2 = DeutschJozsaAlgorithm(n, ConstantOneOracle);
Message($"Функция константная: {isConstant2}");
    
Message("Тестирование сбалансированного оракула:");
let isConstant3 = DeutschJozsaAlgorithm(n, BalancedOracle);
Message($"Функция константная: {isConstant3}");
}

Тестирование константного оракула (всегда 0):
Функция константная: true
Тестирование константного оракула (всегда 1):
Функция константная: true
Тестирование сбалансированного оракула:
Функция константная: false

// Оракул, который возвращает 1, если строка начинается с 11
operation PrefixOracle(input : Qubit[], output : Qubit) : Unit is Adj+Ctl {
if (Length(input) >= 2) {
    // Если первые два бита 1, применяем CNOT к output
    Controlled X([input[0], input[1]], output);
}
}

function IsConstantClassical(f, n) {
    // Запоминаем результат первого вызова
    let firstResult = f(0);
    
    // Проверяем половину + 1 возможных входных значений
    for (i in 1 .. 2^(n-1)) {
        if (f(i) != firstResult) {
            return false; // Функция сбалансированная
        }
    }
    
    return true; // Функция константная
}

operation OptimizedDeutschJozsa(n : Int, oracle : ((Qubit[], Qubit) => Unit is Adj+Ctl)) : Bool {
    use (input, output) = (Qubit[n], Qubit());
    
    X(output);
    ApplyToEach(H, input);
    H(output);
    
    oracle(input, output);
    
    ApplyToEach(H, input);
    
    // Измеряем все кубиты сразу и проверяем результат
    let result = MeasureAllZ(input);
    let allZeros = IsResultZero(result);
    
    ResetAll(input);
    Reset(output);
    
    return allZeros;
}

operation PhaseOracleConstant(qubits : Qubit[]) : Unit is Adj+Ctl {
    // Константная функция, не делаем ничего
}
 
operation PhaseOracleBalanced(qubits : Qubit[]) : Unit is Adj+Ctl {
    // Сбалансированная функция, инвертирует фазу для половины состояний
    Z(qubits[0]);
}
 
operation SimplifiedDeutschJozsa(n : Int, oracle : ((Qubit[]) => Unit is Adj+Ctl)) : Bool {
    use qubits = Qubit[n];
    
    ApplyToEach(H, qubits);
    
    oracle(qubits);
    
    ApplyToEach(H, qubits);
    
    let result = MeasureAllZ(qubits);
    let allZeros = IsResultZero(result);
    
    ResetAll(qubits);
    
    return allZeros;
}

operation CustomOracle(input : Qubit[], output : Qubit) : Unit is Adj+Ctl {
    // Пример сложной функции: f(x) = (x₀ AND x₁) XOR (x₂ AND x₃)
    use ancilla = Qubit[2];
    
    // Вычисляем промежуточные результаты
    Controlled X([input[0], input[1]], ancilla[0]);  // ancilla[0] = x₀ AND x₁
    Controlled X([input[2], input[3]], ancilla[1]);  // ancilla[1] = x₂ AND x₃
    
    // Применяем XOR к выходу
    CNOT(ancilla[0], output);
    CNOT(ancilla[1], output);
    
    // Отменяем вычисления для очистки вспомогательных кубитов
    Controlled X([input[2], input[3]], ancilla[1]);
    Controlled X([input[0], input[1]], ancilla[0]);
}

operation GeneralizedDeutschJozsa(n : Int, oracle : ((Qubit[], Qubit) => Unit is Adj+Ctl)) : Double {
    use (input, output) = (Qubit[n], Qubit());
    
    X(output);
    ApplyToEach(H, input);
    H(output);
    
    oracle(input, output);
    
    ApplyToEach(H, input);
    
    // Оцениваем "степень сбалансированности" функции
    mutable zeroCount = 0;
    for (i in 0 .. n - 1) {
        if (M(input[i]) == Zero) {
            set zeroCount += 1;
        }
    }
    
    ResetAll(input);
    Reset(output);
    
    // Возвращаем долю нулевых результатов
    return IntAsDouble(zeroCount) / IntAsDouble(n);
}

operation HybridQuantumClassicalAlgorithm(data : Bool[][]) : Int {
    // Фаза 1: Используем алгоритм Дойча-Йожи для предварительного анализа
    let isConstantPattern = DeutschJozsaAlgorithm(/* ... */);
    
    // Фаза 2: На основе результатов выбираем оптимальную стратегию
    if (isConstantPattern) {
        // Применяем один подход
        return SimpleClassicalProcessing(data);
    } else {
        // Применяем другой подход, например, квантовый поиск
        return QuantumSearch(data);
    }
}

operation BernsteinVaziraniAlgorithm(n : Int, oracle : ((Qubit[], Qubit) => Unit is Adj+Ctl)) : Int[] {
use (input, output) = (Qubit[n], Qubit());
 
// Переводим выходной кубит в состояние |−⟩
X(output);
H(output);
 
// Создаём суперпозицию всех возможных входных значений
ApplyToEach(H, input);
 
// Применяем оракул
oracle(input, output);
 
// Применяем H к входным кубитам для извлечения s
ApplyToEach(H, input);
 
// Измеряем каждый кубит для получения bitstring s
mutable resultArray = new Int[n];
for (i in 0 .. n - 1) {
    if (M(input[i]) == One) {
        set resultArray w/= i <- 1;
    } else {
        set resultArray w/= i <- 0;
    }
}
 
// Сбрасываем кубиты
ResetAll(input);
Reset(output);
 
return resultArray;
}

operation SecretStringOracle(secretString : Bool[], queryRegister : Qubit[], target : Qubit) : Unit is Adj+Ctl {
for (i in 0 .. Length(secretString) - 1) {
    if (secretString[i]) {
        // Если бит в секретной строке равен 1, включаем этот кубит в XOR
        CNOT(queryRegister[i], target);
    }
}
}

operation GroverSearch(n : Int, oracle : ((Qubit[]) => Unit is Adj)) : Int {
// Определяем оптимальное число итераций
let iterations = Round(PI() / 4.0 * Sqrt(IntAsDouble(2^n)));
 
use qubits = Qubit[n];
 
// Создаём равномерную суперпозицию
ApplyToEach(H, qubits);
 
// Основной цикл алгоритма Гровера
for (i in 1 .. iterations) {
    // Фаза 1: Применяем оракул для инвертирования фазы целевого состояния
    oracle(qubits);
    
    // Фаза 2: Амплитудное усиление
    ApplyToEach(H, qubits);
    ApplyToEach(X, qubits);
    
    Controlled Z(qubits[1 .. n-1], qubits[0]);
    
    ApplyToEach(X, qubits);
    ApplyToEach(H, qubits);
}
 
// Измеряем результат
let result = MeasureInteger(BigEndian(qubits));
 
ResetAll(qubits);
 
return result;
}

operation MarkingOracle(target : Int, qubits : Qubit[]) : Unit is Adj {
// Создаём условие, которое выполняется только для целевого значения
let n = Length(qubits);
let targetBits = IntAsBoolArray(target, n);
 
// Применяем X к кубитам, соответствующим 0 в целевом значении
for (i in 0 .. n - 1) {
    if (not targetBits[i]) {
        X(qubits[i]);
    }
}
 
// Инвертируем фазу целевого состояния
Controlled Z(qubits[1 .. n-1], qubits[0]);
 
// Отменяем применённые X-гейты
for (i in 0 .. n - 1) {
    if (not targetBits[i]) {
        X(qubits[i]);
    }
}
}

operation SimonAlgorithm(n : Int, oracle : ((Qubit[], Qubit[]) => Unit is Adj)) : Bool[] {
mutable results = new Bool[n];
mutable equations = new Bool[][0];
 
use (queryRegister, outputRegister) = (Qubit[n], Qubit[n]);
 
while (Length(equations) < n - 1) {
    // Готовим входной регистр
    ApplyToEach(H, queryRegister);
    
    // Применяем оракул
    oracle(queryRegister, outputRegister);
    
    // Измеряем выходной регистр (опционально)
    // Это измерение коллапсирует суперпозицию, но не влияет на конечный результат
    let outputMeasurement = MultiM(outputRegister);
    
    // Применяем H к входным кубитам для получения значений, ортогональных s
    ApplyToEach(H, queryRegister);
    
    // Измеряем и получаем уравнение y·s = 0 (mod 2)
    mutable equation = new Bool[n];
    for (i in 0 .. n - 1) {
        if (M(queryRegister[i]) == One) {
            set equation w/= i <- true;
        }
    }
    
    // Проверяем, что уравнение не тривиально и линейно независимо
    if (not IsAllZeros(equation)) {
        set equations += [equation];
    }
    
    // Сбрасываем кубиты
    ResetAll(queryRegister);
    ResetAll(outputRegister);
}
 
// Решаем систему линейных уравнений для нахождения s
// (упрощённая версия для иллюстрации)
return SolveLinearEquations(equations);
}

operation DebugQuantumState() : Unit {
use qubits = Qubit[3];
H(qubits[0]);
CNOT(qubits[0], qubits[1]);
T(qubits[2]);
 
// Выводит полное состояние квантовой системы
DumpMachine();
 
// Выводит информацию только о подмножестве кубитов
DumpRegister((), qubits[0..1]);
}

using (estimator = new ResourcesEstimator()) {
MyQuantumAlgorithm.Run(estimator);
}

operation SafeQuantumOperation() : Result {
use q = Qubit();
mutable result = Zero;
 
try {
H(q);
// Потенциально опасная операция
set result = M(q);
} catch {
// Обработка ошибки
Message("Произошла ошибка при выполнении квантовой операции");
Reset(q);  // Всегда сбрасываем кубиты
}
 
// Даже если исключение не возникло, нужно сбросить кубиты
if (result == One) { X(q); }
 
return result;
}