Computação quântica - Quantum computing

IBM Q System One (2019), o primeiro computador quântico comercial baseado em circuito

A computação quântica é um tipo de computação que aproveita as propriedades coletivas dos estados quânticos , como superposição , interferência e emaranhamento , para realizar cálculos. Os dispositivos que realizam cálculos quânticos são conhecidos como computadores quânticos . Acredita-se que eles sejam capazes de resolver certos problemas computacionais , como fatoração de inteiros (que é a base da criptografia RSA ), substancialmente mais rápido do que os computadores clássicos. O estudo da computação quântica é um subcampo da ciência da informação quântica . A expansão é esperada nos próximos anos, conforme o campo muda para o uso no mundo real em aplicações farmacêuticas, segurança de dados e outras.

A computação quântica começou em 1980, quando o físico Paul Benioff propôs um modelo de mecânica quântica da máquina de TuringRichard Feynman  e  Yuri Manin  sugeriram posteriormente que um computador quântico tinha o potencial de simular coisas que um computador clássico não poderia fazer. Em 1994, Peter Shor desenvolveu um algoritmo quântico para fatorar inteiros com potencial para descriptografar comunicações criptografadas por RSA . Apesar do progresso experimental contínuo desde o final da década de 1990, a maioria dos pesquisadores acredita que " a computação quântica tolerante a falhas [é] ainda um sonho bastante distante". Nos últimos anos, o investimento em pesquisa de computação quântica aumentou nos setores público e privado. Em 23 de outubro de 2019, o Google AI , em parceria com a Administração Nacional de Aeronáutica e Espaço dos Estados Unidos ( NASA ), afirmou ter realizado um cálculo quântico que era inviável em qualquer computador clássico , mas se essa afirmação era ou ainda é válida é um tópico de pesquisa ativa.

Existem vários tipos de computadores quânticos (também conhecidos como sistemas de computação quântica), incluindo o modelo quântico circuito , máquina quântica Turing , computador quântico adiabática , one-way computador quântico , e vários quantum autômatos celulares . O modelo mais usado é o circuito quântico , baseado no bit quântico, ou " qubit ", que é um pouco análogo ao bit na computação clássica. Um qubit pode estar em um estado quântico 1 ou 0 , ou em uma superposição dos estados 1 e 0. Quando é medido, entretanto, é sempre 0 ou 1; a probabilidade de qualquer resultado depende do estado quântico do qubit imediatamente antes da medição.

Os esforços para construir um computador quântico físico se concentram em tecnologias como transmons , armadilhas de íons e computadores quânticos topológicos , que visam criar qubits de alta qualidade. Estes qubits podem ser concebidos de forma diferente, dependendo do modelo de computação do computador quântico completo, se portas lógicas quantum , recozimento quântica , ou computação quântica adiabática . Atualmente, há uma série de obstáculos significativos para a construção de computadores quânticos úteis. É particularmente difícil manter os estados quânticos dos qubits, pois eles sofrem de decoerência quântica e fidelidade de estado . Computadores quânticos, portanto, requerem correção de erros .

Qualquer problema computacional que pode ser resolvido por um computador clássico também pode ser resolvido por um computador quântico. Por outro lado, qualquer problema que pode ser resolvido por um computador quântico também pode ser resolvido por um computador clássico, pelo menos em princípio com tempo suficiente. Em outras palavras, os computadores quânticos obedecem à tese de Church – Turing . Isso significa que, embora os computadores quânticos não forneçam vantagens adicionais sobre os computadores clássicos em termos de computabilidade , os algoritmos quânticos para certos problemas têm complexidades de tempo significativamente menores do que os correspondentes algoritmos clássicos conhecidos. Notavelmente, acredita-se que os computadores quânticos sejam capazes de resolver rapidamente certos problemas que nenhum computador clássico poderia resolver em qualquer período de tempo viável - um feito conhecido como "supremacia quântica". O estudo da complexidade computacional de problemas relacionados a computadores quânticos é conhecido como teoria da complexidade quântica .

Circuito quântico

A esfera de Bloch é uma representação de um qubit , o bloco de construção fundamental dos computadores quânticos.

Definição

O modelo predominante de computação quântica descreve a computação em termos de uma rede de portas lógicas quânticas . Este modelo pode ser pensado como uma generalização algébrica linear abstrata de um circuito clássico . Como esse modelo de circuito obedece à mecânica quântica , acredita-se que um computador quântico capaz de operar esses circuitos com eficiência seja fisicamente realizável.

