Q# - универсальный язык Microsoft для квантовых вычислений

namespace Quantum.HelloWorld {
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Intrinsic;
    
    operation SayHello() : Unit {
        Message("Hello quantum world!");
    }
}

operation AllocateQubit() : Result {
    use qubit = Qubit();  // Выделение одного кубита
    
    // По умолчанию кубит инициализирован в состоянии |0⟩
    
    H(qubit);  // Применяем гейт Адамара, создавая суперпозицию
    
    let result = M(qubit);  // Измеряем кубит, что коллапсирует его состояние
    
    Reset(qubit);  // Важно сбросить кубит в |0⟩ перед освобождением
    return result;
}

operation CreateBellPair() : (Result, Result) {
    use (q1, q2) = (Qubit(), Qubit());
    
    H(q1);           // Перевести первый кубит в суперпозицию
    CNOT(q1, q2);    // Запутать оба кубита
    
    // Измерить оба кубита и вернуть результаты
    let r1 = M(q1);
    let r2 = M(q2);
    
    Reset(q1);
    Reset(q2);
    
    return (r1, r2);
}

operation PrepareRegister(nQubits : Int) : Result[] {
    use register = Qubit[nQubits];  // Выделяем массив кубитов
    
    // Применяем Адамара ко всем кубитам
    for q in register {
        H(q);
    }
    
    // Можно применить операцию к целому регистру
    let results = MultiM(register);
    
    ResetAll(register);  // Сбрасываем все кубиты
    
    return results;
}

operation ApplyRotation(qubit : Qubit, angle : Double) : Unit is Adj {
    Rx(angle, qubit);
    Rz(angle * 2.0, qubit);
}
 
operation UndoRotation(qubit : Qubit, angle : Double) : Unit {
    Adjoint ApplyRotation(qubit, angle);
}

operation ApplyControlledX(control : Qubit, target : Qubit) : Unit {
    Controlled X([control], target);
}

operation MeasureWithProbability() : Unit {
    use q = Qubit();
    
    // Создаем суперпозицию с вероятностями |0⟩: 30%, |1⟩: 70%
    Ry(2.0 * ArcSin(Sqrt(0.7)), q);
    
    let result = M(q);
    
    if (result == One) {
        Message("Измерено |1⟩");
    } else {
        Message("Измерено |0⟩");
    }
    
    Reset(q);
}

operation ConditionalOperation(control : Qubit, target : Qubit) : Unit {
    let result = M(control);
    
    if (result == One) {
        X(target);  // Применить X только если control измерен как |1⟩
    }
    
    // Вернуть control в исходное состояние, если нужно
    if (result == One) {
        X(control);
    }
}

operation ApplyQFT(register : Qubit[]) : Unit is Adj {
let n = Length(register);
 
for i in 0 .. n - 1 {
    H(register[i]);
    
    for j in i + 1 .. n - 1 {
        Controlled R1Frac([register[j]], (1, j - i, register[i]));
    }
}
 
// Переворачиваем порядок кубитов
for i in 0 .. n / 2 - 1 {
    SWAP(register[i], register[n - i - 1]);
}
}

operation TeleportQubit(source : Qubit, target : Qubit) : Unit {
use ancilla = Qubit();
 
H(ancilla);
CNOT(ancilla, target);
 
CNOT(source, ancilla);
H(source);
 
if (M(source) == One) {
    Z(target);
}
 
if (M(ancilla) == One) {
    X(target);
}
 
// Сбрасываем вспомогательный кубит
Reset(ancilla);
}

operation EntangleRegister(register : Qubit[]) : Unit {
let n = Length(register);
 
// Первый кубит контролирует все остальные
H(register[0]);
 
for i in 1 .. n - 1 {
    CNOT(register[0], register[i]);
}
 
// Теперь все кубиты запутаны с первым
}

operation ApplyToEach<'T>(op : ('T => Unit), targets : 'T[]) : Unit {
for target in targets {
    op(target);
}
}
 
operation ApplyHadamardToAll(qubits : Qubit[]) : Unit {
ApplyToEach(H, qubits);
}

operation CreateGHZState(qubits : Qubit[]) : Unit is Adj {
if (Length(qubits) > 0) {
    H(qubits[0]);
    
    for i in 1 .. Length(qubits) - 1 {
        CNOT(qubits[0], qubits[i]);
    }
}
}

