Como os bits quânticos aumentam o poder computacional?

Question

Sou novo na computação quântica, estou aprendendo a usar o Qiskit. Estou tentando entender melhor como exatamente as características quânticas do computador quântico ajudam a aumentar seu poder computacional. Pensei no seguinte exemplo: Se estou escrevendo um algoritmo de retrocesso, escrever este algoritmo usando algoritmos quânticos em um computador quântico me permite verificar muitos caminhos em paralelo, em vez de verificar todas as possibilidades em uma linha como aconteceria no computador clássico . É correto dizer isso?

Answer 1

Este é um conceito errado. Por exemplo, as pessoas tendem a dizer que o algoritmo de fatoração de Shor nos ajuda a calcular o fator primo exponencial mais rápido do que o computador clássico porque o computador quântico tentará todos os fatores possíveis simultaneamente e nos dará a resposta certa no final. Na realidade, o poder do algoritmo de Short é mais sutil do que isso. Levando em consideração o fato de que o computador quântico pode realizar certas tarefas de forma muito eficiente. Acontece que a "fatoração" pode ser dividida na questão de "determinação periódica" de uma determinada função. E quando você pensa em descoberta de período, uma ferramenta matemática que pode vir à mente é a transformada de Fourier, ou transformada discreta de Fourier (DFT). Acontece que o DFT pode ser executado de forma muito mais eficiente em um computador quântico do que o computador clássico, isso é conhecido como Transformada Quântica de Fourier. Esta é a chave por trás de muitos algoritmos quânticos, e não apenas o algoritmo de fatoração de Shor.

Devo mencionar que realizar a transformada de Fourier com mais eficiência em um computador quântico não significa que você pode apenas usá-la como faz classicamente. Ou seja, você não pode simplesmente usar QFT em qualquer algoritmo clássico que requeira uma transformada de Fourier e esperar uma aceleração. Isso ocorre porque não podemos acessar o estado quântico diretamente.$$QFT |\psi \rangle = |\phi \rangle$$ Você não pode ler o que $|\phi\rangle$é diretamente como postulado pela mecânica quântica. Isso faz parte do mundo privado do estado quântico. Além disso, preparando um estado arbitrário$|\psi\rangle$em um computador quântico é difícil. Todos os estados qubit são inicializados em$|0\rangle^{\otimes n}$. Portanto, você deve fazer alguma operação para levá-lo$|\psi \rangle$. Ainda não há uma maneira muito eficiente de fazer isso.