Algoritmo quântico - Quantum algorithm

Na computação quântica , um algoritmo quântico é um algoritmo executado em um modelo realista de computação quântica , sendo o modelo mais comumente usado o modelo de circuito quântico de computação. Um algoritmo clássico (ou não quântico) é uma sequência finita de instruções, ou um procedimento passo a passo para resolver um problema, onde cada passo ou instrução pode ser executado em um computador clássico . Da mesma forma, um algoritmo quântico é um procedimento passo a passo, onde cada uma das etapas pode ser realizada em um computador quântico . Embora todos os algoritmos clássicos também possam ser executados em um computador quântico, o termo algoritmo quântico é geralmente usado para aqueles algoritmos que parecem inerentemente quânticos, ou usam algum recurso essencial da computação quântica, como a superposição quântica ou emaranhamento quântico .

Problemas que são indecidíveis usando computadores clássicos permanecem indecidíveis usando computadores quânticos. O que torna os algoritmos quânticos interessantes é que eles podem ser capazes de resolver alguns problemas mais rápido do que os algoritmos clássicos, porque a superposição quântica e o emaranhamento quântico que os algoritmos quânticos exploram provavelmente não podem ser simulados com eficiência em computadores clássicos (ver Supremacia quântica ).

Os algoritmos mais conhecidos são o algoritmo de Shor para fatoração e o algoritmo de Grover para pesquisar um banco de dados não estruturado ou uma lista não ordenada. Os algoritmos de Shor funcionam muito (quase exponencialmente) mais rápido do que o algoritmo clássico mais conhecido para fatoração, a peneira de campo numérico geral . O algoritmo de Grover é executado quadraticamente mais rápido do que o melhor algoritmo clássico possível para a mesma tarefa, uma pesquisa linear .

Visão geral

Os algoritmos quânticos são geralmente descritos, no modelo de circuito comumente usado de computação quântica, por um circuito quântico que atua em alguns qubits de entrada e termina com uma medição . Um circuito quântico consiste em portas quânticas simples que atuam em no máximo um número fixo de qubits. O número de qubits deve ser fixado porque um número variável de qubits implica em evolução não unitária. Os algoritmos quânticos também podem ser declarados em outros modelos de computação quântica, como o modelo de oráculo hamiltoniano .

Os algoritmos quânticos podem ser categorizados pelas principais técnicas utilizadas pelo algoritmo. Algumas técnicas comumente usadas / ideias em algoritmos quânticos incluem fase kick-back , a estimativa de fase , o quantum transformada de Fourier , quantum anda , amplificação amplitude e teoria quântica de campos topológica . Os algoritmos quânticos também podem ser agrupados pelo tipo de problema resolvido, por exemplo, consulte a pesquisa sobre algoritmos quânticos para problemas algébricos.

Algoritmos baseados na transformada quântica de Fourier

A transformada quântica de Fourier é o análogo quântico da transformada discreta de Fourier e é usada em vários algoritmos quânticos. A transformada de Hadamard também é um exemplo de uma transformada de Fourier quântica sobre um espaço vetorial n-dimensional sobre o campo F 2 . A transformada quântica de Fourier pode ser implementada com eficiência em um computador quântico usando apenas um número polinomial de portas quânticas .

Algoritmo Deutsch-Jozsa

Algoritmo Deutsch-Jozsa

O algoritmo Deutsch-Jozsa resolve um problema de caixa preta que provavelmente requer muitas consultas exponencialmente na caixa preta para qualquer computador clássico determinístico, mas pode ser feito com exatamente uma consulta por um computador quântico. Se permitirmos algoritmos quânticos e clássicos de erro limitado, não haverá aceleração, pois um algoritmo probabilístico clássico pode resolver o problema com um número constante de consultas com pequena probabilidade de erro. O algoritmo determina se uma função f é constante (0 em todas as entradas ou 1 em todas as entradas) ou balanceada (retorna 1 para metade do domínio de entrada e 0 para a outra metade).

Algoritmo de Bernstein-Vazirani

O algoritmo de Bernstein-Vazirani é o primeiro algoritmo quântico que resolve um problema de forma mais eficiente do que o algoritmo clássico mais conhecido. Ele foi projetado para criar uma separação oráculo entre BQP e BPP .

Algoritmo de Simon