Uma memória composta por bits de informação tem estados possíveis. Um vetor que representa todos os estados da memória, portanto, tem entradas (uma para cada estado). Este vetor é visto como um vetor de probabilidade e representa o fato de que a memória deve ser encontrada em um determinado estado.

Na visão clássica, uma entrada teria o valor 1 (ou seja, 100% de probabilidade de estar neste estado) e todas as outras entradas seriam zero. Na mecânica quântica, vetores de probabilidade podem ser generalizados para operadores de densidade . O formalismo do vetor de estado quântico é geralmente introduzido primeiro porque é conceitualmente mais simples e porque pode ser usado no lugar do formalismo da matriz de densidade para estados puros, onde todo o sistema quântico é conhecido.

Começamos considerando uma memória simples que consiste em apenas um bit. Essa memória pode ser encontrada em um de dois estados: o estado zero ou o estado um. Podemos representar o estado desta memória usando a notação de Dirac para que

Uma memória quântica pode então ser encontrada em qualquer superposição quântica dos dois estados clássicos e :
Em geral, os coeficientes e são números complexos . Nesse cenário, diz-se que um qubit de informação está codificado na memória quântica. O estado não é em si um vetor de probabilidade, mas pode ser conectado a um vetor de probabilidade por meio de uma operação de medição. Se a memória quântica for medida para determinar se o estado é ou (isso é conhecido como uma medição de base computacional), o estado zero seria observado com probabilidade e o estado um com probabilidade . Os números e são chamados de amplitudes quânticas .

O estado dessa memória quântica de um qubit pode ser manipulado pela aplicação de portas lógicas quânticas , de forma análoga a como a memória clássica pode ser manipulada com portas lógicas clássicas . Uma porta importante para a computação clássica e quântica é a porta NOT, que pode ser representada por uma matriz

Matematicamente, a aplicação de tal porta lógica a um vetor de estado quântico é modelada com multiplicação de matrizes . Assim e .

A matemática de portas de qubit simples pode ser estendida para operar em memórias quânticas multiqubit de duas maneiras importantes. Uma maneira é simplesmente selecionar um qubit e aplicar esse portão ao qubit alvo, deixando o restante da memória inalterado. Outra maneira é aplicar a porta ao seu destino apenas se outra parte da memória estiver no estado desejado. Essas duas opções podem ser ilustradas usando outro exemplo. Os possíveis estados de uma memória quântica de dois qubit são

A porta CNOT pode então ser representada usando a seguinte matriz:
Como consequência matemática desta definição, , , , e . Em outras palavras, o CNOT aplica uma porta NOT ( de antes) ao segundo qubit se e somente se o primeiro qubit estiver no estado . Se o primeiro qubit for , nada será feito para nenhum dos qubit.

Em resumo, uma computação quântica pode ser descrita como uma rede de portas lógicas quânticas e medições. No entanto, qualquer medição pode ser adiada para o final da computação quântica, embora esse adiamento possa vir a um custo computacional, então a maioria dos circuitos quânticos representa uma rede que consiste apenas em portas lógicas quânticas e nenhuma medição.

Qualquer computação quântica (que é, no formalismo acima, qualquer matriz unitária sobre qubits) pode ser representada como uma rede de portas lógicas quânticas de uma família bastante pequena de portas. Uma escolha de família de portas que permite essa construção é conhecida como um

conjunto de portas universais , uma vez que um computador que pode executar tais circuitos é um computador quântico universal . Um desses conjuntos comuns inclui todas as portas de um qubit, bem como a porta CNOT de cima. Isso significa que qualquer computação quântica pode ser realizada executando uma sequência de portas de um qubit junto com portas CNOT. Embora esse conjunto de portas seja infinito, ele pode ser substituído por um conjunto de portas finito apelando para o teorema de Solovay-Kitaev .

Algoritmos quânticos

O progresso na descoberta de algoritmos quânticos normalmente se concentra neste modelo de circuito quântico, embora existam exceções como o algoritmo adiabático quântico . Os algoritmos quânticos podem ser categorizados aproximadamente pelo tipo de aumento de velocidade alcançado sobre os algoritmos clássicos correspondentes.

