Como eu implementaria o oráculo quântico no algoritmo de Deutsch?

Estou tentando simular o algoritmo de Deutsch (caso elementar do algoritmo Deutsch-Josza) e não tenho muita certeza de como implementaria o oráculo quântico necessário para o algoritmo funcionar, sem derrotar o objetivo do algoritmo e "olhar" qual é a função inserida, avaliando a função.

Há duas perguntas aqui. O primeiro pergunta como você realmente pode implementá-lo no código, e o segundo pergunta qual é o sentido se você souber em qual oráculo está passando.

Implementação

Provavelmente, a melhor maneira é criar uma função IsBlackBoxConstantque tome o oráculo como entrada e, em seguida, execute o programa Deutsch Oracle para determinar se é constante. Você pode selecionar o oráculo aleatoriamente, se quiser. Aqui está, implementado em Q #:

operation IsBlackBoxConstant(blackBox: ((Qubit, Qubit) => ())) : (Bool)
{
    body
    {
        mutable inputResult = Zero;
        mutable outputResult = Zero;

        // Allocate two qbits
        using (qbits = Qubit[2])
        {
            // Label qbits as inputs and outputs
            let input = qbits[0];
            let output = qbits[1];

            // Pre-processing
            X(input);
            X(output);
            H(input);
            H(output);

            // Send qbits into black box
            blackBox(input, output);

            // Post-processing
            H(input);
            H(output);

            // Measure both qbits
            set inputResult = M(input);
            set outputResult = M(output);

            // Clear qbits before release
            ResetAll(qbits);
        }

        // If input qbit is 1, then black box is constant; if 0, is variable
        return One == inputResult;
    }
}

Qual é o objetivo?

Complexidade da consulta

A complexidade computacional é um campo relacionado à classificação de algoritmos de acordo com a quantidade de recursos que eles consomem em função do tamanho da entrada. Esses recursos incluem tempo (medido em etapas / instruções), memória e também algo chamado complexidade da consulta . A complexidade da consulta está relacionada ao número de vezes que um algoritmo precisa consultar uma função oracle de caixa preta.

O problema do oráculo da Deutsch é interessante para os teóricos da complexidade, porque o algoritmo quântico só precisa consultar a caixa preta uma vez, mas o algoritmo clássico precisa consultá-la duas vezes. Com o problema generalizado de Deutsch-Josza, em que um oráculo de $n$ bits contém uma função constante ou balanceada, o algoritmo quântico novamente só precisa consultá-lo uma vez, mas o algoritmo clássico (determinístico) requer $2^{n-1}$ consultas n - 1 .

Deve-se notar que existe um algoritmo probabilístico clássico que resolve o problema de Deutsch-Josza em muito menos do que $2^{n-1}$ consultas por amostragem aleatória de entradas do oráculo: se o oráculo continuar produzindo o mesmo valor, independentemente da entrada, a probabilidade de que o oracle é constante cresce muito rapidamente. Isso significa que Deutsch-Josza não é um bom candidato a um problema quântico de supremacia / vantagem, o que leva a ...

Aplicações no mundo real

Se você não é um teórico da complexidade, pode razoavelmente não se importar muito com a complexidade das consultas e, em vez disso, deseja saber por que o problema do oráculo da Deutsch é importante em um mundo "sem regras", onde você pode olhar dentro da caixa preta. Tentar analisar um problema do oráculo como um problema que não é do oráculo é repleto de dificuldades, e não acredito que alguém tenha resolvido a questão do melhor algoritmo clássico para o problema do oráculo da Deutsch quando você tem permissão para analisar o circuito do oráculo. Você pode pensar - o que há para analisar? Existem apenas quatro circuitos possíveis! De fato, é muito mais complicado.

Se observarmos a representação mais simples do Deutsch Oracle de um bit, a construção do portão é a seguinte:

Identidade: $C_{1,0}$

Negação: $X_0C_{1,0}$