O algoritmo de Simon resolve um problema de caixa preta exponencialmente mais rápido do que qualquer algoritmo clássico, incluindo algoritmos probabilísticos de erro limitado. Esse algoritmo, que atinge uma aceleração exponencial sobre todos os algoritmos clássicos que consideramos eficientes, foi a motivação para o algoritmo de fatoração de Shor.

Algoritmo de estimativa de fase quântica

O algoritmo de estimativa de fase quântica é usado para determinar a autofase de um autovetor de uma porta unitária, dado um estado quântico proporcional ao autovetor e acesso à porta. O algoritmo é freqüentemente usado como uma sub-rotina em outros algoritmos.

Algoritmo de Shor

O algoritmo de Shor resolve o problema do logaritmo discreto e o problema da fatoração de inteiros em tempo polinomial, enquanto os algoritmos clássicos mais conhecidos usam tempo superpolinomial. Esses problemas não são conhecidos como P ou NP-completos . É também um dos poucos algoritmos quânticos que resolve um problema não-caixa preta em tempo polinomial, onde os algoritmos clássicos mais conhecidos são executados em tempo superpolinomial.

Problema de subgrupo oculto

O problema do subgrupo oculto abeliano é uma generalização de muitos problemas que podem ser resolvidos por um computador quântico, como o problema de Simon, resolvendo a equação de Pell , testando o ideal principal de um anel R e fatoração . Existem algoritmos quânticos eficientes conhecidos para o problema do subgrupo oculto Abeliano. O problema de subgrupo oculto mais geral, onde o grupo não é necessariamente abeliano, é uma generalização dos problemas mencionados anteriormente e isomorfismo de grafos e certos problemas de rede . Algoritmos quânticos eficientes são conhecidos para certos grupos não abelianos. No entanto, nenhum algoritmo eficiente é conhecido para o grupo simétrico , o que daria um algoritmo eficiente para o isomorfismo de grafos e o grupo diédrico , o que resolveria certos problemas de rede.

Problema de amostragem de bóson

O Problema de Amostragem de Bósons em uma configuração experimental assume uma entrada de bósons (ex. Fótons de luz) de número moderado sendo dispersos aleatoriamente em um grande número de modos de saída restritos por uma unidade definida . O problema é, então, produzir uma amostra justa da distribuição de probabilidade da saída que é dependente do arranjo de entrada dos bósons e da Unidade. Resolver este problema com um algoritmo de computador clássico requer o cálculo da matriz de transformação permanente da unidade , o que pode ser impossível ou levar um tempo proibitivamente longo. Em 2014, foi proposto que a tecnologia existente e os métodos probabilísticos padrão de geração de estados de fóton único poderiam ser usados ​​como entrada em uma rede óptica linear computável quântica adequada e que a amostragem da distribuição de probabilidade de saída seria comprovadamente superior usando algoritmos quânticos. Em 2015, a investigação previu que o problema de amostragem tinha complexidade semelhante para entradas diferentes dos fótons do estado Fock e identificou uma transição na complexidade computacional de classicamente simulável para tão difícil quanto o problema de amostragem do bóson, dependendo do tamanho das entradas de amplitude coerentes.

Estimando somas de Gauss

Uma soma de Gauss é um tipo de soma exponencial . O algoritmo clássico mais conhecido para estimar essas somas leva um tempo exponencial. Uma vez que o problema do logaritmo discreto se reduz à estimativa da soma de Gauss, um algoritmo clássico eficiente para estimar as somas de Gauss implicaria em um algoritmo clássico eficiente para calcular logaritmos discretos, o que é considerado improvável. No entanto, os computadores quânticos podem estimar somas de Gauss para a precisão polinomial em tempo polinomial.

Pesca de Fourier e verificação de Fourier

Temos um oráculo que consiste em n funções booleanas aleatórias mapeando strings de n bits para um valor booleano. Precisamos encontrar cadeias de n n bits z 1 , ..., z n de modo que para a transformada de Hadamard-Fourier, pelo menos 3/4 das cadeias satisfaçam

e pelo menos 1/4 satisfaz

Isso pode ser feito em tempo polinomial quântico de erro limitado (BQP).

Algoritmos baseados em amplificação de amplitude

