# Computação quântica

A computação quântica é a ciência que estuda as aplicações das teorias e propriedades da mecânica quântica na Ciência da Computação. Dessa forma seu principal foco é o desenvolvimento do computador quântico.
Na computação clássica o computador é baseado na arquitetura de Von Neumann que faz uma distinção clara entre elementos de processamento e armazenamento de dados, isto é, possui processador e memória destacados por um barramento de comunicação, sendo o seu processamento sequencial.
Entretanto os computadores atuais possuem limitações, como por exemplo na área de Inteligência Artificial (IA), onde não existem computadores com potência ou velocidade de processamento suficiente para suportar uma IA avançada. Dessa forma surgiu a necessidade da criação de um computador alternativo dos usuais que resolvesse problemas de IA, ou outros como a fatoração em primos de números muito grandes, logaritmos discretos e simulação de problemas da Física Quântica.
A Lei de Moore afirma que a velocidade de um computador é dobrada a cada 12 meses. Assim sempre houve um crescimento constante na velocidade de processamento dos computadores. Entretanto essa evolução tem um certo limite, um ponto onde não será possível aumentar essa velocidade e então se fez necessária uma revolução significativa na computação para que este obstáculo fosse quebrado. E assim os estudos em Computação Quântica se tornaram muito importantes e a necessidade do desenvolvimento de uma máquina extremamente eficiente se torna maior a cada dia.

## História

A pesquisa para o desenvolvimento da computação quântica iniciou-se já na década de 50 quando pensavam em aplicar as leis da física e da mecânica quântica nos computadores. Em 1981 em uma conferência no MIT o físico Richard Feynman apresentou uma proposta para utilização de sistemas quânticos em computadores, que teriam então uma capacidade de processamento superior aos computadores comuns. Já em 1985, David Deutsch, da Universidade de Oxford, descreveu o primeiro computador quântico, uma Máquina de Turing Quântica, ele simularia outro computador quântico. Depois de Deutsch apenas em 1994 houve notícias da computação quântica, quando em Nova Jersey, no Bell Labs da AT&T, o professor de matemática aplicada Peter Shor desenvolveu o Algoritmo de Shor, capaz de fatorar grandes números numa velocidade muito superior à dos computadores convencionais. Em 1996, Lov Grover, também da Bell Labs, desenvolveu o Speedup, o primeiro algoritmo para pesquisa de base de dados quânticos. Nesse mesmo ano foi proposto um modelo para a correção do erro quântico. Em 1999 no MIT foram construídos os primeiros protótipos de computadores quânticos utilizando montagem térmica. No ano de 2007 surge o Orion, um processador quântico de 16 qubits que realiza tarefas praticas foi desenvolvido pela empresa canadense D-Wave. Em 2011 a D-Wave lançou o primeiro computador quântico para comercialização, o D-Wave One, que possui um processador de 128 qubits. Porém o D-Wave One ainda não é totalmente independente, precisa ser usado em conjunto com computadores convencionais. Em 2017, a D-Wave Systems lançou comercialmente o 2000Q, um computador quântico de 2000 qubits a módicos US$ 15 milhões. O computador quântico anterior da companhia tinha 1.000 qubits.
Em 2017, O físico brasileiro Guilherme Tosi, juntamente com uma equipe de pesquisadores da Universidade de Nova Gales do Sul, na Austrália, inventou uma nova arquitetura radical para a computação quântica, baseada em ‘flip-flop qubits’ que pode ser usada em um novo tipo de computador quântico permitindo, assim, a fabricação de processadores quânticos em larga escala pode se tornar muito mais barata – e mais fácil – do que se pensava ser possível, sem a necessidade do processo complicado da colocação precisa dos átomos de silício no processador.

## Quebras de paradigmas

A computação quântica quebra inúmeros paradigmas da computação clássica, na qual podemos dividir os problemas em "problemas tratáveis" e "problemas intratáveis".
Todos os elementos que mudam as estruturas clássicas vem das mudanças que a física clássica trouxe. Físicos como Heisenberg, Bohr, Schrödinger e Einstein estudaram esses novos fundamentos. Dentre eles podemos destacar:
* Sobreposição quântica
* Experiência do Gato de Schrödinger
* Entrelaçamento quântico ou "Ação fantasmagórica à distância"
* Teletransporte quântico
* Espalhamento de Rutherford
* Existência de multiverso
E foi graças a estes princípios que foi possível o desenvolvimento da computação quântica.

## Princípios

A mecânica quântica é considerada a mais bem sucedida teoria física. Pois desde a sua criação até os dias atuais, ela tem sido aplicada em diversos ramos, desde a física de partículas, atômica e molecular até a astrofísica e matéria condensada.
Na computação quântica a unidade de informação básica é o Bit quântico ou q-bit. O fato da computação quântica ser tão poderosa está no fato de que além de assumir '0' ou '1' como na computação clássica, ela pode assumir ambos os estados '0' e '1' ao mesmo tempo. Parece estranho algo assumir os dois estados diferentes ao mesmo tempo, mas a experiência mental do Gato de Schrödinger pode dar um sentido intuitivo à situação. E é graças à essa propriedade da superposição de estados que motivou os estudos em computação quântica. Se na computação clássica o processamento é sequencial, na computação quântica o processamento é simultâneo.
Imagine que uma pessoa precise encontrar o contato de telefone de alguma pessoa em uma lista, na computação clássica é como se ela olhasse em cada nome conferindo se é o contato procurado. Já em um processamento quântico é como se uma pessoa conseguisse conferir vários nomes a cada processamento.
O q-bit é descrito por um vetor estados em um sistema quântico de dois níveis o qual é equivalente a um vetor de espaço bidimensional sobre números complexos. Usa-se a notação de bra-ket para representá-los:
    $|0\rangle ={\begin{bmatrix}0\\1\end{bmatrix}}$
Assim, o estado de um q-bit pode ser representado por:
    $|\psi \rangle =\alpha |0\rangle +\beta |1\rangle ,\,$
O conjunto $\{|0\rangle ,|1\rangle \}$ forma uma base no espaço de Hilbert de duas dimensões, chamada de base computacional.
Para a manipulação dos estados quânticos utiliza-se principalmente técnicas ópticas, isto é radiação eletromagnética. Estes dispositivos constituem-se as portas lógicas quânticas. A manipulação pode ser realizada utilizando átomos que podem ser excitados ou não ou os dois ao mesmo tempo. Outro dispositivo utilizado é a manipulação de fótons. A vantagem em utilizá-los está no fato de que esses fótons podem constituir-se portadores altamente estáveis de informação quântica. Entretanto fótons não interagem diretamente entre si, sendo necessário o uso de um átomo como mediador, que introduz um ruído adicional e complicações no experimento. Neste caso um fóton interage com um átomo que por sua vez interage com o segundo fóton, levando à interação completa entre os dois fótons.
Para armazenar os q-bits utiliza-se armadilhas de íons (íon trap) em que um pequeno número de átomos carregados são aprisionados e armadilhas de átomos neutros (neutral íon trap) para aprisionar átomos sem carga.
Neste esquema os fótons são usados para manipular a informação contida nos átomos, dessa forma constituem um tipo de porta lógica quântica que aplica pulsos apropriados de radiação eletromagnética para que os átomos vizinhos possam interagir um com o outro como via, por exemplo, forças dipolo.
Outra classe de processamento de informação quântica é baseada na ressonância magnética nuclear (RMN). Neste caso a informação quântica é armazenada nos spins nucleares dos átomos em moléculas e as portas lógicas manipulam essa informação usando a radiação eletromagnética. Um pósitron ou elétron podem ter um spin pra cima, pra baixo e os dois ao mesmo tempo.
Os momentos magnéticos nucleares fazem um movimento natural de precessão na presença de campos magnéticos. Os estados quânticos dos núcleos podem ser manipulados irradiando os núcleos com pulsos de rádio frequência sintonizados na frequência de precessão destes.
Em um determinado composto constituído por diferentes átomos pode-se medir as ressonâncias dos núcleos de alguns átomos sem alterá-los utilizando a RMN. Ela é sensível às interações dos momentos nucleares expostos à campos elétricos e magnéticos locais, estas interações são chamadas de hiperfinas. Cada tipo de spin possui uma velocidade angular que depende do campo aplicado e da interação de troca entre eles.
Assim como na computação clássica, na computação quantica utiliza-se circuitos, porém esses circuitos são quânticos:
* Entrada: considera-se conjuntamente os qubits de entrada, matematicamente o que é chamado de seu produto tensorial;
* Linhas horizontais: as linhas que aparecem não são necessariamente fios. Elas representam a evolução de um qubit, podendo ser apenas a passagem do tempo ou, por exemplo, o deslocamento de um fóton;
* Sentido: o circuito descreve a evolução do sistema quântico no tempo, da esquerda para a direita;
* Linhas verticais: o segmento vertical informa que o circuito atua simultaneamente nos dois qubits. A linha vertical representa o sincronismo, e não o envio de informação;
* Controle: indica que o qubit representado nessa linha é um qubit de controle, ou seja, caso esteja no estado $|1\rangle ,$ a porta realiza a operação; caso esteja no estado $|0\rangle ,$ a porta não realiza operação alguma. Caso o qubit de controle seja um estado superposto ou os 2 qubits estejam emaranhados, não é possível compreender o comportamento individual do qubit de controle e do qubit alvo. Deve-se considerar a ação do operador unitário, que representa todo o circuito, atuando simultaneamente nos 2 qubits.
* Saída: os qubits que compõem a saída do circuito podem ou não ser medidos. Como o qubit inferior está sendo medido, o resultado será 0 ou 1.
Como vemos, operações lógicas ou até mesmo algoritmos podem ser descritos por um circuito quântico. Nestes circuitos podemos utilizar as portas lógicas utilizadas na computação clássica, mas podemos utilizar ainda outras que chegam a permitir, por exemplo, a construção de um possível circuito para o teletransporte de dados.
Atualmente é possível realizar qualquer operação clássica utilizando somente portas Nand. O mesmo ocorre em circuitos quânticos onde as portas são: Hadanard (H), Controladora (CNOT), fase (S) e $\scriptstyle {\pi }/8$(T). Exemplos de portas quânticas:
* Porta NOT Quântica:
No caso clássico, a porta NOT troca o 1 por 0 e vice-versa. A generalização para o caso quântico é dada por um operador $X$ que satisfaz
    $X|1\rangle =|0\rangle$ e $X|0\rangle =|1\rangle .$
Com isso, verifica-se facilmente que a representação matricial do operador $X$ é dada por
    $X={\begin{bmatrix}0&1\\1&0\end{bmatrix}}.$
Com a porta NOT quântica, existem situações sem contrapartida no caso clássico, pois, se a entrada $|\phi \rangle$ for uma superposição dos estados $|0\rangle$ e $|1\rangle ,$
    $|\phi \rangle =\alpha |0\rangle +\beta |1\rangle ,$
a saída será
    $X|\phi \rangle =\beta |0\rangle +\alpha |1\rangle ,$
A porta $X$ é apenas uma das portas de 1 qubit, já que há infinitas matrizes unitárias $2\times 2$.
* Porta CNOT Quântica:
Atua em estados de 2 qubits, é a contrapartida quântica do circuito clássico da porta XOR. Ela tem 2 qubits de entrada, o de controle e o alvo. Uma porta controlada, age dependendo do valor do qubit de controle. Ela é "ativada" se o qubit de controle estiver no estado $|1\rangle ,$ e nada faz, se ele estiver no estado $|0\rangle .$ Essa descrição é adequada apenas quando o qubit de controle está nos estados $|0\rangle ,$ ou $|1\rangle .$ Entretanto, o que distingue a porta CNOT quântica da clássica é que, na porta CNOT quântica, os qubits alvo e de controle podem ser estados superpostos.
A ação da porta CNOT pode ser caracterizada pelas transformações operadas nos elementos da base computacional associada, ou seja,
    ${\begin{matrix}|00\rangle &\rightarrow &|00\rangle ,\\|01\rangle &\rightarrow &|01\rangle ,\\|10\rangle &\rightarrow &|11\rangle ,\\|11\rangle &\rightarrow &|10\rangle .\end{matrix}}$
Note que é possível representar essa ação na base computacional de forma mais esquemática por
    $|i,j\rangle \rightarrow |i,i\oplus j\rangle ,$
onde $i,j\in \{0,1\}$ e $\oplus$ é a adição módulo 2.
Entretanto da mesma maneira que a superposição de estados permite a criação do computador quântico é essa mesma propriedade que inviabiliza a criação deles. A superposição é muito sensível a qualquer microruído eletromagnético que pode alterar o estado do q-bit fazendo com que a informação que ele continha seja perdida. Outro fato importante em questão é o superaquecimento das máquinas.

## Algoritmos quânticos

No mundo da computação quântica, estamos sempre buscando maneiras de tornar nossos computadores mais rápidos e eficientes. Existem diferentes tipos de programas, chamados de algoritmos, que podem ajudar nisso. Alguns desses algoritmos funcionam de maneira diferente dos programas normais que usamos em nossos computadores todos os dias.

#### Pilares dos algoritmos quânticos

* Amplificação de Amplitude: Uma técnica empregada em algoritmos como o de Grover para aumentar a probabilidade de encontrar a solução correta.
* Princípio da Transformada Quântica de Fourier: Fundamental em muitos algoritmos quânticos, como o de Shor, realiza transformações de dados em espaços de estado quântico.
* Interferência Quântica: Trabalhando junto com a amplificação de amplitude, a interferência serve para neutralizar os resultados menos prováveis deixando somente o mais provável como output.
* Princípio da Incerteza de Heisenberg: A mecânica quântica é probabilística, ou seja, os outputs dos algoritmos não vão nos devolver um resultado determinado, mas sim a probabilidade de um.
O progresso em achar algoritmos quânticos normalmente foca no modelo de circuito quântico, apesar de exceções como o algoritmo adiabático quântico existam. Algoritmos quânticos podem ser grosseiramente categorizados pela quantidade de aumento na velocidade de processamento alcançada sobre o correspondente algoritmo clássico.

#### Algoritmo adiabático

O algoritmo quântico adiabático funciona com base nas leis adiabáticas físicas, indo de um estado de menos energia cinética para um estado com mais energia. Os computadores quânticos adiabáticos são relativamente mais simples de serem produzidos, mas sua aplicação também é bem mais limitada. Um dos exemplos de usos desses computadores é ao calcular rotas em até um lugar.
Primeiro, é encontrada uma Hamiltoniana (potencialmente complicada) cujo estado fundamental descreve a solução do problema de interesse. Em seguida, um sistema com uma Hamiltoniana simples é preparado e inicializado para o estado fundamental. Por fim, a Hamiltoniana simples é evoluída adiabaticamente para a Hamiltoniana complicada desejada. Pelo teorema adiabático, o sistema permanece no estado fundamental, então, no final, o estado do sistema descreve a solução do problema. Foi demonstrado que a computação quântica adiabática é polinomialmente equivalente à computação quântica convencional no modelo de circuito.
Na computação quântica adiabática, cada processamento de algum algoritmo faz com que o sistema quântico que reproduz os qubits passe por um processo chamado annealing quântico, na tradução literal recozimento, que evolui o estado do sistema de uma configuração inicial (inputs, ou especificações do problema desejado) para um estado final (output, resolução do problema), sempre almejando o estado com menor energia.

#### Demais algoritmos

Algoritmos quânticos que oferecem mais de um aumento de velocidade polinomial sobre o algoritmo clássico mais conhecido incluem o algoritmo de Shor para fatorar e os demais algoritmos quânticos para computar logaritmos discretos. Esses algoritmos dependem do princípio da transformação quântica de Fourier, que transforma a saída do algoritmo em uma onda de probabilidade parecido com o a do princípio da incerteza de Heisenberg para o usuário. Nenhuma prova matemática foi achada que mostre que algoritmos clássicos com velocidade igual não possam ser descobertos, mas evidências sugerem que sejam improváveis.
Outro algoritmo importante é o algoritmo quântico de Deutsch-Jozsa, que serve para descobrir se uma função é balanceada ou constante com bem menos medidas do que seu correspondente clássico, seu aumento de velocidade oferecido comparado ao que temos no mundo clássico é quadrático, ou seja, se um algoritmo clássico demorasse n inputs para achar o resultado, com o algoritmo de Deutsch-Jozsa demoraria-se √n inputs.
Outros problemas, incluindo a simulação de processos físicos quânticos da química e física de estado solido, aproximação de certas “Jones” polinomiais, e o algoritmo quântico para esses sistemas lineares de equações tem algoritmos quânticos que parecem dar aumento de velocidade super polinomiais e são completas “BQP”. Por conta desses problemas serem completas “BQP”, um algoritmo clássico igualmente rápido para eles sugeriria que nenhum algoritmo quântico daria aceleração super polinomial, que se acredita ser improvável.
Alguns algoritmos quânticos, como o algoritmo de Grover e a amplificação de amplitude, dão melhora de velocidade polinomial sobre o algoritmo clássico correspondente. Apesar de esses algoritmos darem comparáveis aumentos de velocidade quadráticas modestas, eles são aplicáveis amplamente e assim aceleram um amplo alcance de problemas.

### Eficiência do algoritmo de Grover

O algoritmo de Grover oferece uma vantagem quadrática sobre os algoritmos clássicos para problemas de busca não estruturada. Enquanto a busca clássica requer O(N) operações, o algoritmo de Grover requer aproximadamente O(√N) operações.
Os problemas de busca são fundamentais em computação, a computação quântica oferece uma maneira mais eficiente de lidar com eles, especialmente com o algoritmo de Grover. Este algoritmo demonstra como a superposição e a interferência quântica podem ser aproveitadas para realizar cálculos de forma mais eficiente do que é possível em computação clássica.

## Recozimento quântico

É um método da computação quântica utilizado para encontrar a melhor solução dentre várias possíveis. Encontra por meio do recozimento quântico o menor estado de energia possível.
Este processo normalmente retorna soluções com baixa energia, sendo que algumas aplicações requerem o mínimo de energia (otimizando problemas) e outras necessitam de níveis de energia extremamente baixos (problemas de amostragem probabilística).
Aplica-se o recozimento quântico em problemas de otimização, onde se procura o melhor em várias combinações, como enviar um pacote neste caminhão ou no próximo? A física pode resolver este problema, enquadrando-os como problemas de minimização de energia, já que, de acordo com a física, tudo tende a perseguir o estado de energia mínima, como a água quente esfriar, terá o mínimo de energia nela.
Cada estado pode ser representado por um nível de energia. Estes estados são simulados em um curto período de tempo, utilizando da superposição quântica e emaranhando qubits e a menor quantidade de energia é obtida, dando a melhor solução.
Por meio do tunelamento quântico, a transição entre estados é instantânea, sendo a transição entre níveis de energia não requere elétrons para “escalar” a barreira, eles somente atravessam-a. O tunelamento quântico é um fenômeno fundamental na física quântica que permite que partículas quânticas atravessem barreiras de potencial, mesmo que não tenham energia suficiente para superá-las de acordo com a física clássica. Princípio do tunelamento consiste em partículas quânticas, como elétrons, fótons e átomos, exibirem um comportamento ondulatório e são descritas por uma função de onda. Esta função de onda não descreve a localização precisa da partícula, mas sim uma distribuição de probabilidade de onde a partícula pode estar. Quando uma partícula se depara com uma barreira de potencial, há uma pequena, mas não nula, probabilidade de que ela atravesse essa barreira, mesmo que não tenha energia suficiente para superá-la de acordo com a física clássica. Na computação quântica, o tunelamento é utilizado em algoritmos quânticos, como o algoritmo de Grover, para buscar em espaços de busca de forma mais eficiente.
No contexto da criptografia quântica, o tunelamento é utilizado no estabelecimento de chaves de criptografia seguras. garante que qualquer tentativa de interceptação desses fótons seria detectada, garantindo assim a segurança da comunicação.
Seu potencial é resolver otimização combinada de problemas assim com o machine learning e otimizar rotas. Pode-se também calcular o ponto mínimo de uma função com várias variáveis.

### Problema da não linearidade

Consiste em modelagem de dados não lineares, onde algoritmos como regressão linear ou SVM (support vector machines) podem ter dificuldade em modelar relacionamentos não lineares entre variáveis de entrada e saída. Isso ocorre porque esses modelos são lineares por natureza e podem ter dificuldade em capturar a complexidade de dados não lineares, levando a baixo desempenho em determinadas tarefas. Seus desafios, no contexto do machine learning quântico, consiste na não linearidade, onde também pode ser um desafio. No entanto, os algoritmos quânticos têm uma estrutura diferente dos algoritmos clássicos e podem lidar com a não linearidade de maneira diferente.
Modelos quânticos não lineares são algoritmos de machine learning quântico, como os circuitos quânticos utilizados em algoritmos de aprendizado de variacionais quânticos (VQA), que podem capturar a não linearidade por meio da construção de circuitos quânticos complexos. Esses circuitos podem conter camadas de portas quânticas que introduzem não linearidades nos dados.