Program.qs

namespace Quantum.Guest_Seating {
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Measurement;
    
    @EntryPoint()
    operation Main() : Int {
        // Prepare the input data
        let nGuests = 4;
        let enemies = [
            [0, 1],
            [2, 3]
        ];

        // Total number of qubits required to represent all guests/seats
        let nQubits = nGuests * NBitsPerGuest(nGuests);

        // The main qubit register represents the seating of all nGuests guests
        use (register, verificationQubit) = (Qubit[nQubits], Qubit());

        mutable foundAnswer = false;
        mutable nTry = 0;
        repeat {
            mutable estimatedSolutionsOrder = 0;
            repeat {
                // Run Grover search
                let nIterations = NIterations(nQubits, estimatedSolutionsOrder);
                RunGrover(register, nGuests, enemies, nIterations);

                // Measure the qubit register
                let results = MultiM(register);

                // Check if the result is a valid answer by simply applying
                // the marking oracle to the qubit register
                MarkingOracle(register, verificationQubit, nGuests, enemies);

                if (MResetZ(verificationQubit) == One) {
                    set foundAnswer = true;
                    let seating = ResultsAsIntArray(results, nGuests);

                    Message("Answer: " + IntArrayAsString(seating));
                }

                // Reset the qubits so they can be re-used
                ResetAll(register);

                set estimatedSolutionsOrder += 1;
            } until (foundAnswer or estimatedSolutionsOrder > nQubits);

            set nTry += 1;
		} until (foundAnswer or nTry > 10); // Try until success, but limit the number of tries to 10

        return 0;
    }

    operation RunGrover(inputQubits: Qubit[], nGuests: Int, enemies: Int[][], nIterations: Int) : Unit {
        ApplyToEachCA(H, inputQubits);

        for i in 1 .. nIterations {
            PhaseOracle(inputQubits, nGuests, enemies);
            GroverDiffusion(inputQubits);
        }
    }

    operation GroverDiffusion(inputQubits: Qubit[]) : Unit {
        // Grover's "diffusion" operator

        within {
            ApplyToEachCA(H, inputQubits);
            ApplyToEachCA(X, inputQubits);
        } apply {
            Controlled Z(Most(inputQubits), Tail(inputQubits));
        }
    }

    operation PhaseOracle(inputQubits : Qubit[], nGuests: Int, enemies: Int[][]) : Unit {
        // Phase oracle adds a negative phase to those states that
        // represent valid solutions

        use outputQubit = Qubit();

        within {
            X(outputQubit);
            H(outputQubit);
        } apply {
            MarkingOracle(inputQubits, outputQubit, nGuests, enemies);
        }
    }

    operation MarkingOracle(inputQubits: Qubit[], outputQubit: Qubit, nGuests: Int, enemies: Int[][]) : Unit {
        // Marking oracle flips the ancillary qubit
        // if the input contains a valid solution

        let nBitsPerGuest = NBitsPerGuest(nGuests);
        
        use enemyCheckQubits = Qubit[nGuests];
        use repeatedGuestsCheckQubits = Qubit[nGuests * (nGuests - 1) / 2];

        within {
            // Verify that the neighbouring guests aren't enemies
            for i in 0 .. nGuests - 1 {
                let j = (i + 1) % nGuests;

                VerifyNotEnemies(
                    inputQubits[i * nBitsPerGuest .. i * nBitsPerGuest + nBitsPerGuest - 1],
                    inputQubits[j * nBitsPerGuest .. j * nBitsPerGuest + nBitsPerGuest - 1],
                    enemyCheckQubits[i],
                    enemies
                );
            }

            // Verify that all guests are different
            for i in 0 .. nGuests - 2 {
                for j in i + 1 .. nGuests - 1 {
                    let ind = (nGuests * (nGuests - 1) / 2) - ((nGuests - i) * ((nGuests - i) - 1) / 2) + j - i - 1;

                    MarkIfNotEqual(
                        inputQubits[i * nBitsPerGuest .. i * nBitsPerGuest + nBitsPerGuest - 1],
                        inputQubits[j * nBitsPerGuest .. j * nBitsPerGuest + nBitsPerGuest - 1],
                        repeatedGuestsCheckQubits[ind]
                    );
                }
            }
	    }
        apply {
            Controlled X(enemyCheckQubits + repeatedGuestsCheckQubits, outputQubit);
        }
    }

    operation MarkIfNotEqual(guest1Qubits: Qubit[], guest2Qubits: Qubit[], outputQubit: Qubit) : Unit is Adj {
        // Flip the ancillary qubit if the two guests are different
        X(outputQubit);
        MarkIfEqual(guest1Qubits, guest2Qubits, outputQubit);
    }

    operation MarkIfEqual(guest1Qubits: Qubit[], guest2Qubits: Qubit[], outputQubit: Qubit) : Unit is Adj {
        // Flip the ancillary qubit if the two guests are the same
        within {
            for k in 0 .. Length(guest1Qubits) - 1 {
                X(guest2Qubits[k]);
                CNOT(guest1Qubits[k], guest2Qubits[k]);
            }
        } apply {
            Controlled X(guest2Qubits, outputQubit);
        }
    }

    operation VerifyNotEnemies(guest1Qubits: Qubit[], guest2Qubits: Qubit[], outputQubit: Qubit, enemies: Int[][]) : Unit is Adj {
        // Flip the ancillary qubit if the two guests are enemies

        use enemyCheck = Qubit[Length(enemies)];

        within {
            for pairInd in 0 .. Length(enemies) - 1 {
                let enemyPair = enemies[pairInd];

                use andQubits = Qubit[2];

                let enemy1Bits = IntAsBoolArray(enemyPair[0], Length(guest1Qubits));
                let enemy2Bits = IntAsBoolArray(enemyPair[1], Length(guest2Qubits));

                within {
                    MarkIfEnemies(guest1Qubits, guest2Qubits, enemy1Bits, enemy2Bits, andQubits[0]);
                    MarkIfEnemies(guest2Qubits, guest1Qubits, enemy1Bits, enemy2Bits, andQubits[1]);
			    }
                apply {
                    (ControlledOnInt(0, X))(andQubits, enemyCheck[pairInd]);
                }
			}
        }
        apply {
            Controlled X(enemyCheck, outputQubit);
        }
    }

    operation MarkIfEnemies(guest1Qubits: Qubit[], guest2Qubits: Qubit[], enemy1Bits: Bool[], enemy2Bits: Bool[], outputQubit: Qubit) : Unit is Adj {
        // Flip the ancillary qubit if the two guests are the same
        // as the two specified enemies

        within {
            for k in 0 .. Length(guest1Qubits) - 1 {
                if (not enemy1Bits[k]) {
                    X(guest1Qubits[k]);
				}
                if (not enemy2Bits[k]) {
                    X(guest2Qubits[k]);
				}
            }
        } apply {
            Controlled X(guest1Qubits + guest2Qubits, outputQubit);
        }
    }

    function NIterations(nQubits: Int, estimatedSolutionsOrder: Int) : Int {
        // Calculate the number of required Grover iterations
        // if the total number of items is N = 2 ^ nQubits
        // and the estimated number of solutions is k = 2 ^ estimatedSolutionsOrder
        let nItems = 1 <<< nQubits;
        let nEstimatedSolutions = 1 <<< estimatedSolutionsOrder;
        let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems) / IntAsDouble(nEstimatedSolutions)));
        let nIterations = Round(0.25 * PI() / angle - 0.5);
        return nIterations;
    }

    function NBitsPerGuest(nGuests: Int) : Int {
        // We use binary numbers from 0 to nGuests - 1 to represent each guest
        return BitSizeI(nGuests - 1);
    }

    function ResultsAsIntArray(results: Result[], nGuests: Int): Int[] {
        // Transform measured results into a list of guest numbers
        let bitsPerSeat = Length(results) / nGuests;
        mutable array = new Int[nGuests];
        for i in 0 .. bitsPerSeat .. Length(results) - 1 {
            set array w/= i / bitsPerSeat <- ResultArrayAsInt(results[i .. i + bitsPerSeat - 1]) + 1;
        }
        return array;
    }

    function IntArrayAsString(numbers: Int[]): String {
        // Transform a list of integers into a printable string
        mutable resultStr = "";
        for i in 0 .. Length(numbers) - 1 {
            if (i > 0) {
                set resultStr += " ";
            }
            set resultStr += IntAsString(numbers[i]);
        }
        return resultStr;
    }
}