Os algoritmos quânticos que oferecem mais do que uma aceleração polinomial sobre o algoritmo clássico mais conhecido incluem o algoritmo de Shor para fatoração e os algoritmos quânticos relacionados para calcular logaritmos discretos , resolver a equação de Pell e, de forma mais geral, resolver o problema de subgrupo oculto para grupos finitos abelianos. Esses algoritmos dependem da primitiva da transformada de Fourier quântica . Nenhuma prova matemática foi encontrada que mostre que um algoritmo clássico igualmente rápido não pode ser descoberto, embora isso seja considerado improvável. Certos problemas de oráculo, como o problema de Simon e o

problema de Bernstein-Vazirani , fornecem acelerações comprováveis, embora isso esteja no modelo de consulta quântica , que é um modelo restrito onde os limites inferiores são muito mais fáceis de provar e não necessariamente se traduzem em acelerações para problemas práticos .

Outros problemas, incluindo a simulação de processos físicos quânticos de química e física de estado sólido, a aproximação de certos polinômios de Jones e o algoritmo quântico para sistemas lineares de equações, têm algoritmos quânticos que parecem fornecer acelerações superpolinomiais e são BQP completos. Como esses problemas são BQP-completos, um algoritmo clássico igualmente rápido para eles implicaria que nenhum algoritmo quântico fornece uma aceleração superpolinomial, o que se acredita ser improvável.

Alguns algoritmos quânticos, como o algoritmo de Grover e a amplificação de amplitude , fornecem acelerações polinomiais sobre os algoritmos clássicos correspondentes. Embora esses algoritmos forneçam aceleração quadrática comparativamente modesta, eles são amplamente aplicáveis ​​e, portanto, fornecem acelerações para uma ampla gama de problemas. Muitos exemplos de acelerações quânticas prováveis ​​para problemas de consulta estão relacionados ao algoritmo de Grover, incluindo o algoritmo de Brassard, Høyer e Tapp para encontrar colisões em funções dois para um, que usa o algoritmo de Grover e o algoritmo de Farhi, Goldstone e Gutmann para avaliar NAND árvores, que é uma variante do problema de pesquisa.

Aplicações potenciais

Criptografia

Uma aplicação notável da computação quântica é para ataques a sistemas criptográficos que estão atualmente em uso. A fatoração de inteiros , que sustenta a segurança dos sistemas criptográficos de chave pública , é considerada computacionalmente inviável com um computador comum para números inteiros grandes se eles forem o produto de poucos números primos (por exemplo, produtos de dois números primos de 300 dígitos). Por comparação, um computador quântico poderia resolver esse problema com eficiência usando o algoritmo de Shor para encontrar seus fatores. Essa capacidade permitiria a um computador quântico quebrar muitos dos sistemas criptográficos em uso hoje, no sentido de que haveria um algoritmo de tempo polinomial (no número de dígitos do inteiro) para resolver o problema. Em particular, a maioria das cifras de chave pública populares são baseadas na dificuldade de fatorar inteiros ou no problema do logaritmo discreto , ambos os quais podem ser resolvidos pelo algoritmo de Shor. Em particular, os algoritmos RSA , Diffie – Hellman e curva elíptica Diffie – Hellman podem ser quebrados. Eles são usados ​​para proteger páginas da Web seguras, e-mail criptografado e muitos outros tipos de dados. Quebrá-los teria ramificações significativas para a privacidade e segurança eletrônicas.

Identificar sistemas criptográficos que podem ser seguros contra algoritmos quânticos é um tópico pesquisado ativamente no campo da criptografia pós-quântica . Alguns algoritmos de chave pública são baseados em outros problemas que não a fatoração de inteiros e problemas de logaritmo discreto aos quais o algoritmo de Shor se aplica, como o criptosistema de McEliece baseado em um problema na teoria da codificação . Criptossistemas baseados em rede também não são conhecidos por serem quebrados por computadores quânticos, e encontrar um algoritmo de tempo polinomial para resolver o problema do subgrupo escondido diédrico , que quebraria muitos criptossistemas baseados em rede, é um problema aberto bem estudado. Foi provado que a aplicação do algoritmo de Grover para quebrar um algoritmo simétrico (chave secreta) por força bruta requer tempo igual a aproximadamente 2 n / 2 invocações do algoritmo criptográfico subjacente, em comparação com aproximadamente 2 n no caso clássico, o que significa que a chave simétrica os comprimentos são efetivamente reduzidos à metade: o AES-256 teria a mesma segurança contra um ataque usando o algoritmo de Grover que o AES-128 contra a busca de força bruta clássica (consulte o tamanho da chave ).