Constante-0: $\mathbb{I}_4$

Constante-1: $X_0$

No entanto, essas não são de forma alguma a única maneira de implementar os oráculos. Tudo isso pode ser reescrito usando centenas, milhares e até milhões de portas lógicas! Tudo o que importa é o efeito cumulativo desses portões lógicos é equivalente à construção simples acima. Considere a seguinte implementação alternativa da Constant-1:

$H_0Z_0H_0$

Acontece que, para qualquer entrada que você possa dar:

$H_0Z_0H_0|\psi\rangle = X_0|\psi\rangle$

Isto é devido à associatividade da multiplicação de matrizes. Se você escrever as matrizes reais para $H_0Z_0H_0$ e multiplicá-las, obtém $X_0$ :

$H_0Z_0H_0 = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = X_0$

Então nós temos:

$(H_0(Z_0(H_0|\psi\rangle))) = (((H_0Z_0)H_0)|\psi\rangle) = X_0|\psi\rangle$

$H_0Z_0H_0$$X_0$

Importante por razões históricas e pedagógicas

Principalmente, o problema da Deutsch Oracle é importante por razões históricas e pedagógicas. É o primeiro algoritmo ensinado aos alunos porque é o mais simples e parece demonstrar a aceleração quântica, desde que você não faça muitas perguntas. Também serve como um bom ponto de partida para aprender o Problema da Periodicidade de Simon e, em seguida, o Algoritmo de Shor.

Não há como construir o oráculo de uma maneira que não derrote o ponto do algoritmo de Deutsch - é por isso que é um algoritmo baseado em oráculo.

$x$$f(x)$$f(0)=f(1)$

$f(x)$$1 \leq x \leq N$$f(x)$$y$$f(x+y)=f(x)$$f(x)$

Portanto, o ponto é que os algoritmos baseados em oracle provam que você pode acelerar se tiver um problema com essa estrutura (ou seja, onde você deseja apenas aprender alguma propriedade específica de uma função), mas não informa se existe esse problema.

Portanto, se você deseja implementar o Deutsch, qualquer maneira de fazer o oráculo é boa - é um algoritmo de "prova de princípio" e não produz uma aceleração real de um problema real (pelo menos, nenhum que conhecemos).

Você tem dois exemplos na página IBM Q Experience sobre o algoritmo . Eles mostram um exemplo de uma função. Isso poderia inspirá-lo para suas simulações, espero.

Não tenho um exemplo útil para o algoritmo de Deutsch, mas aqui e aqui estão dois tutoriais que explicam a implementação do algoritmo Deutsch-Jozsa e dos oráculos que ele usa no Q #.

A idéia para esses dois algoritmos é a mesma: você precisa fornecer o oráculo para o algoritmo como uma operação implementada em outro lugar. Dessa maneira, o algoritmo não sabe qual oráculo é dado e não tem como "olhar" para o oráculo, exceto por chamá-lo. Esses tutoriais também possuem um chicote que conta quantas vezes o oráculo é chamado, para que, se sua solução o chamar mais de uma vez, ele falhará no teste.

É certo que isso ainda tem um problema que os algoritmos do oracle costumam ter: um humano pode observar a implementação do teste e do oráculo aprovado e descobrir a resposta descobrindo qual oracle é implementado. Isso pode ser combatido aleatoriamente a escolha do oráculo, como sugeriu DaftWullie.

Eu acho que essa ahelwerresposta toca em algumas das maneiras que pensamos sobre a complexidade dos algoritmos. No entanto - como não temos literalmente "oráculos" no mundo real que desejamos consultar, você pode se perguntar por que nos preocuparíamos com a complexidade das consultas ou com a idéia de oráculos. Vou tentar dar uma perspectiva sobre isso e, em particular, descrever como você pode tentar pensar em maneiras de construir um "oráculo Deutsch-Josza" de uma maneira que você não sinta que está trapaceando.

