Que nível de "confiança" do resultado de um computador quântico é possível?

Em um nível muito básico, ler ou medir um qubit obriga a estar em um estado ou outro, de modo que a operação de um computador quântico para obter um resultado colapsa o estado em uma das muitas possibilidades.

Mas como o estado de cada qubit é probabilístico, certamente isso significa que o resultado pode realmente ser qualquer uma dessas possibilidades, com probabilidade variável. Se eu executar novamente o programa - devo esperar ver resultados diferentes?

Como posso ter certeza de que tenho o "melhor" resultado? O que fornece essa confiança? Presumo que não possam ser as medidas intermediárias, conforme descrito nesta pergunta, pois elas não reduzem a saída.

A maioria dos algoritmos úteis / relativamente eficientes ¹ para computadores quânticos pertence à classe de complexidade 'tempo de polinômio quântico com erro de limite' (BQP) . Por essa definição, você deseja que a 'taxa de falhas' de qualquer algoritmo quântico seja ouP(sucesso)$\leq\frac{1}{3}$ , embora o resultado ainda possa estar dentro de um pequeno erro. Um algoritmo não probabilístico (que pode ser executado em tempo polinomial) ainda estará nessa classe de complexidade, com a única diferença:$\mathbb{P}\left(\text{success}\right) \geq \frac{2}{3}$ sempre retorna o resultado correto ² .

No entanto, como você pode executar um algoritmo um número arbitrário de vezes, isso equivale a ter uma probabilidade de sucesso de pelo menos para uma entrada de comprimentone qualquer constante positivac.$\frac{1}{2} + n^{-c}$$n$$c$

Portanto, o resultado 'correto' é o que aparece pelo menos dois terços do tempo, a menos que você queira um cálculo 'one-shot', como se você deseja gerar números aleatórios ou se deseja fazer algo como referência o chip quântico, onde as estatísticas são importantes e fazem parte do 'resultado'.

Além desses (ou de outros algoritmos que não possuem um único 'resultado correto'), se você encontrar um algoritmo com uma taxa de sucesso abaixo da metade, ele não será mais um 'erro limitado' e poderá não ser possível para o usuário para saber o resultado correto - pode haver simplesmente uma resposta errada com maior probabilidade de ocorrer do que a correta.

Sim, você pode ver um resultado diferente cada vez que executa um cálculo. A confiança no resultado é fornecida por:

1. O próprio algoritmo quântico assegura que o resultado correto aconteça com alta probabilidade e;
2. Repetindo o algoritmo várias vezes para encontrar o resultado mais provável.

^{1 Aqui, algoritmos que podem ser computados em tempo polinomial para fornecer uma solução com 'alta probabilidade', embora, para os fins desta resposta, a complexidade do tempo seja de menor importância}

^{2 Bem, idealisticamente, pelo menos}

Elaborando um pouco Mithrandir24601da resposta de

O recurso com o qual você está preocupado, que um computador quântico pode produzir uma resposta diferente na próxima execução do cálculo, também é um recurso do cálculo aleatório. De certa forma, é bom poder obter uma única resposta repetidamente, mas, no final, basta obter uma resposta correta com confiança suficiente. Assim como em um algoritmo aleatório, o importante é que você possa ter certeza das chances de obter a resposta correta em qualquer execução da computação.

Por exemplo, seu computador quântico pode fornecer a resposta correta para uma pergunta SIM / NÃO duas vezes a cada três. Isto pode parecer um mau desempenho, mas o que isto significa é que se você executá-lo muitas vezes, você pode simplesmente tomar a resposta da maioria e ser muito confiante de que a regra da maioria dá-lhe a resposta correta. (O mesmo vale para o cálculo aleatório normal também.) A maneira como a confiança aumenta com o número de runas significa que, desde que qualquer uma delas dê uma resposta que tenha significativamente mais do que apenas 50% de chance de estar correta, você pode ter sua confiança o mais alta possível apenas executando um número modesto de execuções repetidas (embora sejam necessárias mais execuções, mais próximas as chances de uma resposta correta em qualquer execução são de 50%).

$\mathrm{poly}(n)$$n$ seqüência de bits, onde a resposta é corrigir com probabilidade de pelo menos 2/3; pelo argumento acima, o mesmo conjunto exato de problemas é fornecido se você exigir que a resposta seja correta com probabilidade 999/1000 ou (1 - 1e-8).

Para problemas que têm respostas mais elaboradas do que perguntas SIM / NÃO, não podemos necessariamente assumir que a mesma resposta será produzida mais de uma vez, para que possamos votar por maioria. (Se você estiver usando um computador quântico para obter amostras de um número exponencial de resultados, é possível que exista uma quantidade menor, mas ainda exponencial de muitas respostas corretas e úteis!) Suponha que você esteja tentando resolver um problema de otimização: pode não ser fácil verificar se você encontrou a solução ideal ou uma solução quase ideal - ou se a resposta que você obteve é ​​a melhor que o computador quântico pode fazer (e se a próxima execução lhe der uma melhor resposta por acaso?). Nesse caso, o importante é determinar o que você sabe sobre o problema,NP , o que significa que você pode, em princípio, verificar com eficiência qualquer resposta que você receber?) E com qual qualidade de solução você ficaria feliz.

Novamente, isso também é verdade para algoritmos aleatórios - a diferença é que esperamos que os computadores quânticos sejam capazes de resolver problemas que apenas um computador aleatório não poderia resolver facilmente.

$15$$3\times5$

É uma boa linha, especialmente com a batida oportuna de Aaronson, e o público sempre parece rir um pouco, mas é claro que todos sabemos que isso é uma pequena simplificação excessiva da natureza probabilística do algoritmo de Shor.

$15$$3$$15$$5$$15=3\times 5$

$\mathsf{FACTORING}$$\mathrm{BQP}\cap\mathrm{NP}$$\mathrm{BQP}$ para gerar soluções candidatas, mas sempre podemos testar classicamente se as supostas soluções do computador quântico estão corretas.

$\mathrm{BQP}$$\mathrm{NP}$

(Eu sei que já existem duas ótimas respostas; no entanto, a pergunta permite exposição / esclarecimento sobre a citação / aneto de Aaronson.)