BQP é apenas sobre o tempo? Isso é significativo?

A classe de complexidade BQP (tempo polinomial quântico com erro delimitado) parece ser definida apenas considerando o fator tempo. Isso é sempre significativo? Existem algoritmos onde o tempo computacional é escalonado polinomialmente com o tamanho da entrada, mas outros recursos, como a memória, são escalonados exponencialmente?

O BQP é definido considerando o tamanho do circuito , ou seja, o número total de portas. Isso significa que ele incorpora:

• Número de qubits - porque podemos ignorar quaisquer qubits que não são acionados por um portão. Isso será polinomialmente delimitado em relação ao tamanho da entrada, e geralmente um polinômio modesto (por exemplo, o algoritmo de Shor envolve apenas um número de qubits, que é um fator constante vezes o tamanho da entrada).
• Profundidade do circuito (ou 'tempo') - porque o maior tempo que a computação pode demorar é se executarmos uma porta após a outra, sem executar nenhuma operação em paralelo.
• Comunicação com sistemas de controle - porque os portões que estão sendo executados são retirados de algum conjunto finito de portas e, mesmo que permitamos medições intermediárias, a quantidade de comunicação necessária para indicar o resultado da medição e a quantidade de computação necessária para determinar o que será feito a seguir geralmente é uma constante para cada operação.
• Interações entre sistemas quânticos - mesmo se considerarmos uma arquitetura que não possui interações todos-para-todos ou algo próximo, podemos simular a conectividade realizando operações SWAP explícitas, que podem ser decompostas em um número constante de dois operações de qubit. Isso pode nos dar uma sobrecarga polinomial perceptível que afeta a praticidade de um algoritmo para uma determinada arquitetura, mas não oculta uma quantidade exponencial de trabalho.
• Energia - novamente porque os circuitos são decompostos em um conjunto finito de portas, não há maneira óbvia de obter uma velocidade aparente "fazendo os portões mais rápidos" ou ocultando o trabalho em uma interação exótica, se o nosso limite for em termos de o número de operações realizadas a partir de um conjunto bastante básico de operações. Essa consideração é mais importante na computação quântica adiabática: não podemos tentar evitar pequenas lacunas apenas amplificando todo o cenário energético o quanto quisermos - o que significa que devemos levar mais tempo para fazer a computação, correspondendo na imagem do circuito a um circuito com mais portões.

De fato, contar o número de portas de um conjunto de tamanho constante captura muitas coisas com as quais você pode se preocupar como recursos práticos: deixa muito pouco espaço para esconder qualquer coisa que seja secretamente muito cara.

$O(1)$

$O(1)$

Penso que é mais claro que contar operações elementares é uma medida fundamental e importante do número de recursos exigidos por um algoritmo, pois sempre podemos decidir quantos recursos cada operação elementar exige.

Enquanto na definição de BQP e para algoritmos quânticos consideramos a complexidade do circuito em vez da 'complexidade da operação', a complexidade do circuito pode ser novamente definida em termos de operações em máquinas de Turing, portanto o mesmo raciocínio se aplica.