(Como Norbert Schuchaponta, para o problema da Deutsch, que é o caso elementar da Deutsch-Josza, não há muito espaço para insights, mas espero que sua pergunta sobre oráculos se aplique de maneira mais geral também. É com isso que vou falar aqui.)

Uma intuição sobre oráculos

O conceito de um oráculo é uma maneira de nos permitir simplificar a maneira como falamos sobre problemas computacionais.

A aplicação original do conceito de um oráculo era considerar hipoteticamente o que poderíamos fazer se pudéssemos resolver problemas difíceis, mesmo impossíveis, sem nos comprometermos com o modo de fazê-lo, mesmo em princípio. Mas na complexidade computacional atualmente - particularmente na computação quântica, por exemplo ,  nos casos de Deutsch – Josza, Bernstein – Vazirani e outros problemas do oráculo - a situação é diferente: o oráculo descreve uma função que é a base do problema. O fato de ser 'um oráculo' é uma maneira de estruturar como descrevemos a função que está no centro do problema: não que nunca devamos contemplar como a função é computada, mas que essas informações simplesmente não são fornecidas como parte do problema e que não estamos preocupados com o tempo ou outra complexidade associada a essa função.

Quando adotamos essa abordagem, podemos realmente obter respostas relacionadas a perguntas muito difíceis na computação. Por exemplo, você pode saber que não sabemos como provar quer P  ≠  NP ou P  =  NP , mas que pode mostrar que existem oráculos A tais que podemos mostrar que P ^A  ≠  NP ^A . O que o oráculo A faz aqui não ajuda um computador (mais precisamente, uma máquina de Turing determinística ou uma máquina de Turing não determinística) a resolver um problema - ele representa o problema que o computador deve resolver. O fato de podermos mostrar em alguns casos que P ^A ≠  NP ^A , não significa que P é realmente diferente de NP : Significa apenas que apenas usando não-determinismo é realmente um recurso significativo para um modelo de computação para ter - ele permite que você para resolver alguns problemas de forma eficiente, e não há nenhuma maneira genericamente para simular o não-determinismo de forma eficiente em um computador determinístico. Então, se você quiser resolver o problema relacionado com o que A calcula, é absolutamente exigiria algumas informações sobre a estrutura de qualquer função que poderia eficientemente computação A .

Essa é uma das principais coisas que os oráculos tratam: eles permitem que você fale sobre maneiras pelas quais os modelos de computação podem ou não resolver problemas, quando você recebe informações limitadas sobre o problema.

Usando algoritmos oracle para resolver problemas não oracle

O algoritmo Deutsch-Josza, ou o algoritmo Bernstein-Vazirani, não são, em princípio, algoritmos executados por eles mesmos. (Bem, na verdade não - consulte a próxima seção.) Eles representam maneiras pelas quais você pode resolver um problema . Que problemas eles resolvem? Eles permitem descobrir certos recursos de uma função na qual você está interessado - seja constante / equilibrada ou qual vetor está associado a alguma função linear com valor escalar em vetores.

Em quais funções você as executa? - Você as executa em qualquer função pela qual esteja interessado na resposta.

A descrição deles como algoritmos baseados em oráculo não vem ao caso. Os problemas do oracle basicamente permitem que você saiba que, com um computador quântico ideal, você pode resolver o problema mesmo que saiba muito pouco sobre a função , desde que possa realmente avaliar a função com eficiência na prática. Para realmente avaliar essa função, é claro que você precisará de uma descrição de como fazê-lo, e assim terá mais informações do que na configuração do oracle; mas isso não impede que você use o mesmo algoritmo.