A amplificação de amplitude é uma técnica que permite a amplificação de um subespaço escolhido de um estado quântico. Aplicações de amplificação de amplitude geralmente levam a acelerações quadráticas sobre os algoritmos clássicos correspondentes. Pode ser considerado uma generalização do algoritmo de Grover.

Algoritmo de Grover

O algoritmo de Grover procura um banco de dados não estruturado (ou uma lista não ordenada) com N entradas, para uma entrada marcada, usando apenas consultas em vez das consultas exigidas classicamente. Classicamente, as consultas são necessárias, mesmo permitindo algoritmos probabilísticos de erro limitado.

Os teóricos consideraram uma generalização hipotética de um computador quântico padrão que poderia acessar as histórias das variáveis ​​ocultas na mecânica de Bohm . (Esse computador é completamente hipotético e não seria um computador quântico padrão, nem mesmo possível sob a teoria padrão da mecânica quântica.) Esse computador hipotético poderia implementar uma busca em um banco de dados de N itens no máximo em etapas. Isso é um pouco mais rápido do que os passos dados pelo algoritmo de Grover . Nenhum dos métodos de pesquisa permitiria que os modelos de computador quântico resolvessem problemas NP-completos em tempo polinomial.

Contagem quântica

A contagem quântica resolve uma generalização do problema de pesquisa. Ele resolve o problema de contar o número de entradas marcadas em uma lista não ordenada, em vez de apenas detectar se existe uma. Especificamente, ele conta o número de entradas marcadas em uma lista de elementos, com erro fazendo apenas consultas, onde é o número de elementos marcados na lista. Mais precisamente, o algoritmo produz uma estimativa para o número de entradas marcadas, com a seguinte precisão: .

Algoritmos baseados em caminhadas quânticas

Um passeio quântico é o análogo quântico de um passeio aleatório clássico , que pode ser descrito por uma distribuição de probabilidade sobre alguns estados. Uma caminhada quântica pode ser descrita por uma superposição quântica sobre estados. As caminhadas quânticas são conhecidas por fornecer acelerações exponenciais para alguns problemas de caixa preta. Eles também fornecem acelerações polinomiais para muitos problemas. Uma estrutura para a criação de algoritmos de caminhada quântica existe e é uma ferramenta bastante versátil.

Problema de distinção de elemento

O problema da distinção do elemento é o problema de determinar se todos os elementos de uma lista são distintos. Classicamente, Ω ( N ) consultas são necessários para obter uma lista de tamanho N . No entanto, pode ser resolvido em consultas em um computador quântico. O algoritmo ideal é de Andris Ambainis . Yaoyun Shi provou ser um limite inferior estreito quando o tamanho do intervalo é suficientemente grande. Ambainis e Kutin independentemente (e por meio de diferentes provas) estenderam seu trabalho para obter o limite inferior para todas as funções.

Problema de localização de triângulos

O problema de localização de triângulos é o problema de determinar se um dado grafo contém um triângulo (um clique de tamanho 3). O limite inferior mais conhecido para algoritmos quânticos é Ω ( N ), mas o melhor algoritmo conhecido requer O ( N 1.297 ) consultas, uma melhoria em relação às melhores O ( N 1.3 ) consultas anteriores.

Avaliação de fórmula

Uma fórmula é uma árvore com uma porta em cada nó interno e um bit de entrada em cada nó folha. O problema é avaliar a fórmula, que é a saída do nó raiz, dado o acesso do oráculo à entrada.

Uma fórmula bem estudada é a árvore binária balanceada com apenas portas NAND. Este tipo de fórmula requer consultas Θ ( N c ) usando aleatoriedade, onde . Com um algoritmo quântico, entretanto, ele pode ser resolvido em consultas Θ ( N 0,5 ). Nenhum algoritmo quântico melhor para este caso era conhecido até que um fosse encontrado para o modelo de oráculo hamiltoniano não convencional. O mesmo resultado para a configuração padrão logo se seguiu.

Algoritmos quânticos rápidos para fórmulas mais complicadas também são conhecidos.

Comutatividade de grupo

O problema é determinar se um grupo caixa preta , dado por k geradores, é comutativo . Um grupo caixa preta é um grupo com uma função oráculo, que deve ser usado para realizar as operações do grupo (multiplicação, inversão e comparação com identidade). Estamos interessados ​​na complexidade da consulta, que é o número de chamadas do oracle necessárias para resolver o problema. As complexidades de consulta determinística e aleatória são e, respectivamente. Um algoritmo quântico requer consultas, mas o algoritmo mais conhecido usa consultas.

