O problema P vs. NP se tornaria trivial como resultado do desenvolvimento de computadores quânticos universais?

Se alguém construísse um computador quântico universal, isso teria alguma implicação no problema de P vs. NP?

Não, não haverá absolutamente nenhuma implicação, por várias razões:

1. O problema P vs. NP é mais sobre computação clássica do que sobre computação quântica. Mesmo que computadores quânticos possam resolver problemas difíceis de NP em tempo polinomial (o que não esperamos que eles sejam capazes de fazer), ainda assim pode ser o caso que computadores clássicos não possam resolvê-los em tempo polinomial.

2. Computadores quânticos universais, em um sentido teórico, são (até onde sei) já conhecidos. Estes são apenas os análogos quânticos das máquinas universais de Turing: eles podem executar qualquer "programa" quântico.

3. Tanto a computação quântica quanto o problema P vs. NP são noções teóricas. O que alguém pode construir no mundo físico não tem absolutamente nenhuma influência em nada que tenha a ver com eles.

Lieuwe Vinkhuijzen deu uma interpretação diferente da sua pergunta:

Os computadores quânticos serão capazes de resolver problemas de NP-complete com eficiência?

A resposta esperada é: não. Portanto, mesmo nesse sentido, os computadores quânticos físicos não nos permitem resolver problemas completos de NP à vontade.

Nenhuma implicação é conhecida de qualquer maneira: a simulação clássica de computadores quânticos não nos diz nada sobre a dificuldade dos problemas de pesquisa de NP; soluções rápidas para problemas de pesquisa NP não nos dizem nada sobre a rapidez com que computadores quânticos podem ser simulados classicamente. Os seguintes cenários são possíveis:

• $P=NP=BQP$
• $P=NP\subsetneq BQP$
• $P\subsetneq NP=BQP$
• $P\subsetneq NP\subsetneq BQP$
• , P ⊊ B Q P, mas B Q P e N P são incomparáveis$P\subsetneq NP$$P\subsetneq BQP$$BQP$$NP$
• Os problemas de NP requerem força bruta classicamente, mas são resolvidos por algoritmos quânticos rápidos (embora não necessariamente polinomiais)

O blog de um influente cientista da computação quântica, Scott Aaronson, tem o cabeçalho " Se você pegar apenas uma informação deste blog: os computadores quânticos não resolveriam problemas de pesquisa instantânea, apenas tentando todas as soluções de uma só vez ".

Em um cenário (considerado improvável), construir um computador quântico universal teria de fato implicações no problema de P vs. NP.

Isso está se expandindo no caso mencionado por Yuval Filmus, "se os computadores quânticos pudessem resolver problemas difíceis de NP em tempo polinomial".

Em tal situação, construir um computador quântico universal versus apenas raciocinar teoricamente sobre um teria implicações para o problema P vs NP. Isso permitiria a possibilidade de usar apenas computadores quânticos para pesquisar / encontrar uma prova que resolvesse P vs NP, que poderia então ser verificada por um computador clássico.

No entanto, como mencionado nas outras respostas, embora não haja provas que separem BQP e NP-complete, atualmente as evidências e as expectativas são de que os computadores quânticos não serão capazes de resolver os problemas de NP-complete com eficiência.