A criptografia quântica pode cumprir potencialmente algumas das funções da criptografia de chave pública. Os sistemas criptográficos baseados em quantum poderiam, portanto, ser mais seguros do que os sistemas tradicionais contra hacking quântico.

Problemas de pesquisa

O exemplo mais conhecido de um problema de admissão de uma aceleração quântica polinomial é a pesquisa não estruturada , localizando um item marcado em uma lista de itens em um banco de dados. Isso pode ser resolvido pelo algoritmo de Grover usando consultas ao banco de dados, quadraticamente menos do que as consultas necessárias para algoritmos clássicos. Nesse caso, a vantagem não é apenas demonstrável, mas também ótima: foi mostrado que o algoritmo de Grover fornece a probabilidade máxima possível de encontrar o elemento desejado para qualquer número de pesquisas do oráculo.

Os problemas que podem ser resolvidos com o algoritmo de Grover têm as seguintes propriedades:

  1. Não há estrutura pesquisável na coleção de respostas possíveis,
  2. O número de respostas possíveis para verificar é o mesmo que o número de entradas para o algoritmo, e
  3. Existe uma função booleana que avalia cada entrada e determina se é a resposta correta

Para problemas com todas essas propriedades, o tempo de execução do algoritmo de Grover em um computador quântico é calculado como a raiz quadrada do número de entradas (ou elementos no banco de dados), em oposição ao escalonamento linear dos algoritmos clássicos. Uma classe geral de problemas aos quais o algoritmo de Grover pode ser aplicado é o problema de satisfatibilidade booleana , onde o banco de dados através do qual o algoritmo itera é aquele de todas as respostas possíveis. Um exemplo e (possível) aplicação disso é um cracker de senha que tenta adivinhar uma senha. Cifras simétricas como Triple DES e AES são particularmente vulneráveis ​​a esse tipo de ataque. Esta aplicação de computação quântica é um grande interesse das agências governamentais.

Simulação de sistemas quânticos

Uma vez que a química e a nanotecnologia dependem da compreensão dos sistemas quânticos, e tais sistemas são impossíveis de simular de maneira eficiente, classicamente, muitos acreditam que a simulação quântica será uma das aplicações mais importantes da computação quântica. A simulação quântica também pode ser usada para simular o comportamento de átomos e partículas em condições incomuns, como as reações dentro de um colisor . Simulações quânticas podem ser usadas para prever caminhos futuros de partículas e prótons sob superposição no experimento de dupla fenda . Cerca de 2% da produção anual de energia global é usada para a fixação de nitrogênio para produzir amônia para o processo Haber na indústria de fertilizantes agrícolas, enquanto os organismos que ocorrem naturalmente também produzem amônia. Simulações quânticas podem ser usadas para entender este processo aumentando a produção.

Recozimento quântico e otimização adiabática

O recozimento quântico ou computação quântica adiabática se baseia no teorema adiabático para realizar cálculos. Um sistema é colocado no estado fundamental para um hamiltoniano simples, que evolui lentamente para um hamiltoniano mais complicado, cujo estado fundamental representa a solução para o problema em questão. O teorema adiabático afirma que, se a evolução for lenta o suficiente, o sistema permanecerá em seu estado fundamental durante todo o processo.

Aprendizado de máquina

Como os computadores quânticos podem produzir resultados que os computadores clássicos não podem produzir de forma eficiente, e como a computação quântica é fundamentalmente algébrica linear, alguns expressam esperança no desenvolvimento de algoritmos quânticos que podem acelerar as tarefas de aprendizado de máquina. Por exemplo, acredita-se que o algoritmo quântico para sistemas lineares de equações , ou "Algoritmo HHL", em homenagem a seus descobridores Harrow, Hassidim e Lloyd, fornece aceleração em relação às contrapartes clássicas. Alguns grupos de pesquisa exploraram recentemente o uso de hardware de recozimento quântico para treinar máquinas de Boltzmann e redes neurais profundas .

Biologia Computacional

No campo da biologia computacional , a computação tem desempenhado um grande papel na solução de muitos problemas biológicos. Um dos exemplos mais conhecidos seria em genômica computacional e como a computação reduziu drasticamente o tempo para sequenciar um genoma humano. Dado como a biologia computacional está usando modelagem e armazenamento de dados genéricos, suas aplicações para biologia computacional também devem surgir.

