Qual é o modelo computacional quântico?

Ocasionalmente, ouvi pessoas falarem sobre algoritmos quânticos e sobre estados e a capacidade de considerar várias possibilidades ao mesmo tempo, mas nunca consegui alguém para explicar o modelo computacional por trás disso. Para ser claro, não estou perguntando como os computadores quânticos são fisicamente construídos, mas como vê-los do ponto de vista computacional.

Vou repetir a recomendação de Martin Schwartz de Nielsen & Chaung como referência padrão; Há muitos outros também.

Pesquisas em campo preferem considerar famílias uniformes de circuitos quânticos, que (ironicamente) são redes acíclicas direcionadas que descrevem como o estado de um ou mais registros se transforma com o tempo, de maneira semelhante aos circuitos booleanos clássicos. Se você deseja aprender mais, recomendo aprender nos termos deste modelo.

Eu gostaria de dar algumas respostas qualitativas para complementar a resposta de Martin.

1. A computação quântica não considera realmente "múltiplas possibilidades ao mesmo tempo" --- ou mais precisamente, se você as considera ou não múltiplas possibilidades ao mesmo tempo, é uma questão de sua escolha de interpretação da mecânica quântica , ou seja, uma escolha filosófica que não tem influência sobre a capacidade ou previsões do modelo computacional. ("Considerar múltiplas possibilidades ao mesmo tempo" corresponde à "interpretação de muitos mundos" de QM.)
   
   No mínimo, pode-se dizer que um computador quântico considera múltiplas possibilidades ao mesmo tempo apenas na medida em que uma computação aleatória usando moeda flips considera múltiplas possibilidades ao mesmo tempo. Isto é porque:

2. Os estados quânticos são generalizações das distribuições de probabilidade "usuais" - com algumas diferenças simples, mas importantes. Uma distribuição de probabilidade pode ser representada como um vetor real não negativo cujas entradas somam 1: ou seja, um vetor unitário na norma ℓ ¹ . Os cálculos probabilísticos devem mapear os vetores da unidade ℓ ¹ para outros vetores e, portanto, são descritos por mapas estocásticos. Pode-se descrever a computação quântica de maneira semelhante, exceto pelo uso de vetores de unidade over ² sobre ℂ (não restrito a ser real ou não negativo); as transformações são feitas pelos mapas que preservam a ℓ ² -norm, ie operações unitárias.
   
   Esta diferença não é trivial, é claro, nem explica ainda que os coeficientes dos vetores de estado quântico significa . Mas pode ajudar a explicar o que está acontecendo com os espaços de Hilbert e os produtos tensores na computação quântica: ou seja, exatamente as mesmas coisas que acontecem na computação probabilística. O espaço de configuração de um bit aleatório é um vetor em ℝ ₊ ² (onde ℝ ₊ são os reais não negativos); mas como os bits aleatórios podem ser correlacionados, combinamos os espaços de configuração de um ou mais bits aleatórios usando o produto tensorial. Portanto, o espaço de configuração de dois bits aleatórios é ℝ ₊ ²  ℝ ℝ ₊ ²  ≅ ℝ ₊ ⁴ , ou o espaço totalmente geral de distribuições de probabilidade nas quatro seqüências distintas de dois bits. Uma operação A no primeiro desses bits aleatórios que não atua no segundo é representada pelo operador A  ⊗  I ₂  . E assim por diante. As mesmas construções se aplicam aos bits quânticos; e podemos considerar registros quânticos sobre conjuntos de elementos distinguíveis da mesma maneira que consideramos distribuições de probabilidade nesses conjuntos, novamente usando vectors vetores ² -norm sobre ℂ.
   
   Esta descrição descreve realmente os estados quânticos "puros" - aqueles para os quais você pode, em princípio, transformar de maneira preservadora de informações em uma distribuição delta na cadeia de bits 00 ... 0 (ou, mais precisamente, em um arbitrariamente próximo a isso na norma ℓ ² ). Além da aleatoriedade quântica (da qual ainda não mencionei nada explícito), você pode considerar a aleatoriedade de convexidade de baunilha correspondente a misturas probabilísticas de estados quânticos: elas são representadas por operadores de densidade , que podem ser representados por matrizes definidas positivas com traço 1 (generalizando novamente distribuições de probabilidade "clássicas", que podem ser representadas pelo caso especial de matrizes diagonais positivas com traço 1).
   
   O que é importante sobre isso é que, embora os estados quânticos sejam freqüentemente descritos como "exponencialmente grandes", isso ocorre porque geralmente são descritos usando as mesmas estruturas matemáticas das distribuições de probabilidade; por que as distribuições de probabilidade não são descritas como "exponencialmente grandes" da mesma maneira não é clara (mas, em última análise, sem importância). A dificuldade de simular estados quânticos advém desse fato, juntamente com o fato de que os coeficientes complexos dessas distribuições ℓ ² (ou os termos fora da diagonal complexos dos operadores de densidade, se você preferir) podem cancelar de uma maneira que as probabilidades não podem , tornando a estimativa deles mais difícil.

3. O emaranhamento é apenas outra forma de correlação. Para computação probabilística em, por exemplo, seqüências de caracteres booleanas, os únicos estados "puros" (que podem ser mapeados por transformações de preservação de informação em uma distribuição com pico delta em 000 ... 0) são a "base padrão" das distribuições com pico delta no cadeias booleanas diferentes. Assim, essa base de ℝ ₊ ^{2 n}é distinto. Mas não existe uma base tão distinta na mecânica quântica, tanto quanto podemos dizer - isso é mais claro para bits quânticos (procure partículas de rotação 1/2, se você quiser saber o porquê). Como conseqüência, há mais transformações de preservação de informações do que apenas as permutações: um grupo contínuo delas, de fato. Isso permite que computadores quânticos possam transformar estados de maneiras que não são possíveis para computadores probabilísticos, possivelmente obtendo uma vantagem assintótica sobre eles.
   
   Mas e o emaranhamento, que muitas pessoas acham misterioso e afirmam ser a causa da aceleração dos computadores quânticos em relação aos clássicos? "Enredamento" aqui é realmente apenas uma forma de correlação: assim como duas variáveis ​​aleatórias são correlacionadas se sua distribuição é uma combinação convexa de mais de uma distribuição de produto (com marginais diferentes em cada variável), duas "variáveis ​​quânticas" são entrelaçadas se suas distribuição é uma combinação linear (com unidade ℓ ²-norm) de duas distribuições válidas de produtos; é o mesmo conceito sob uma norma diferente e desempenha um papel semelhante nas tarefas de comunicação. (Por exemplo: "teletransporte quântico" na comunicação quântica corresponde à codificação e decodificação de uma mensagem usando um bloco único classicamente.) Essa é uma forma de correlação mais geral do que apenas bits correlacionados classicamente; mas a única maneira de mostrar isso é que as correlações codificadas no estado emaranhado se aplicam a mais de uma base privilegiada . De certa forma, o emaranhamento é uma consequência da ausência de uma base privilegiada.
   
   As pessoas gostam de invocar o entrelaçamento como o elemento-chave da computação quântica, mas isso simplesmente não parece reter água: houve resultados mostrando queo emaranhamento não é quantitativamente importante para o algoritmo de Shor fatorar números inteiros grandes, e que de fato um sistema quântico pode ter muito emaranhamento para ser útil para um cálculo. De fato, em todos os lugares que eu conheço que o emaranhamento desempenha um papel importante em um protocolo quântico é essencialmente de comunicação (onde seria de esperar que as correlações desempenhassem um papel importante para um protocolo clássico).

Nesse ponto, começo a entrar no domínio da opinião pessoal, então vou parar por aqui. Mas, esperançosamente, essas observações podem desmistificar parte do que é obscuro sobre a computação quântica e como ela é descrita.

Lance Fortnow escreveu um artigo que explica a computação quântica sem usar a mecânica quântica. Ele o apresenta essencialmente da mesma maneira que se apresentaria a computação probabilística. Suspeito que este possa ser um ponto de partida mais rápido do que algo como Nielson e Chuang (embora eu concorde que, se você realmente quiser entrar nisso, Nielson e Chung devem definitivamente estar na sua lista de leitura).

L. Fortnow. A visão de um teórico da complexidade da computação quântica. Teoria da Computação, 292 (3): 597-610, 2003. Edição especial de trabalhos apresentados no segundo workshop sobre Algoritmos no Processamento Quântico de Informações.

Bem, o texto padrão usado é Computação Quântica e Informação Quântica de Nielsen e Chuang. Abrange uma série de aspectos diferentes em um nível razoável. Quase todo mundo que trabalha no campo tem uma cópia disso na prateleira. O livro Kaye, Laflamme e Mosca também é bom, mas cobre menos (embora exista um pouco mais de foco nos algoritmos).

