Pull to refresh

Квантовые вычисления в играх, или сходим с ума по-серьезному

Reading time 12 min
Views 7.7K
Если живешь среди сумасшедших, надо и самому научиться быть безумным

Вы когда-нибудь пробовали «научиться быть безумным»? Нетривиальная задачка. Даже нормальной методики не найдешь, ибо каждый сходит с ума по-своему. Моя первая попытка: теория заговора. Теория не предполагает практики, а значит не придется много работать. Опять-таки, при любом раскладе никто не пострадает.

Как создавать теории заговора?
Создать теорию заговора относительно просто. Нужна идея, достаточно простая для того, чтобы её восприняли 90% населения. Она должна быть спорна, чтобы 5% населения могли объяснять 90% какие они идиоты. Наконец, нужны какие-либо исследования, которые эти 95% людей не понимают, но которые используются 90% как аргумент «люди поумнее нас доказали...».

Квантовые вычисления — отличная область для такого исследования. Можно накатать простую схему, но слово «квантовые» придаст веса результатам.

Объект исследования — игра, ибо объект должен простым и привычным молодежи. Кто у нас занимается квантовыми вычислениями и играми? 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($"\r\nTotal measures: {results.Count()}");                                  
            }
        }





Движение

Реализуется контролируемым SWAP. Если контролирующий кубит единичен — свапаемся вниз. Если контролирующий кубит занулён — свапаемся вверх.


Схема в редакторе.

Q# оператор
    // 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
        }  
    }


Q#: оператор для тестов
    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);        
        }         
    }


C# код
        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($"\r\nTotal measures: {results.Count()}");
            }

        }


Код можно посмотреть в Commit 3.

Делаем 6 ходов


Наконец, выделяем шестой кубит под статус игры (лиса свободна/лиса не свободна). Единица соответсвует свободной лисе. Будем делать дальнейшие ходы только при единичном кубите статуса.

Кубиты 7,8,9,10,11 будут хранить историю ходов. После каждого хода мы бдуем свапать один из них с кубитом текущего направления (это позволит хранить историю ходов и обнулять кубит текущего направления перед каждым ходом).

Схема прилагается.

Q# оператор
    /// 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]);                                           
        }        
    }


Q# : оператор для тестов
    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);              
        }
    }


C# : тестируем
        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($"\r\nTotal zeroes: {zerosCount}");
            }
        }


Смотрим Commit 4.

Последние штрихи


У нас в схеме есть ошибка. Поскольку мы проверяем стратегию 1-2-3-1-2-3, каждую нору мы проверяем дважды. Соответственно, поймав лису первым же ходом, мы пройдемся по кубиту статуса дважды (на первом ходу и четвертом).

Чтобы избежать такой ситуации, мы используем 12 кубит для фиксации статуса после ходов 4-5-6. Кроме того, добавим определение победы: если хотя бы один из статусных кубитов обращается в ноль — мы победили.

Итоговая схема.

Q# : фиксим оператор 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]);                                           
        }        
    }


Q# : фиксим оператор, тестирующий стратегию 1-2-3-1-2-3
    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);
        }
    }


C# : запускаем финальную проверку
        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");            
        }



Commit 5.

Что из этого следует


В принципе, схему можно оптимизировать, как по числу кубитов, так и по числу операций. Тривиальная оптимизация по числу кубитов — избавиться от кубита-13, возвращая только 6 и 12. Оптимизация по операциям — делать первый выстрел сразу после инициации. Однако, оставим эту работу инженерам Google.

Как видно, любой человек, поверхностно знакомый с квантовыми вычислениями, может спокойно играть в «охотника на лис». Будь у нас чуть больше кубитов — можно было бы найти оптимальное решение, а не проверять существующее. Вполне возможно, следующими падут крестики-нолики (и их квантовая версия), шашки, шахматы, Го.

При этом, вопрос «решаемости» игр вроде DotA, Starcraft и Doom остается открыт. Для квантовых вычислений характерно хранение всей истории нажатий. Берем APM (Actions Per Minute) в 500, умножаем на количество игроков, умножаем на количество минут, добавляем рандом самой игры — количество кубитов требуемых для хранения всей информации растет слишком быстро.

Так что, выбор игры в маленьком соревновании Брина и Пейджа может сыграть решающее значение. Впрочем, генерация игры «одинаковой сложной» для классического и квантового компьютеров заслуживает собственной теории.
Tags:
Hubs:
+15
Comments 12
Comments Comments 12

Articles