Projeto de drogas auxiliado por computador e química generativa

Modelos profundos de química generativa surgem como ferramentas poderosas para acelerar a descoberta de medicamentos. No entanto, o imenso tamanho e a complexidade do espaço estrutural de todas as possíveis moléculas semelhantes a drogas representam obstáculos significativos, que poderiam ser superados no futuro por computadores quânticos. Os computadores quânticos são naturalmente bons para resolver problemas complexos de muitos corpos quânticos e, portanto, podem ser instrumentais em aplicações que envolvem a química quântica. Portanto, pode-se esperar que modelos generativos aprimorados quânticos, incluindo GANs quânticos, possam eventualmente ser desenvolvidos em algoritmos de química generativa finais. Arquiteturas híbridas que combinam computadores quânticos com redes clássicas profundas, como Autoencoders Variacionais Quânticos, já podem ser treinadas em recozedores disponíveis comercialmente e usadas para gerar novas estruturas moleculares semelhantes a drogas.

Supremacia quântica

John Preskill introduziu o termo supremacia quântica para se referir à vantagem hipotética de aceleração que um computador quântico teria sobre um computador clássico em um determinado campo. O Google anunciou em 2017 que esperava alcançar a supremacia quântica até o final do ano, embora isso não tenha acontecido. A IBM disse em 2018 que os melhores computadores clássicos serão derrotados em alguma tarefa prática dentro de cerca de cinco anos e vê o teste de supremacia quântica apenas como um potencial futuro benchmark. Embora céticos como Gil Kalai duvidem de que a supremacia quântica será alcançada, em outubro de 2019, um processador Sycamore criado em conjunto com o Google AI Quantum foi relatado por ter alcançado a supremacia quântica, com cálculos mais de 3.000.000 vezes mais rápidos que os da Summit , em geral considerado o computador mais rápido do mundo. Em dezembro de 2020, um grupo da USTC implementou um tipo de amostragem de Boson em 76 fótons com um computador quântico fotônico Jiuzhang para demonstrar a supremacia quântica. Os autores afirmam que um supercomputador contemporâneo clássico exigiria um tempo computacional de 600 milhões de anos para gerar o número de amostras que seu processador quântico pode gerar em 20 segundos. Bill Unruh duvidou da praticidade dos computadores quânticos em um artigo publicado em 1994. Paul Davies argumentou que um computador de 400 qubit entraria em conflito com a informação cosmológica limitada pelo princípio holográfico .

Obstáculos

Existem vários desafios técnicos na construção de um computador quântico em grande escala. O físico David DiVincenzo listou estes requisitos para um computador quântico prático:

  • Fisicamente escalável para aumentar o número de qubits
  • Qubits que podem ser inicializados com valores arbitrários
  • Portas quânticas que são mais rápidas que o tempo de decoerência
  • Conjunto de portão universal
  • Qubits que podem ser lidos facilmente

Fornecer peças para computadores quânticos também é muito difícil. Muitos computadores quânticos, como os construídos pelo Google e pela IBM , precisam do Hélio-3 , um subproduto da pesquisa nuclear , e de cabos supercondutores especiais feitos apenas pela empresa japonesa Coax Co.

O controle de sistemas multi-qubit requer a geração e coordenação de um grande número de sinais elétricos com resolução de temporização rígida e determinística. Isso levou ao desenvolvimento de controladores quânticos que permitem a interface com os qubits. O dimensionamento desses sistemas para suportar um número crescente de qubits é um desafio adicional.

Decoerência quântica

Um dos maiores desafios envolvidos na construção de computadores quânticos é controlar ou remover a decoerência quântica . Isso geralmente significa isolar o sistema de seu ambiente, pois as interações com o mundo externo fazem com que o sistema descoere. No entanto, outras fontes de decoerência também existem. Os exemplos incluem os portões quânticos e as vibrações da rede e rotação termonuclear de fundo do sistema físico usado para implementar os qubits. A decoerência é irreversível, pois é efetivamente não unitária, e geralmente é algo que deve ser altamente controlado, se não evitado. Decoherence vezes para sistemas candidatos, em particular, o tempo de relaxamento transversal T 2 (por RMN e de ressonância magnética tecnologia, também chamado o tempo dephasing ), tipicamente variam entre nanosegundos e segundos a baixa temperatura. Atualmente, alguns computadores quânticos exigem que seus qubits sejam resfriados a 20 milikelvins para evitar decoerência significativa. Um estudo de 2020 argumenta que a radiação ionizante , como os raios cósmicos, pode, no entanto, causar a descoerência de certos sistemas em milissegundos.