// В файле Utilities.qs
namespace Quantum.Utilities {
open Microsoft.Quantum.Intrinsic;
 
operation PrepareUniform(qubits : Qubit[]) : Unit is Adj {
for q in qubits {
    H(q);
}
}
}
 
// В другом файле
namespace Quantum.Algorithm {
open Microsoft.Quantum.Intrinsic;
open Quantum.Utilities;
 
operation RunAlgorithm(n : Int) : Result[] {
use qubits = Qubit[n];
PrepareUniform(qubits);
// ...остальной код...
}
}

function DividedBy(divisor : Int, dividend : Int) : Bool {
return dividend % divisor == 0;
}
 
function IsDivisibleBy3(n : Int) : Bool {
return DividedBy(3, n);
}
 
@EntryPoint()
operation CheckNumbers() : Unit {
let numbers = [3, 6, 9, 12, 15, 7, 11];
let divisibleBy3 = Filtered(IsDivisibleBy3, numbers);
Message($"Числа, делящиеся на 3: {divisibleBy3}");
}

// Неоптимальная версия
operation ApplyXThenH(q : Qubit) : Unit {
X(q);
H(q);
}
 
// Оптимизированная версия с использованием Y-гейта
operation OptimizedVersion(q : Qubit) : Unit {
Y(q);
S(q);
}

operation DebugQuantumState(q : Qubit) : Unit {
Message($"Вероятность измерения |1⟩: {Abs(Sin(2.0))^2}");
 
// В симуляторе можно использовать недетерминированные операции
// для проверки состояния без его измерения
let (isInOne, prob) = IsResultOne(q);
Message($"Кубит в состоянии |1⟩: {isInOne}, вероятность: {prob}");
 
// Визуализация состояния для отладки
DumpMachine();
}

operation DebugState() : Unit {
    use qubits = Qubit[3];
    
    // Создаем сложное состояние
    H(qubits[0]);
    CNOT(qubits[0], qubits[1]);
    H(qubits[2]);
    
    // Визуализируем текущее состояние
    DumpMachine();
    
    ResetAll(qubits);
}

@Test("QuantumSimulator")
operation QuantumRNGTest() : Unit {
    use q = Qubit();
    
    H(q);  // Создаем суперпозицию
    let result = M(q);
    
    // Проверяем, что результат действительно случаен
    // В большом количестве запусков примерно 50% будет One и 50% - Zero
    Reset(q);
}

// Этот код может работать как на симуляторе,
// так и на реальном квантовом устройстве
operation SampleRandomBit() : Result {
    use q = Qubit();
    H(q);
    let result = M(q);
    Reset(q);
    return result;
}

// Пример из Quantum Kata "Basic Gates"
operation StatePrep_ZeroState(q : Qubit) : Unit {
    // Задача: подготовить кубит в состоянии |0⟩
    // Решение: кубит уже в состоянии |0⟩ по умолчанию
}
 
operation StatePrep_PlusState(q : Qubit) : Unit {
    // Задача: подготовить кубит в состоянии |+⟩
    // Решение:
    H(q);
}

operation OptimizedCircuit(q : Qubit) : Unit {
    // Исходная последовательность
    X(q);
    H(q);
    Z(q);
    
    // После оптимизации компилятор может заменить это на:
    // Y(q);
    // S(q);
}

operation AdiabiaticAlgorithm() : Result[] {
    // Определение гамильтониана проблемы
    let problemHamiltonian = GenerateProblemHamiltonian();
    
    // Определение начального гамильтониана
    let initialHamiltonian = GenerateInitialHamiltonian();
    
    // Параметры адиабатической эволюции
    let evolutionTime = 100.0;
    let steps = 1000;
    
    // Запуск адиабатической эволюции
    return SimulateAdiabiaticEvolution(
        initialHamiltonian, 
        problemHamiltonian, 
        evolutionTime, 
        steps);
}

namespace GroverSearch {
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Math;
    
    // Оракул - функция, которая распознает решение
    operation Oracle(register : Qubit[], target : Qubit) : Unit is Adj+Ctl {
        // Предположим, что мы ищем строку 101
        // Инвертируем целевой кубит, если входной регистр в состоянии |101⟩
        (ControlledOnBitString([true, false, true], X))(register, target);
    }
    
    // Отражение относительно среднего - ключевая часть алгоритма Гровера
    operation ReflectAboutMean(register : Qubit[]) : Unit is Adj+Ctl {
        within {
            ApplyToEachA(H, register);
            ApplyToEachA(X, register);
        } apply {
            Controlled Z(Most(register), Tail(register));
        }
    }
    
