Если живешь среди сумасшедших, надо и самому научиться быть безумным
Вы когда-нибудь пробовали «научиться быть безумным»? Нетривиальная задачка. Даже нормальной методики не найдешь, ибо каждый сходит с ума по-своему. Моя первая попытка: теория заговора. Теория не предполагает практики, а значит не придется много работать. Опять-таки, при любом раскладе никто не пострадает.
Квантовые вычисления — отличная область для такого исследования. Можно накатать простую схему, но слово «квантовые» придаст веса результатам.
Объект исследования — игра, ибо объект должен простым и привычным молодежи. Кто у нас занимается квантовыми вычислениями и играми? Google.
Итак, еретическая теория: через 5 лет Пейдж и Грин решат, кто будет главным в Google, и сделают это с помощью игры. У каждого из них есть группа исследователей. Команда AlphaGo со своими боевыми нейросетями натянула соперников в Го. Оппоненты вынуждены были искать новые методы, и таки обнаружили инструмент тотального превосходства: квантовые вычисления.
Можно ли использовать Квантовые Вычисления для игр? Легко. Покажем для примера, что игра «охотник на лис» может быть «решена» за 6 ходов. Ради правдоподобности ограничимся 15 кубитами (онлайн-редактор quirk больше пятнадцати не эмулирует), ради простоты проигнорируем ограничения архитектуры процессора и коррекцию ошибок.
Правила
Предельно просты. Есть пять нор, расположенных в ряд (нумеруем их как 0-1-2-3-4). В одной из них сидит лиса. Каждую ночь лиса перебирается в соседнюю норку слева или справа. Каждое утро охотник может проверить одну нору на выбор. Задача охотника — поймать лису. Задача лисы — выжить. В теории, лиса может бегать от охотника вечно. На практике, есть победная стратегия: проверять норы 1-2-3-1-2-3. Только эту стратегию я и буду проверять.
Строим схему
Начнем с инициации кубитов 0-1-2-3-4 (5 нор). Тут можно редактировать
По факту, после инициации у нас есть система, в которой после измерения строго один кубит будет единичным. Вероятности «единичности» различаются для каждого кубита, но в нашем случае это не критично. Надо же оставить пространство для обсуждения схемы (и нашей теории заодно).
На Q# мы получим код вроде такого:
operation TestStrategy () : (Result)
{
let res = Zero;
using(qubits=Qubit[16])
{
// 0..4 - holes
// 5 - current movement direction. Zero means "go down", One means "go up"
// 6 - Game status. 1 means "fox is free, go further"
// 7,8,9,10, 11 - movements history
InitFoxHoles(qubits);
ResetAll(qubits); // ALWAYS clean after yourself
}
return Zero;
}
// Inits fox holes, with almost equal probabilities
operation InitFoxHoles(register: Qubit[]) : Unit
{
body
{
ResetAll(register);
// Step 1
H(register[0]);
H(register[2]);
// Step 2
(Controlled (X))([register[0],register[2]], register[3]);
// Step 3
X(register[0]);
X(register[2]);
(Controlled (X))([register[0],register[2]], register[3]);
X(register[0]);
X(register[2]);
// Step 4
CNOT(register[3], register[0]);
CNOT(register[3], register[2]);
// Step 5
(Controlled (H))([register[3]], register[4]);
// Step 6
CNOT(register[4], register[3]);
}
}TestStrategy будет проверять нашу стратегию 1-2-3-1-2-3, InitFoxHoles() отвечает только за инициацию лисьих нор. Давайте проверим инициацию. Скопипастим TestStrategy, запустим инициацию, измерим первые 5 кубитов и вернем их значения.
operation TestInit(): (Result, Result, Result, Result, Result)
{
body
{
mutable res0 = Zero;
mutable res1 = Zero;
mutable res2 = Zero;
mutable res3 = Zero;
mutable res4 = Zero;
using(qubits=Qubit[16])
{
// 0..4 - holes
// 5 - current movement direction. Zero means "go down", One means "go up"
// 6 - Game status. 1 means "fox is free, go further"
// 7,8,9,10, 11 - movements history
InitFoxHoles(qubits);
set res0 = M(qubits[0]);
set res1 = M(qubits[1]);
set res2 = M(qubits[2]);
set res3 = M(qubits[3]);
set res4 = M(qubits[4]);
ResetAll(qubits); // ALWAYS clean after yourself
}
return (res0, res1, res2, res3, res4);
}
}Тест прогоним тысячу раз (многократный прогон типичен для квантовых алгоритмов, кое-где даже необходим). Код вызова — под спойлером, результаты: на скрине ниже.
static void TestInitiation()
{
using (var sim = new QuantumSimulator())
{
var initedQubitsValues = Enumerable.Range(0, 5)
.ToDictionary(qubitIndex => qubitIndex, oneMesaured => 0);
for (int i = 0; i < 1000; i++)
{
(Result, Result, Result, Result, Result) result = TestInit.Run(sim).Result;
if (result.Item1 == Result.One) { initedQubitsValues[0]++; }
if (result.Item2 == Result.One) { initedQubitsValues[1]++; }
if (result.Item3 == Result.One) { initedQubitsValues[2]++; }
if (result.Item4 == Result.One) { initedQubitsValues[3]++; }
if (result.Item5 == Result.One) { initedQubitsValues[4]++; }
}
Console.WriteLine($"Qubit-0 initiations: {initedQubitsValues[0]}");
Console.WriteLine($"Qubit-1 initiations: {initedQubitsValues[1]}");
Console.WriteLine($"Qubit-2 initiations: {initedQubitsValues[2]}");
Console.WriteLine($"Qubit-3 initiations: {initedQubitsValues[3]}");
Console.WriteLine($"Qubit-4 initiations: {initedQubitsValues[4]}");
}
}
Что-то пошло не так. Ожидалось почти-равномерное распределение. Причина проста: на шаге 3 я заинвертил третий кубит, вместо первого: (Controlled (X))([register[0],register[2]], register[3]); старый недобрый копипаст.
Исправляем код, запускаем тест:
// Inits fox holes, with almost equal probabilities
operation InitFoxHoles(register: Qubit[]) : Unit
{
body
{
ResetAll(register);
// Step 1
H(register[0]);
H(register[2]);
// Step 2
(Controlled (X))([register[0],register[2]], register[3]);
// Step 3
X(register[0]);
X(register[2]);
(Controlled (X))([register[0],register[2]], register[1]);
X(register[0]);
X(register[2]);
// Step 4
CNOT(register[3], register[0]);
CNOT(register[3], register[2]);
// Step 5
(Controlled (H))([register[3]], register[4]);
// Step 6
CNOT(register[4], register[3]);
}
}
}
Уже лучше. Код можно посмотреть в репе, версия Commit 1.
Куда бежать лисе?
Выделим пятый кубит (нумерация стартует сверху) под текущее направление перемещения лисы. Договоримся, что ноль означает движение «вниз», единица — «вверх». Очевидно, если лиса уже в нулевой норе — она должна двигаться вниз. Если лиса в четвертой норе — она двигается вверх. В остальных случаях лиса может двигаться и вниз, и вверх. По этим нехитрым правилам можно устанавливаем «кубит текущего направления» в 0, 1, или суперпозицию нуля и единицы. Код смотрим в репозитории, Commit 2.
// Select next Fox movement direction, updating qubit 5
// 1 means go up (4 -> 3, 3 -> 2, ... 1 -> 0)
// 0 means go down (0 -> 1, 1 -> 2, ... 3 -> 4)
operation SetupMovementDirection(qubits: Qubit[]) : Unit
{
body
{
// Step 1
CNOT(qubits[4], qubits[5]);
// Step 2
(Controlled (H))([qubits[3]], qubits[5]);
// Step 3
(Controlled (H))([qubits[2]], qubits[5]);
// Step 4
(Controlled (H))([qubits[1]], qubits[5]);
}
}
operation TestMovementDirectionSetup(): (Result, Result, Result, Result, Result, Result)
{
body
{
mutable res0 = Zero;
mutable res1 = Zero;
mutable res2 = Zero;
mutable res3 = Zero;
mutable res4 = Zero;
mutable res5 = Zero;
using(qubits=Qubit[16])
{
InitFoxHoles(qubits);
SetupMovementDirection(qubits);
set res0 = M(qubits[0]);
set res1 = M(qubits[1]);
set res2 = M(qubits[2]);
set res3 = M(qubits[3]);
set res4 = M(qubits[4]);
set res5 = M(qubits[5]);
ResetAll(qubits); // ALWAYS clean after yourself
}
return (res0, res1, res2, res3, res4, res5);
}
} static void TestMovementDirectionSetup()
{
using (var sim = new QuantumSimulator())
{
List<string> results = new List<string>();
string initedCubit = null;
string moveDirection = null;
for (int i = 0; i < 1000; i++)
{
(Result, Result, Result, Result, Result, Result) result = Quantum.FoxHunter.TestMovementDirectionSetup.Run(sim).Result;
if (result.Item1 == Result.One) { initedCubit = "0"; }
if (result.Item2 == Result.One) { initedCubit = "1"; }
if (result.Item3 == Result.One) { initedCubit = "2"; }
if (result.Item4 == Result.One) { initedCubit = "3"; }
if (result.Item5 == Result.One) { initedCubit = "4"; }
if (result.Item6 == Result.One) { moveDirection = "1"; }
else { moveDirection = "0"; }
results.Add($"{initedCubit}{moveDirection}");
}
foreach(var group in results
.GroupBy(result => result)
.OrderBy(group => group.Key))
{
Console.WriteLine($"{group.Key} was measured {group.Count()} times");
}
Console.WriteLine($"rnTotal measures: {results.Count()}");
}
}
Движение
Реализуется контролируемым SWAP. Если контролирующий кубит единичен — свапаемся вниз. Если контролирующий кубит занулён — свапаемся вверх.
// Makes a movement based on the 5'th qubit value
// 1 means go up (4 -> 3, 3 -> 2, ... 1 -> 0)
// 0 means go down (0 -> 1, 1 -> 2, ... 3 -> 4)
operation MakeMovement(qubits: Qubit[]) : Unit
{
body
{
// Code movement Up
// Step 1
mutable qubitsToSwap = [qubits[0], qubits[1]];
(Controlled(SwapReverseRegister))([qubits[5]],qubitsToSwap);
// Step 2
set qubitsToSwap = [qubits[1], qubits[2]];
(Controlled(SwapReverseRegister))([qubits[5]],qubitsToSwap);
// Step 3
set qubitsToSwap = [qubits[2], qubits[3]];
(Controlled(SwapReverseRegister))([qubits[5]],qubitsToSwap);
// Step 4
set qubitsToSwap = [qubits[3], qubits[4]];
(Controlled(SwapReverseRegister))([qubits[5]],qubitsToSwap);
// COde movement down
X(qubits[5]); // Invert direction qubit for the ZeroControlled operations
// Step 5
set qubitsToSwap = [qubits[3], qubits[4]];
(Controlled(SwapReverseRegister))([qubits[5]],qubitsToSwap);
// Step 6
set qubitsToSwap = [qubits[2], qubits[3]];
(Controlled(SwapReverseRegister))([qubits[5]],qubitsToSwap);
// Step 7
set qubitsToSwap = [qubits[1], qubits[2]];
(Controlled(SwapReverseRegister))([qubits[5]],qubitsToSwap);
// Step 8
set qubitsToSwap = [qubits[0], qubits[1]];
(Controlled(SwapReverseRegister))([qubits[5]],qubitsToSwap);
X(qubits[5]); // Back-invert for the direction qubit
}
}
operation TestFirstMovement(): (Result, Result, Result, Result, Result, Result)
{
body
{
mutable res0 = Zero;
mutable res1 = Zero;
mutable res2 = Zero;
mutable res3 = Zero;
mutable res4 = Zero;
mutable res5 = Zero;
using(qubits=Qubit[16])
{
InitFoxHoles(qubits);
SetupMovementDirection(qubits);
MakeMovement(qubits);
set res0 = M(qubits[0]);
set res1 = M(qubits[1]);
set res2 = M(qubits[2]);
set res3 = M(qubits[3]);
set res4 = M(qubits[4]);
set res5 = M(qubits[5]);
ResetAll(qubits); // ALWAYS clean after yourself
}
return (res0, res1, res2, res3, res4, res5);
}
}
static void TestFirstMove()
{
using (var sim = new QuantumSimulator())
{
List<string> results = new List<string>();
string initedCubit = null;
string moveDirection = null;
for (int i = 0; i < 1000; i++)
{
(Result, Result, Result, Result, Result, Result) result = Quantum.FoxHunter.TestFirstMovement.Run(sim).Result;
if (result.Item1 == Result.One) { initedCubit = "0"; }
if (result.Item2 == Result.One) { initedCubit = "1"; }
if (result.Item3 == Result.One) { initedCubit = "2"; }
if (result.Item4 == Result.One) { initedCubit = "3"; }
if (result.Item5 == Result.One) { initedCubit = "4"; }
if (result.Item6 == Result.One) { moveDirection = "1"; }
else { moveDirection = "0"; }
results.Add($"{initedCubit}{moveDirection}");
}
// Holes measurements
foreach (var group in results
.GroupBy(result => result[0])
.OrderBy(group => group.Key))
{
Console.WriteLine($"{group.Key} hole was measured {group.Count()} times");
}
// Directions measuremetns
foreach (var group in results
.GroupBy(result => result[1])
.OrderBy(group => group.Key))
{
Console.WriteLine($"{group.Key} direction was measured {group.Count()} times");
}
Console.WriteLine($"rnTotal measures: {results.Count()}");
}
}
Код можно посмотреть в Commit 3.
Делаем 6 ходов
Наконец, выделяем шестой кубит под статус игры (лиса свободна/лиса не свободна). Единица соответсвует свободной лисе. Будем делать дальнейшие ходы только при единичном кубите статуса.
Кубиты 7,8,9,10,11 будут хранить историю ходов. После каждого хода мы бдуем свапать один из них с кубитом текущего направления (это позволит хранить историю ходов и обнулять кубит текущего направления перед каждым ходом).
Схема прилагается.
/// Make 6 movements. Every movement is controlled by the 6'th qubit.
/// After the every qubit we check if the fox has been captured and invert the 6'th qubit
/// Reminder: 6'th qubit equal to One means "Fox is free, go further"
operation MakeSixMovements(qubits: Qubit[]) : Unit
{
body
{
// Move 1
(Controlled(SetupMovementDirection))([qubits[6]],(qubits));
(Controlled(MakeMovement))([qubits[6]],(qubits));
CNOT(qubits[1], qubits[6]); // Reverse Fox State if it's shot
// Move 2
SwapReverseRegister([qubits[5], qubits[7]]); // Move the first move direction to the qubit 7, qubit 5 is Zero again
(Controlled(SetupMovementDirection))([qubits[6]],(qubits));
(Controlled(MakeMovement))([qubits[6]],(qubits));
CNOT(qubits[2], qubits[6]);
// Move 3
SwapReverseRegister([qubits[5], qubits[8]]);
(Controlled(SetupMovementDirection))([qubits[6]],(qubits));
(Controlled(MakeMovement))([qubits[6]],(qubits));
CNOT(qubits[3], qubits[6]);
// Move 4
SwapReverseRegister([qubits[5], qubits[9]]);
(Controlled(SetupMovementDirection))([qubits[6]],(qubits));
(Controlled(MakeMovement))([qubits[6]],(qubits));
CNOT(qubits[1], qubits[6]);
// Move 5
SwapReverseRegister([qubits[5], qubits[10]]);
(Controlled(SetupMovementDirection))([qubits[6]],(qubits));
(Controlled(MakeMovement))([qubits[6]],(qubits));
CNOT(qubits[2], qubits[6]);
// Move 6
SwapReverseRegister([qubits[5], qubits[11]]);
(Controlled(SetupMovementDirection))([qubits[6]],(qubits));
(Controlled(MakeMovement))([qubits[6]],(qubits));
CNOT(qubits[3], qubits[6]);
}
}
operation TestSixMovements(): (Result)
{
body
{
mutable res = Zero;
using(qubits=Qubit[16])
{
ResetAll(qubits);
InitFoxHoles(qubits);
X(qubits[6]); // At the beginning of the game our fox is alive
MakeSixMovements(qubits);
set res = M(qubits[6]);
ResetAll(qubits); // ALWAYS clean after yourself
}
return (res);
}
}
static void TestMovements()
{
using (var sim = new QuantumSimulator())
{
int zerosCount = 0;
for (int i = 0; i < 1000; i++)
{
Result result = Quantum.FoxHunter.TestSixMovements.Run(sim).Result;
if(result == Result.Zero) { zerosCount++; }
}
Console.WriteLine($"rnTotal zeroes: {zerosCount}");
}
}
Смотрим Commit 4.
Последние штрихи
У нас в схеме есть ошибка. Поскольку мы проверяем стратегию 1-2-3-1-2-3, каждую нору мы проверяем дважды. Соответственно, поймав лису первым же ходом, мы пройдемся по кубиту статуса дважды (на первом ходу и четвертом).
Чтобы избежать такой ситуации, мы используем 12 кубит для фиксации статуса после ходов 4-5-6. Кроме того, добавим определение победы: если хотя бы один из статусных кубитов обращается в ноль — мы победили.
Итоговая схема.
operation MakeSixMovements(qubits: Qubit[]) : Unit
{
body
{
// Move 1
(Controlled(SetupMovementDirection))([qubits[6]],(qubits));
(Controlled(MakeMovement))([qubits[6]],(qubits));
CNOT(qubits[1], qubits[6]); // Reverse Fox State if it's shot
// Move 2
SwapReverseRegister([qubits[5], qubits[7]]); // Move the first move direction to the qubit 7, qubit 5 is Zero again
(Controlled(SetupMovementDirection))([qubits[6]],(qubits));
(Controlled(MakeMovement))([qubits[6]],(qubits));
CNOT(qubits[2], qubits[6]);
// Move 3
SwapReverseRegister([qubits[5], qubits[8]]);
(Controlled(SetupMovementDirection))([qubits[6]],(qubits));
(Controlled(MakeMovement))([qubits[6]],(qubits));
CNOT(qubits[3], qubits[6]);
// Move 4
SwapReverseRegister([qubits[5], qubits[9]]);
(Controlled(SetupMovementDirection))([qubits[6], qubits[12]],(qubits));
(Controlled(MakeMovement))([qubits[6], qubits[12]],(qubits));
CNOT(qubits[1], qubits[12]);
// Move 5
SwapReverseRegister([qubits[5], qubits[10]]);
(Controlled(SetupMovementDirection))([qubits[6], qubits[12]],(qubits));
(Controlled(MakeMovement))([qubits[6], qubits[12]],(qubits));
CNOT(qubits[2], qubits[12]);
// Move 6
SwapReverseRegister([qubits[5], qubits[11]]);
(Controlled(SetupMovementDirection))([qubits[6], qubits[12]],(qubits));
(Controlled(MakeMovement))([qubits[6], qubits[12]],(qubits));
CNOT(qubits[3], qubits[12]);
}
}
operation TestStrategy () : (Result)
{
// 0..4 - holes
// 5 - current movement direction. Zero means "go down", One means "go up"
// 6 - Game status. 1 means "fox is free, go further"
// 7,8,9,10, 11 - movements history
// 12 - another qubit of the fox live. 1 means "fox is still free, go further"
// 13 Result qubit. If it's zero, the fox is alive
body
{
mutable res = Zero;
using(qubits=Qubit[14])
{
ResetAll(qubits);
// Init fox positions and the fox' live
InitFoxHoles(qubits);
X(qubits[6]); // At the beginning of the game our fox is alive
X(qubits[12]); // The second qubit of the fox live. If it's one - the fox is alive.
// Make moves
MakeSixMovements(qubits);
// Measure results. If the 13'th qubit is zero the fox is alive
X(qubits[6]);
X(qubits[12]);
CNOT(qubits[6], qubits[13]);
CNOT(qubits[12], qubits[13]);
CCNOT(qubits[6], qubits[12], qubits[13]);
set res = M(qubits[13]);
ResetAll(qubits); // ALWAYS clean after yourself
}
return (res);
}
}
static void RunFoxHunt()
{
Stopwatch sw = new Stopwatch();
sw.Start();
using (var sim = new QuantumSimulator())
{
var foxSurvives = 0;
var hunterWins = 0;
for (int i = 0; i < 1000; i++)
{
var result = (Result)(TestStrategy.Run(sim).Result);
if (result == Result.Zero) { foxSurvives++; }
else { hunterWins++; }
}
Console.WriteLine($"Fox survives: t{foxSurvives}");
Console.WriteLine($"Hunter wins: t{hunterWins}");
}
sw.Stop();
Console.WriteLine($"Experiment finished. " +
$"Time spent: {sw.ElapsedMilliseconds / 1000} seconds");
}
Что из этого следует
В принципе, схему можно оптимизировать, как по числу кубитов, так и по числу операций. Тривиальная оптимизация по числу кубитов — избавиться от кубита-13, возвращая только 6 и 12. Оптимизация по операциям — делать первый выстрел сразу после инициации. Однако, оставим эту работу инженерам Google.
Как видно, любой человек, поверхностно знакомый с квантовыми вычислениями, может спокойно играть в «охотника на лис». Будь у нас чуть больше кубитов — можно было бы найти оптимальное решение, а не проверять существующее. Вполне возможно, следующими падут крестики-нолики (и их квантовая версия), шашки, шахматы, Го.
При этом, вопрос «решаемости» игр вроде DotA, Starcraft и Doom остается открыт. Для квантовых вычислений характерно хранение всей истории нажатий. Берем APM (Actions Per Minute) в 500, умножаем на количество игроков, умножаем на количество минут, добавляем рандом самой игры — количество кубитов требуемых для хранения всей информации растет слишком быстро.
Так что, выбор игры в маленьком соревновании Брина и Пейджа может сыграть решающее значение. Впрочем, генерация игры «одинаковой сложной» для классического и квантового компьютеров заслуживает собственной теории.
Автор: Oxoron