Como resultado, tarefas demoradas podem tornar alguns algoritmos quânticos inoperantes, já que manter o estado dos qubits por um período longo o suficiente acabará por corromper as superposições.

Esses problemas são mais difíceis para abordagens ópticas, pois as escalas de tempo são ordens de magnitude mais curtas e uma abordagem frequentemente citada para superá-los é a modelagem de pulso óptico . As taxas de erro são normalmente proporcionais à razão entre o tempo de operação e o tempo de decoerência, portanto, qualquer operação deve ser concluída muito mais rapidamente do que o tempo de decoerência.

Conforme descrito no teorema do limiar quântico , se a taxa de erro for pequena o suficiente, acredita-se que seja possível usar a correção de erros quânticos para suprimir erros e decoerência. Isso permite que o tempo total de cálculo seja maior do que o tempo de decoerência se o esquema de correção de erros puder corrigir os erros mais rápido do que a decoerência os introduz. Um número frequentemente citado para a taxa de erro necessária em cada porta para cálculo tolerante a falhas é 10 -3 , assumindo que o ruído está despolarizando.

Atender a essa condição de escalabilidade é possível para uma ampla variedade de sistemas. No entanto, o uso da correção de erros traz consigo o custo de um número muito maior de qubits necessários. O número necessário para fatorar inteiros usando o algoritmo de Shor ainda é polinomial, e pensado estar entre L e L 2 , onde L é o número de dígitos no número a ser fatorado; algoritmos de correção de erro seria inflar este valor por um fator adicional de L . Para um número de 1000 bits, isso implica a necessidade de cerca de 10 4 bits sem correção de erros. Com a correção de erros, o número aumentaria para cerca de 10 7 bits. O tempo de cálculo é de cerca de L 2 ou cerca de 10 7 passos e a 1 MHz, cerca de 10 segundos.

Uma abordagem muito diferente para o problema de estabilidade-decoerência é criar um computador quântico topológico com anyons , quase-partículas usadas como fios e contando com a teoria da trança para formar portas lógicas estáveis.

O físico Mikhail Dyakonov expressou ceticismo em relação à computação quântica da seguinte forma:

"Portanto, o número de parâmetros contínuos que descrevem o estado de um computador quântico útil em qualquer momento deve ser ... cerca de 10 300 ... Poderíamos aprender a controlar os mais de 10 300 parâmetros continuamente variáveis ​​que definem o estado quântico de tal sistema? Minha resposta é simples. Não, nunca. "

Desenvolvimentos

Modelos de computação quântica

Existem vários modelos de computação quântica, diferenciados pelos elementos básicos nos quais a computação é decomposta. Os quatro modelos principais de importância prática são:

A máquina de Turing quântica é teoricamente importante, mas a implementação física desse modelo não é viável. Todos os quatro modelos de computação demonstraram ser equivalentes; cada um pode simular o outro com não mais do que uma sobrecarga polinomial.

Realizações físicas

Para implementar fisicamente um computador quântico, muitos candidatos diferentes estão sendo buscados, entre eles (distinguidos pelo sistema físico usado para realizar os qubits):

O grande número de candidatos demonstra que a computação quântica, apesar do rápido progresso, ainda está em sua infância.

Relação com a computabilidade e a teoria da complexidade

Teoria da computabilidade

Qualquer problema computacional solucionável por um computador clássico também pode ser resolvido por um computador quântico. Intuitivamente, isso ocorre porque se acredita que todos os fenômenos físicos, incluindo o funcionamento de computadores clássicos, podem ser descritos por meio da mecânica quântica , que está por trás do funcionamento dos computadores quânticos.

Por outro lado, qualquer problema solucionável por um computador quântico também pode ser resolvido por um computador clássico; ou mais formalmente, qualquer computador quântico pode ser simulado por uma máquina de Turing . Em outras palavras, os computadores quânticos não fornecem nenhum poder adicional sobre os computadores clássicos em termos de computabilidade . Isso significa que os computadores quânticos não podem resolver problemas indecidíveis como o problema da parada e a existência de computadores quânticos não refuta a tese de Church-Turing .