    // Основная операция поиска
    operation GroverSearch(nQubits : Int) : Result[] {
        use register = Qubit[nQubits];
        use target = Qubit();
        
        // Инициализация регистра в равную суперпозицию
        ApplyToEach(H, register);
        
        // Вычисляем оптимальное число итераций
        let nIterations = Round(PI() / 4.0 * Sqrt(IntAsDouble(2^nQubits)));
        
        for _ in 1..nIterations {
            // Применяем оракул
            within {
                X(target);
                H(target);
            } apply {
                Oracle(register, target);
            }
            
            // Отражение относительно среднего
            ReflectAboutMean(register);
        }
        
        // Измеряем регистр - с высокой вероятностью получим искомое значение
        let result = MultiM(register);
        ResetAll(register);
        Reset(target);
        
        return result;
    }
}

// Ищем число 5 (101 в двоичной системе)
let markedElement = 5;
(ControlledOnInt(markedElement, X))(register, target);

namespace ShorAlgorithm {
    open Microsoft.Quantum.Arithmetic;
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Oracles;
    open Microsoft.Quantum.Characterization;
    
    // Модульное возведение в степень
    operation ModExp(modulus : Int, exponent : Int, generator : Int, target : Qubit[]) : Unit is Adj+Ctl {
        let modulusLE = LittleEndian(target);
        
        // Инициализация в |1⟩
        ApplyXorInPlace(1, modulusLE);
        
        // Последовательное умножение на generator^(2^i) для каждого 1-бита в exponent
        for (power, bitPosition) in Zip(
            ExponentiatedGenerator(modulus, generator), 
            BinaryRepresentationWithHighestBitFirst(exponent)
        ) {
            if (bitPosition) {
                ModularMultiplyByConstant(modulus, power, modulusLE);
            }
        }
    }
    
    // Квантовое преобразование Фурье
    operation QFT(register : Qubit[]) : Unit is Adj {
        let n = Length(register);
        
        for (i in 0 .. n - 1) {
            H(register[i]);
            
            for (j in i + 1 .. n - 1) {
                let angle = 2.0 * PI() / IntAsDouble(2^(j - i));
                Controlled R1([register[j]], (angle, register[i]));
            }
        }
        
        // Переворачиваем порядок кубитов
        SwapReverseRegister(register);
    }
    
    // Оценка периода - ключевая квантовая часть алгоритма Шора
    operation EstimatePeriod(modulus : Int, generator : Int, precision : Int) : Int {
        // Выделяем регистры
        use eigenstateRegister = Qubit[BitSizeI(modulus)];
        use measurementRegister = Qubit[precision];
        
        // Подготавливаем регистр измерения в суперпозицию
        ApplyToEach(H, measurementRegister);
        
        // Применяем контролируемое модульное возведение в степень
        for (idx, measureQubit) in Enumerated(measurementRegister) {
            let power = 2^idx;
            Controlled ModExp([measureQubit], (modulus, power, generator, eigenstateRegister));
        }
        
        // Применяем обратное квантовое преобразование Фурье
        Adjoint QFT(measurementRegister);
        
        // Измеряем регистр и получаем оценку периода
        let measurement = MeasureInteger(LittleEndian(measurementRegister));
        let (numerator, denominator) = ContinuedFractionConvergent(
            IntAsDouble(measurement) / IntAsDouble(2^precision),
            modulus);
        
        ResetAll(eigenstateRegister);
        ResetAll(measurementRegister);
        
        return denominator;
    }
    
    // Главная функция
    operation FactorInteger(number : Int) : (Int, Int) {
        // Классическая предобработка
        if (number % 2 == 0) {
            return (2, number / 2);
        }
        
        // Выбор случайного числа для начала алгоритма
        let generator = RandomInt(number - 1) + 1;
        let gcd = GreatestCommonDivisorI(generator, number);
        
        if (gcd > 1) {
            return (gcd, number / gcd);
        }
        
        // Квантовая часть - поиск периода
        let period = EstimatePeriod(number, generator, 2 * BitSizeI(number));
        
        // Классическая постобработка
        if (period % 2 == 0) {
            let halfPower = ExpModI(generator, period / 2, number);
            
            if (halfPower != number - 1) {
                let factor1 = GreatestCommonDivisorI(halfPower - 1, number);
                let factor2 = GreatestCommonDivisorI(halfPower + 1, number);
                
                if (factor1 > 1) {
                    return (factor1, number / factor1);
                }
                elseif (factor2 > 1) {
                    return (factor2, number / factor2);
                }
            }
        }
        
        // Если не удалось найти множители, пробуем снова
        return FactorInteger(number);
    }
}

namespace DeutschJozsa {
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Measurement;
    
    // Оракул для константной функции
    operation ConstantOracle(input : Qubit[], output : Qubit) : Unit is Adj+Ctl {
        // Для константной функции f(x) = 0, ничего не делаем
        // Для константной функции f(x) = 1, инвертируем выход:
        // X(output);
    }
    
    // Оракул для сбалансированной функции
    operation BalancedOracle(input : Qubit[], output : Qubit) : Unit is Adj+Ctl {
        // Для сбалансированной функции, инвертируем выход
        // в зависимости от четности числа единиц во входе
        CNOT(input[0], output);
    }
    
    // Алгоритм Дойча-Йожи
    operation DeutschJozsaAlgorithm(nQubits : Int, oracle : ((Qubit[], Qubit) => Unit is Adj+Ctl)) : Bool {
        use input = Qubit[nQubits];
        use output = Qubit();
        
        // Инициализация output в состояние |1⟩
        X(output);
        
        // Применяем преобразования Адамара
        ApplyToEach(H, input);
        H(output);
        
        // Применяем оракул
        oracle(input, output);
        
        // Снова применяем Адамара к входным кубитам
        ApplyToEach(H, input);
        
        // Измеряем результат
        let results = MultiM(input);
        
        // Сбрасываем кубиты
        ResetAll(input);
        Reset(output);
        
        // Если все измерения дали 0, функция константная
        return All(ResultIsZero, results);
    }
}

// Тест алгоритма
operation TestDeutschJozsa() : String {
    let isConstantForConstantOracle = DeutschJozsaAlgorithm(3, ConstantOracle);
    let isConstantForBalancedOracle = DeutschJozsaAlgorithm(3, BalancedOracle);
    
    return $"Константный оракул определен как {isConstantForConstantOracle}, сбалансированный оракул определен как {not isConstantForBalancedOracle}";
}

namespace QAOA {
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Math;
    
    // Гамильтониан проблемы для MaxCut
    operation ApplyProblemHamiltonian(
        graph : (Int, Int)[], // Список ребер
        beta : Double, 
        qubits : Qubit[]
    ) : Unit {
        for (u, v) in graph {
            // Реализация взаимодействия ZZ между кубитами
            CNOT(qubits[u], qubits[v]);
            Rz(2.0 * beta, qubits[v]);
            CNOT(qubits[u], qubits[v]);
        }
    }
    
    // Гамильтониан смешивания
    operation ApplyMixingHamiltonian(
        gamma : Double, 
        qubits : Qubit[]
    ) : Unit {
        for q in qubits {
            Rx(2.0 * gamma, q);
        }
    }
    
    // Один слой QAOA
    operation ApplyQAOALayer(
        graph : (Int, Int)[], 
        beta : Double, 
        gamma : Double, 
        qubits : Qubit[]
    ) : Unit {
        ApplyProblemHamiltonian(graph, beta, qubits);
        ApplyMixingHamiltonian(gamma, qubits);
    }
    
    // Полный алгоритм QAOA
    operation RunQAOA(
        nVertices : Int,
        graph : (Int, Int)[],
        layers : Int,
        betas : Double[],
        gammas : Double[]
    ) : Int[] {
        // Создаем кубиты - по одному на каждую вершину графа
        use qubits = Qubit[nVertices];
        
        // Начинаем с равной суперпозиции
        ApplyToEach(H, qubits);
        
        // Применяем слои QAOA
        for idx in 0 .. layers - 1 {
            ApplyQAOALayer(graph, betas[idx], gammas[idx], qubits);
        }
        
        // Измеряем результат
        let result = MeasureEachZ(qubits);
        
        // Сбрасываем кубиты
        ResetAll(qubits);
        
        return ResultArrayAsInt(result);
    }
}

namespace QuantumTeleportation {
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Measurement;
    
    operation TeleportQubit(source : Qubit, target : Qubit) : Unit {
        use auxiliary = Qubit();
        
        // Создаем запутанную пару между auxiliary и target
        H(auxiliary);
        CNOT(auxiliary, target);
        
        // Запутываем source и auxiliary
        CNOT(source, auxiliary);
        H(source);
        
        // Измеряем оба кубита
        let measurementZ = M(source);
        let measurementX = M(auxiliary);
        
        // Применяем корректирующие операции
        if (measurementX == One) {
            Z(target);
        }
        
        if (measurementZ == One) {
            X(target);
        }
        
        // Сбрасываем вспомогательный кубит
        Reset(auxiliary);
    }
    
    // Тест телепортации
    operation TestTeleportation() : Unit {
        use source = Qubit();
        use target = Qubit();
        
        // Готовим нетривиальное состояние
        Ry(0.5, source);
        
        // Телепортируем состояние
        TeleportQubit(source, target);
        
        // В этот момент target должен быть в том же состоянии, что и source изначально
        
        // Проверяем результат (в реальности это невозможно, т.к. требует знания состояния)
        Ry(-0.5, target);
        let result = M(target);
        
        // Если телепортация идеальна, результат должен быть Zero
        Assert(result == Zero, "Телепортация не сработала корректно");
        
        ResetAll([source, target]);
    }
}

operation CreateBellState() : (Result, Result) {
    use (q1, q2) = (Qubit(), Qubit());
    
    H(q1);
    CNOT(q1, q2);
    
    let r1 = M(q1);
    let r2 = M(q2);
    
    Reset(q1);
    Reset(q2);
    
    return (r1, r2);
}

// Соответствующая Q# операция
operation RotateAndMeasure(angle : Double) : Result {
    use q = Qubit();
    Rx(angle, q);
    let result = M(q);
    Reset(q);
    return result;
}

operation PrepareAndMeasureBB84(basis : Pauli, sendBit : Bool) : Bool {
    use q = Qubit();
    
    // Подготовка состояния
    if (sendBit) {
        X(q);
    }
    
    // Выбор базиса
    if (basis == PauliX) {
        H(q);
    }
    
    // Измерение
    let result = Measure([basis], [q]) == Zero ? false | true;
    Reset(q);
    
    return result;
}
 
operation BB84Protocol(numBits : Int) : (Bool[], Bool[], Pauli[], Pauli[]) {
    mutable senderBits = new Bool[numBits];
    mutable receiverBits = new Bool[numBits];
    mutable senderBases = new Pauli[numBits];
    mutable receiverBases = new Pauli[numBits];
    
    for (i in 0..numBits-1) {
        // Случайный выбор базиса и бита отправителем
        set senderBases w/= i <- RandomPauli([PauliZ, PauliX]);
        set senderBits w/= i <- RandomBool();
        
        // Случайный выбор базиса получателем
        set receiverBases w/= i <- RandomPauli([PauliZ, PauliX]);
        
        // Отправка и измерение
        set receiverBits w/= i <- PrepareAndMeasureBB84(senderBases[i], senderBits[i]);
    }
    
    return (senderBits, receiverBits, senderBases, receiverBases);
}

namespace QuantumRNG {
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Convert;
    
    // Генерирует один случайный бит
    operation GenerateRandomBit() : Result {
        use q = Qubit();
        H(q);         // Переводим кубит в суперпозицию
        let result = M(q);  // Измеряем
        Reset(q);     // Важно сбросить кубит перед освобождением
        return result;
    }
    
    // Генерирует 8-битное случайное число (байт)
    operation GenerateRandomByte() : Int {
        mutable results = new Result[8];
        
        for (i in 0..7) {
            set results w/= i <- GenerateRandomBit();
        }
        
        return ResultArrayAsInt(results);
    }
    
    // Генерирует массив случайных байтов
    operation GenerateRandomBytes(count : Int) : Int[] {
        mutable bytes = new Int[count];
        
        for (i in 0..count-1) {
            set bytes w/= i <- GenerateRandomByte();
        }
        
        return bytes;
    }
    
    // Альтернативный метод с использованием запутанности
    operation GenerateEntangledRandomBits(count : Int) : Result[] {
        use qubits = Qubit[count];
        
        // Подготавливаем запутанное GHZ-состояние
        H(qubits[0]);
        for (i in 1..count-1) {
            CNOT(qubits[0], qubits[i]);
        }
        
        // Применяем индивидуальные вращения для разрушения корреляций
        for (i in 0..count-1) {
            Rx(1.1 * IntAsDouble(i), qubits[i]);
            Ry(0.7 * IntAsDouble(i), qubits[i]);
        }
        
        // Измеряем все кубиты
        let results = MultiM(qubits);
        
        // Сбрасываем состояние
        ResetAll(qubits);
        
        return results;
    }
}