Skip to content

Instantly share code, notes, and snippets.

@KirillNikonov
Created Jun 2, 2021
Embed
What would you like to do?
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment