Teoria da complexidade quântica é o subcampo da teoria da complexidade computacional que lida com classes de complexidade definidas usando computadores quânticos, um modelo de computação baseado na mecânica quântica. Ela estuda a dificuldade de problemas computacionais em relação a essas classes de complexidade, bem como a relação entre classes de complexidade quântica e classes de complexidade clássicas (isto é, não quânticas).

Duas classes de complexidade quântica importantes são BQP e QMA.

Antecedentes

Uma classe de complexidade é uma coleção de problemas computacionais que podem ser resolvidos por um modelo computacional sob certas restrições de recursos. Por exemplo, a classe de complexidade P é definida como o conjunto de problemas solucionáveis por uma Máquina de Turing (determinística) em tempo polinomial. Similarmente, classes de complexidade quântica podem ser definidas usando modelos quânticos de computação, como o modelo de circuitos quânticos ou a Máquina de Turing quântica equivalente. Um dos principais objetivos da teoria da complexidade quântica é descobrir como essas classes se relacionam com classes de complexidade clássicas como P, NP, BPP e PSPACE.

Uma das razões pelas quais a teoria da complexidade quântica é estudada são as implicações da computação quântica para a tese de Church–Turing moderna. Em suma, a tese de Church–Turing moderna afirma que qualquer modelo computacional pode ser simulado em tempo polinomial por uma máquina de Turing probabilística. No entanto, questões em torno da tese de Church–Turing surgem no contexto da computação quântica. Não está claro se a tese de Church–Turing se sustenta para o modelo de computação quântica. Há muitas evidências de que a tese não se sustenta. Pode não ser possível para uma máquina de Turing probabilística simular modelos de computação quântica em tempo polinomial.

As complexidades computacionais assintóticas de algoritmos quânticos e algoritmos clássicos são frequentemente expressas com notação assintótica. Algumas formas comuns de notação assintótica de funções são , e . expressa que algo é limitado superiormente por , onde é uma constante tal que e é uma função de ; expressa que algo é limitado inferiormente por ; e expressa ambos e . Essas notações também têm seus próprios nomes. é chamada de notação grande O, é chamada de notação grande Omega e é chamada de notação grande Theta.

Visão geral das classes de complexidade As classes de complexidade importantes P, BPP, BQP, PP e PSPACE podem ser comparadas com base em problemas de promessa. Um problema de promessa é um problema de decisão cuja entrada é assumida como sendo selecionada do conjunto de todas as cadeias de entrada possíveis. Um problema de promessa é um par , onde é o conjunto de instâncias sim, é o conjunto de instâncias não, e a interseção desses conjuntos é vazia: . Todas as classes de complexidade anteriores contêm problemas de promessa. +Classe de ComplexidadeCritérioPProblemas de promessa para os quais uma máquina de Turing determinística de tempo polinomial aceita todas as cadeias em e rejeita todas as cadeias em BPPProblemas de promessa para os quais uma máquina de Turing probabilística de tempo polinomial aceita toda cadeia em com probabilidade de pelo menos , e aceita toda cadeia em com probabilidade de no máximo BQPProblemas de promessa tais que para funções , existe uma família gerada em tempo polinomial de circuitos quânticos , onde é um circuito que aceita qubits e dá uma saída de um qubit. Um elemento de é aceito por com probabilidade maior ou igual a . Um elemento de é aceito por com probabilidade menor ou igual a .PPProblemas de promessa para os quais uma máquina de Turing probabilística de tempo polinomial aceita toda cadeia em com probabilidade maior que , e aceita toda cadeia em com probabilidade de no máximo PSPACEProblemas de promessa para os quais uma máquina de Turing determinística que executa em espaço polinomial aceita toda cadeia em e rejeita todas as cadeias em

BQP

+Algoritmo BQP (1 execução) ≥ 2/3 ≤ 1/3 ≤ 1/3 ≥ 2/3

A classe de problemas que podem ser resolvidos eficientemente por um computador quântico com erro limitado é chamada BQP ("erro limitado, quântico, tempo polinomial"). Mais formalmente, BQP é a classe de problemas que podem ser resolvidos por uma máquina de Turing quântica de tempo polinomial com probabilidade de erro de no máximo 1/3.

Como uma classe de problemas probabilísticos, BQP é a contraparte quântica de BPP ("erro limitado, probabilístico, tempo polinomial"), a classe de problemas que podem ser resolvidos eficientemente por máquinas de Turing probabilísticas com erro limitado. Sabe-se que e é amplamente suspeito, mas não provado, que , o que intuitivamente significaria que computadores quânticos são mais poderosos que computadores clássicos em termos de complexidade de tempo.Nielsen, p. 201 BQP é um subconjunto de PP.

A relação exata de BQP com P, NP e PSPACE não é conhecida. No entanto, sabe-se que ; isto é, a classe de problemas que podem ser resolvidos eficientemente por computadores quânticos inclui todos os problemas que podem ser resolvidos eficientemente por computadores clássicos determinísticos, mas não inclui nenhum problema que não possa ser resolvido por computadores clássicos com recursos de espaço polinomial. Suspeita-se ainda que BQP é um superconjunto próprio de P, o que significa que existem problemas que são resolvíveis eficientemente por computadores quânticos, mas não 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 suspeita-se que estejam fora de P. Sobre a relação de BQP com NP, pouco se sabe além do fato de que alguns problemas NP estão em BQP (fatoração de inteiros e o problema do logaritmo discreto estão ambos em NP, por exemplo). Suspeita-se que ; ou seja, acredita-se que existem problemas verificáveis eficientemente que não são resolúveis eficientemente por um computador quântico. Como consequência direta dessa crença, suspeita-se também que BQP é disjunto da classe de problemas NP-completos (se algum problema NP-completo estivesse em BQP, então decorreria da dureza NP que todos os problemas em NP estão em BQP).

A relação de BQP com as classes de complexidade clássicas essenciais pode ser resumida como:

Sabe-se também que BQP está contido na classe de complexidade (ou mais precisamente na classe associada de problemas de decisão ), que é um subconjunto de PSPACE.

Simulação de circuitos quânticos Não há maneira conhecida de simular eficientemente um modelo computacional quântico com um computador clássico. Isso significa que um computador clássico não pode simular um modelo computacional quântico em tempo polinomial. No entanto, um circuito quântico de qubits com portas quânticas pode ser simulado por um circuito clássico com portas clássicas. Esse número de portas clássicas é obtido determinando quantas operações de bit são necessárias para simular o circuito quântico. Para fazer isso, primeiro as amplitudes associadas aos qubits devem ser consideradas. Cada um dos estados dos qubits pode ser descrito por um vetor complexo bidimensional, ou vetor de estado. Esses vetores de estado também podem ser descritos como uma combinação linear de seus vetores componentes com coeficientes chamados amplitudes. Essas amplitudes são números complexos normalizados para um, o que significa que a soma dos quadrados dos valores absolutos das amplitudes deve ser um. As entradas do vetor de estado são essas amplitudes. As amplitudes, atuando como coeficientes na descrição da combinação linear, cada uma corresponde a um componente não nulo do vetor de estado. Como uma equação, isso é descrito como ou usando a notação de Dirac. O estado de todo o sistema de qubits pode ser descrito por um único vetor de estado. Esse vetor de estado que descreve todo o sistema é o produto tensorial dos vetores de estado que descrevem os qubits individuais no sistema. O resultado dos produtos tensoriais dos qubits é um único vetor de estado que tem dimensões e entradas que são as amplitudes associadas a cada estado base ou vetor componente. Portanto, amplitudes devem ser consideradas com um vetor complexo de dimensões, que é o vetor de estado para o sistema de qubits. Para obter um limite superior para o número de portas necessárias para simular um circuito quântico, precisamos de um limite superior suficiente para a quantidade de dados usados para especificar a informação sobre cada uma das amplitudes. Para isso, bits de precisão são suficientes para codificar cada amplitude. Portanto, são necessários bits clássicos para considerar o vetor de estado do sistema de qubits. Em seguida, a aplicação das portas quânticas nas amplitudes deve ser considerada. As portas quânticas podem ser representadas como matrizes esparsas . Assim, para considerar a aplicação de cada uma das portas quânticas, o vetor de estado deve ser multiplicado por uma matriz esparsa para cada uma das portas quânticas. Cada vez que o vetor de estado é multiplicado por uma matriz esparsa , operações aritméticas devem ser realizadas. Portanto, há operações de bit para cada porta quântica aplicada ao vetor de estado. Assim, portas clássicas são necessárias para simular um circuito de qubits com apenas uma porta quântica. Portanto, portas clássicas são necessárias para simular um circuito quântico de qubits com portas quânticas. Embora não haja maneira conhecida de simular eficientemente um computador quântico com um computador clássico, é possível simular eficientemente um computador clássico com um computador quântico. Isso é evidente pelo fato de que .

Complexidade de consulta quântica Uma das principais vantagens de usar um sistema computacional quântico em vez de um clássico é que um computador quântico pode ser capaz de fornecer um algoritmo de tempo polinomial para algum problema para o qual nenhum algoritmo clássico de tempo polinomial existe, mas mais importante, um computador quântico pode diminuir significativamente o tempo de cálculo para um problema que um computador clássico já pode resolver eficientemente. Essencialmente, um computador quântico pode determinar quanto tempo levará para resolver um problema, enquanto um computador clássico pode ser incapaz de fazê-lo, e também pode melhorar muito a eficiência computacional associada à solução de um problema específico. A complexidade de consulta quântica refere-se a quão complexo, ou quantas consultas ao grafo associado à solução de um problema particular, são necessárias para resolver o problema. Antes de nos aprofundarmos na complexidade de consulta, consideremos alguns antecedentes sobre grafos de soluções para problemas particulares e as consultas associadas a essas soluções.

Modelos de consulta de grafos direcionados Um tipo de problema que a computação quântica pode tornar mais fácil de resolver são os problemas de grafos. Se considerarmos a quantidade de consultas a um grafo que são necessárias para resolver um determinado problema, consideremos primeiro os tipos mais comuns de grafos, chamados grafos direcionados, que estão associados a este tipo de modelagem computacional. Em resumo, grafos direcionados são grafos onde todas as arestas entre vértices são unidirecionais. Grafos direcionados são formalmente definidos como o grafo , onde N é o conjunto de vértices, ou nós, e E é o conjunto de arestas.

Modelo da matriz de adjacência Ao considerar a computação quântica da solução de problemas de grafos direcionados, existem dois modelos de consulta importantes para entender. Primeiro, há o modelo de matriz de adjacência, onde o grafo da solução é dado pela matriz de adjacência: , com , se e somente se .

Modelo do array de adjacência