Embora seja perfeitamente possível explicar a computação quântica sem entrar em muita mecânica quântica, não acho que essa seja necessariamente uma boa maneira de abordar o aprendizado da computação quântica. Há muita intuição a se ganhar com a teoria física, uma vez que muitos dos modelos mais recentes de computação quântica (ou seja, modelos adiabáticos, topológicos e baseados em medidas) são mais motivados fisicamente do que a máquina quântica de Turing ou o modelo de circuito.

Dito isto, a mecânica quântica necessária para entender a computação quântica é bastante simples e é bastante bem abordada em Nielsen e Chuang. Realmente, você pode ter uma boa ideia lendo o capítulo relevante e tentando os exercícios. É o tipo de coisa com a qual você pode entender com alguns dias de trabalho. Meu conselho, no entanto, é não usar um texto de introdução padrão para a mecânica quântica. A abordagem adotada para modelar átomos, moléculas e materiais utiliza sistemas dimensionais infinitos e exige muito mais esforço para superar. Para informações quânticas, é um começo muito melhor olhar para sistemas dimensionais finitos. Além disso, tradicionalmente, os problemas estudados pelos físicos tendem a girar em torno da descoberta de estados fundamentais e comportamentos de estado estacionário, e é isso que a maioria dos textos introdutórios abordará (começando com a equação da onda de Schroedinger, independente do tempo). Para a computação quântica, tendemos a estar mais interessados ​​na evolução temporal dos sistemas, e isso é tratado de maneira muito mais sucinta nos textos de computação quântica do que nos textos introdutórios da mecânica quântica em geral (que são, por definição, mais gerais).

$BQP$

$|\phi\rangle$$\cal{H_2}$$\cal{H_2} \otimes ... \otimes \cal{H_2}$$|\psi\rangle$$U$$square$

Para uma introdução mais aprofundada, consulte o manual padrão Nielsen e Chuang.

Primeiro, você precisará entender a física quântica.

Algumas recomendações:

1. " Computação quântica para cientistas da computação ", de Noson S. Yanofsky e Mirco A. Mannucci
2. "Uma introdução à computação quântica", de Phillip Kaye, Raymond Laflamme e Michele Mosca

E, do lado mais divertido, "Um atalho no tempo: o caminho para o computador quântico", de George Johnson.

Você pode ter uma boa introdução no artigo "Uma introdução à computação quântica para não físicos", de Eleanor Rieffel e Wolfgang Polak. Talvez seja um pouco antigo, mas ainda é uma introdução boa, curta e independente ao tópico: http://arxiv.org/abs/quant-ph/9809016

Outro artigo, muito mais resumido, é "A computação quântica explicada a minha mãe", de Pablo Arrighi, em http://arxiv.org/abs/quant-ph/0305045

Você provavelmente já está ciente disso, mas em seu blog , Scott Aaronson possui links para várias palestras de seu curso sobre computação quântica, além de links para os primers de CQ de outras pessoas (basta rolar a barra lateral direita para encontrá-las) .

Se você quiser uma introdução de um livro, mas algo mais gentil que um texto como Nielsen e Chuang, eu recomendaria a Computação Quântica para Cientistas da Computação, de Yanofsky e Mannucci. Eles passam bastante tempo revisando os pré-requisitos matemáticos antes de mergulhar no próprio CQ. Se você tem uma sólida formação em matemática, este livro pode parecer muito básico, mas achei bastante útil.

Em geral, eu aconselho o segundo Joe. Mas, para uma introdução rápida, eu colocaria os textos de Lance Fortnow e Stephen Fenner na lista de leitura de cientistas da computação que se tornaram quânticos.

Se você é bastante avançado, pode começar com a pesquisa de Wolf-Drucker sobre métodos quânticos para problemas clássicos. É uma boa maneira de entender as técnicas quânticas antes de chegar a problemas quânticos .

Eu não acho que você precise aprender mecânica quântica. No entanto, depende de qual área você gostaria de trabalhar. Existem áreas do campo que realmente precisam de conhecimento sobre mecânica quântica, no entanto, como na área em que trabalho, teoria dos tipos e cálculo lambda, não preciso disso, posso fazê-lo apenas conhecendo alguns dos modelos computacionais para isso.

Além de seu texto padrão com Chuang, Michael Nielsen tem uma série de palestras em vídeo no Youtube, chamada Quantum Computing for the Determined, que até agora fornece uma visão geral do modelo computacional. Os vídeos são muito acessíveis para qualquer pessoa com um pouco de conhecimento de ciência da computação e álgebra linear.