Problemas completos de BQP

A classe de complexidade BQP (tempo polinomial quântico de erro limitado) é o conjunto de problemas de decisão solucionáveis ​​por um computador quântico em tempo polinomial com probabilidade de erro de no máximo 1/3 para todas as instâncias. É o análogo quântico da classe de complexidade clássica BPP .

Um problema é BQP -completo se estiver em BQP e qualquer problema em BQP pode ser reduzido a ele em tempo polinomial . Informalmente, a classe de problemas completos de BQP são aqueles que são tão difíceis quanto os problemas mais difíceis em BQP e são eles próprios solucionáveis ​​de forma eficiente por um computador quântico (com erro limitado).

Invariantes de nó de computação

Witten mostrou que a teoria quântica de campo topológica de Chern-Simons (TQFT) pode ser resolvida em termos de polinômios de Jones . Um computador quântico pode simular um TQFT e, assim, aproximar o polinômio de Jones, que, até onde sabemos, é difícil de calcular classicamente no pior cenário.

Simulação quântica

A ideia de que os computadores quânticos podem ser mais poderosos do que os computadores clássicos se originou na observação de Richard Feynman de que os computadores clássicos parecem exigir um tempo exponencial para simular sistemas quânticos de muitas partículas. Desde então, a ideia de que os computadores quânticos podem simular processos físicos quânticos exponencialmente mais rápido do que os computadores clássicos foi amplamente desenvolvida e elaborada. Algoritmos quânticos eficientes (isto é, tempo polinomial) foram desenvolvidos para simular sistemas bosônicos e fermiônicos e, em particular, a simulação de reações químicas além das capacidades dos supercomputadores clássicos atuais requer apenas algumas centenas de qubits. Os computadores quânticos também podem simular com eficiência as teorias de campo quântico topológico. Além de seu interesse intrínseco, este resultado levou a algoritmos quânticos eficientes para estimar invariantes topológicos quânticos , como polinômios de Jones e HOMFLY , e o invariante de Turaev-Viro de variedades tridimensionais.

Resolvendo um sistema linear de equações

Em 2009, Aram Harrow , Avinatan Hassidim e Seth Lloyd , formularam um algoritmo quântico para resolver sistemas lineares . O algoritmo estima o resultado de uma medição escalar no vetor de solução para um determinado sistema linear de equações.

Desde que o sistema linear seja esparso e tenha um número de condição baixo , e que o usuário esteja interessado no resultado de uma medição escalar no vetor de solução, em vez dos valores do próprio vetor de solução, então o algoritmo tem um tempo de execução de , onde é o número de variáveis ​​no sistema linear. Isso oferece uma aceleração exponencial sobre o algoritmo clássico mais rápido, que funciona em (ou para matrizes semidefinidas positivas).

Algoritmos híbridos quânticos / clássicos

Os algoritmos híbridos quânticos / clássicos combinam a preparação e medição do estado quântico com a otimização clássica. Esses algoritmos geralmente visam determinar o autovetor e o autovalor do estado fundamental de um Operador Hermitiano.

QAOA

O algoritmo de otimização quântica aproximada é um modelo de brinquedo de recozimento quântico que pode ser usado para resolver problemas na teoria dos grafos. O algoritmo faz uso da otimização clássica de operações quânticas para maximizar uma função objetivo.

Autossolvedor quântico variacional

O algoritmo VQE aplica a otimização clássica para minimizar a expectativa de energia de um estado ansatz para encontrar a energia do estado fundamental de uma molécula. Isso também pode ser estendido para encontrar energias excitadas de moléculas.

Eigensolvedor quântico contraído

O algoritmo CQE minimiza o resíduo de uma contração (ou projeção) da equação de Schrödinger no espaço de dois (ou mais) elétrons para encontrar a energia do estado fundamental ou excitado e a matriz de densidade reduzida de dois elétrons de uma molécula. É baseado em métodos clássicos para resolver energias e matrizes de densidade reduzida de dois elétrons diretamente da equação de Schrödinger contraída anti-Hermitiana.

Veja também

Referências

links externos

pesquisas