Por enquanto, os computadores quânticos não satisfazem a forte tese da Igreja . Embora máquinas hipotéticas tenham sido realizadas, um computador quântico universal ainda não foi construído fisicamente. A versão forte da tese de Church requer um computador físico e, portanto, não há computador quântico que ainda satisfaça a forte tese de Church.

Teoria da complexidade quântica

Embora os computadores quânticos não consigam resolver quaisquer problemas que os computadores clássicos já não possam resolver, suspeita-se que eles podem resolver certos problemas mais rápido do que os computadores clássicos. Por exemplo, sabe-se que os computadores quânticos podem fatorar números inteiros de forma eficiente , embora não seja o caso dos computadores clássicos.

A classe de problemas que podem ser eficientemente resolvidos por um computador quântico com erro limitado é chamada de BQP , para "erro limitado, tempo quântico, polinomial". Mais formalmente, BQP é a classe de problemas que podem ser resolvidos por uma máquina de Turing quântica de tempo polinomial com uma probabilidade de erro de no máximo 1/3. Como uma classe de problemas probabilísticos, BQP é a contraparte quântica do BPP ("erro limitado, probabilístico, tempo polinomial"), a classe de problemas que podem ser resolvidos por máquinas de Turing probabilísticas em tempo polinomial com erro limitado. Sabe-se que BPP BQP e é amplamente suspeito que BQP BPP, o que intuitivamente significaria que os computadores quânticos são mais poderosos do que os computadores clássicos em termos de complexidade de tempo.

A relação suspeita de BQP com várias classes de complexidade clássicas.

A relação exata de BQP com P , NP e PSPACE não é conhecida. No entanto, sabe-se que P BQP PSPACE; ou seja, todos os problemas que podem ser resolvidos de forma eficiente por um computador clássico determinístico também podem ser resolvidos de forma eficiente por um computador quântico, e todos os problemas que podem ser resolvidos de forma eficiente por um computador quântico também podem ser resolvidos por um computador clássico determinístico com recursos de espaço polinomial . Suspeita-se ainda que BQP seja um superconjunto estrito de P, o que significa que existem problemas que são eficientemente solucionáveis ​​por computadores quânticos que não são eficientemente solucionáveis ​​por computadores clássicos determinísticos. Por exemplo, a fatoração de inteiros e o problema do logaritmo discreto são conhecidos por estarem em BQP e são suspeitos de estarem fora de P. Sobre a relação de BQP a NP, pouco se sabe além do fato de que alguns problemas NP que se acredita não estarem em P também estão em BQP (a fatoração de inteiros e o problema de logaritmo discreto estão em NP, por exemplo). Suspeita-se que NP BQP; isto é, acredita-se que existam problemas verificáveis ​​de forma eficiente que não podem ser resolvidos de forma eficiente por um computador quântico. Como uma consequência direta dessa crença, também se suspeita que BQP é disjunto da classe de problemas NP-completos (se um problema NP-completo estivesse em BQP, então seguir-se-ia da dureza NP que todos os problemas em NP estão em BQP).

A relação do BQP com as classes básicas de complexidade clássica pode ser resumida da seguinte forma:

Também é conhecido que BQP está contido na classe de complexidade #P (ou mais precisamente na classe associada de problemas de decisão P #P ), que é uma subclasse de PSPACE .

Especulou-se que mais avanços na física poderiam levar a computadores ainda mais rápidos. Por exemplo, foi mostrado que um computador quântico de variável oculta não local baseado na Mecânica Bohmiana poderia implementar uma busca em um banco de dados de itens em na maioria das etapas, uma ligeira aceleração sobre o algoritmo de Grover , que é executado em etapas. Observe, entretanto, que nenhum dos métodos de pesquisa permitiria aos computadores quânticos resolver problemas NP-completos em tempo polinomial. As teorias da gravidade quântica , como a teoria M e a gravidade quântica em loop , podem permitir que computadores ainda mais rápidos sejam construídos. No entanto, definir computação nessas teorias é um problema em aberto devido ao problema do tempo ; isto é, dentro dessas teorias físicas, atualmente não há uma maneira óbvia de descrever o que significa para um observador enviar dados a um computador em um ponto no tempo e, em seguida, receber os resultados em um momento posterior.

Veja também

Referências

Leitura adicional

Livros didáticos

Artigos acadêmicos

links externos

Palestras