O que acontece quando você tem mais informações do que na configuração do oráculo, é que, de repente, existem outras maneiras de solucionar o problema. Especificamente, pode ser possível resolver o problema de maneira eficiente e classicamente . (Esta é a mesma observação de P ^A  ≠  NP ^A : prova que existem problemas em NP , que qualquer algoritmo determinístico eficiente exigiria pelo menos informações estruturais reais para poder resolver - de modo que, quando você fornece uma descrição de uma função eficientemente computável em vez de um 'oráculo', é possível que o problema estejaP. ) Isso significa que o algoritmo quântico pode não ter a mesma vantagem sobre os algoritmos clássicos na solução do problema específico que você apresenta - e, de fato, pode ser que a abordagem clássica seja melhor (principalmente com os dispositivos que temos no momento).

No final, apenas porque você tem um algoritmo quântico para resolver algo, não significa que seja necessariamente a melhor maneira de resolver algo. Isso certamente se aplica ao algoritmo Deutsch – Josza: mesmo no cenário do oráculo, o uso da aleatoriedade é quase tão bom quanto é melhor, já que ainda não temos grandes computadores quânticos confiáveis! Mas, novamente ...

"Implementando" um oráculo

O objetivo de implementar o algoritmo Deutsch – Josza é o mesmo que implementar " Olá, Mundo! " - não para resolver um problema premente não resolvido, mas para praticar o uso de uma ferramenta que você espera que seja útil para fazer outras coisas.

Para praticar a codificação, você deve se sentir absolutamente relaxado e confortável com a idéia de implementar um oráculo e com a idéia do computador que está avaliando o oráculo. Em princípio, este é o ponto do que você deseja fazer. Mesmo se você estiver usando um emulador clássico, no qual o computador clássico está realmente avaliando todos os ramos da superposição e encontrando explicitamente a resposta para um problema, a fim de fingir que é um computador quântico agindo de maneira um pouco mais indireta, então esteja praticando como usar uma ferramenta que pode ser útil para outras coisas e que um dia não será executada em um computador clássico.

Então, como você deve implementar seu oráculo?

(i) Se você está realmente comprometido com a ideia de que está apenas praticando, não precisa fingir que está fazendo algo mágico. Crie qualquer maneira de implementar a função oracle, mesmo que seja óbvio para o observador casual se o resultado é constante ou equilibrado. Você está apenas tentando praticar a realização de um algoritmo - não se preocupe que alguém o acuse de ser um impostor, que você esteja fingindo curar o câncer, mas que esteja brincando com o Lego. Você nunca foram fingindo para curar o câncer, e você está jogando com Lego por escolha deliberada. Aceite isso e apenas faça-o.

$f(x) = g(x,r)$$r$$g(x,r)$$x$$r$, e onde não é óbvio como resolvê-lo classicamente, não é trivial.

• $g(x,r) = x \cdot r$$x,r \in \{0,1\}^n$$g(x,r)$$f(x)$$f(x)$$r \ne 0$

• É concebível que a construção acima possa ser elaborada / ofuscada de algum modo, para obter uma construção que garanta a avaliação de uma função constante ou uma função equilibrada, e onde qual dessas duas ocorre não é óbvia ou até difícil - mas eu posso ' Não pense em como, no momento.

Lembre-se de que isso é realmente muito difícil de fazer - mas se você puder ver uma maneira de fazer isso, pode valer a pena: Bravyi, Gossett e Koening fizeram algo assim para o problema de Bernstein – Vazirani e permitiu que eles mostrar uma separação pequena, mas incondicional, entre a complexidade quântica e a clássica, que foi uma das coisas mais interessantes que ocorreram na complexidade quântica nos últimos anos.

TL; DR

• Não se preocupe com o fato de que você está 'avaliando' um oráculo.

• Se você se preocupa com alguma coisa, preocupe-se apenas com o fato de que uma descrição real da função permita resolver o mesmo problema facilmente sem um computador quântico.

• Se sua motivação é apenas praticar a programação quântica, nem se preocupe. Salve sua preocupação com problemas mais importantes, como o aquecimento global. Enquanto isso, divirta-se brincando com Legos enquanto você constrói algo mais.