Se P = NP fosse verdadeiro, os computadores quânticos seriam úteis?

29

Suponha que P = NP seja verdadeiro. Haveria alguma aplicação prática na construção de um computador quântico, como resolver certos problemas mais rapidamente, ou alguma melhoria seria irrelevante com base no fato de P = NP ser verdadeiro? Como você caracterizaria a melhoria da eficiência que aconteceria se um computador quântico pudesse ser construído em um mundo onde P = NP, em oposição a um mundo em que P! = NP?

Aqui está um exemplo inventado sobre o que estou procurando:

Se P! = NP, vemos que a classe de complexidade ABC é igual à classe de complexidade quântica XYZ ... mas se P = NP, a classe ABC entra em colapso na classe relacionada UVW de qualquer maneira.

(Motivação: estou curioso sobre isso e relativamente novo na computação quântica; migre esta questão se ela não estiver suficientemente avançada.)

Philip White
fonte
9
Não sabemos se implica B Q P = P , de modo que possa haver algum problema em B Q P que não esteja em P, mesmo que P = N P .... Também é uma questão em aberto se ou não B Q P é em P H ....P=NPBQP=PBQPPP=NPBQPPH
Tayfun Pagamento
4
Mais basicamente, a classe captura algoritmos quânticos "eficientes" (tempo polinomial quântico com erro delimitado). É por isso que a formalização da sua pergunta por Tayfun é natural, por exemplo, se P = N P , ainda existem problemas ainda em P , mas em B Q P ? E, aparentemente, é consistente com o nosso conhecimento atual que isso acontece. BQPP=NPPBQP
usul

Respostas:

30

O artigo " BQP e a hierarquia polinomial " de Scott Aaronson aborda diretamente sua pergunta. Se P = NP, o PH entraria em colapso. Se, além disso, o BQP estivesse em PH, não seria possível uma aceleração quântica nesse caso. Por outro lado, Aaronson fornece evidências de um problema com a aceleração quântica fora da HP, portanto, essa aceleração sobreviveria ao colapso da HP.

Martin Schwarz
fonte
10
Na verdade, o próprio Aaronson provou que a conjectura de que ele se baseava nesse trabalho é falsa. Veja scottaaronson.com/papers/glnfalse.pdf
Alex Grilo
5
@AlexGrilo Alguns dos resultados no artigo foram incondicionais e ainda permanecem: existe uma separação entre oracle entre as versões relacionais do BQP e PH.
Sasho Nikolov
8
Um esclarecimento: embora a "Conjectura Linial-Nisan Generalizada" tenha sido falsa, a conjectura de que o problema da Verificação de Fourier / "Relação de Relação" não está no PH ainda permanece. É apenas que alguma outra abordagem será necessária para provar isso. Além disso, posso reforçar meu resultado de que existe um oráculo em relação ao qual existem problemas de relação BQP que não estão no BPP ^ PH, para mostrar que existe um oráculo em relação ao qual P = NP, mas ainda existem problemas na relação de BQP que não estão no BPP . É uma extensão direta, mas infelizmente ainda não a escrevi.
22815 Scott Aronson
9

A resposta é um inequívoco sim. Computadores quânticos definitivamente ainda seriam úteis.

Computadores quânticos não são oráculos para o BQP, mas dispositivos que processam estados quânticos e podem se comunicar usando estados quânticos. Assim como a capacidade de fazer consultas não determinísticas é fundamentalmente mais poderosa do que a capacidade de fazer consultas puramente determinísticas, independentemente do status de P vs NP (e, de fato, essa é a raiz das separações do oráculo), a capacidade de fazer consultas quânticas e se comunicar usando estados quânticos é fundamentalmente mais poderoso que o equivalente puramente clássico.

Isso leva a vantagens em uma ampla gama de aplicações

  1. A capacidade de consultar oráculos ou bancos de dados externos em superposição fornece uma separação comprovável entre computadores quânticos e computadores clássicos em termos de complexidade de consultas.
  2. Há uma variedade de tarefas de comunicação que vêem reduções drásticas no custo de comunicação, sendo utilizada a comunicação quântica.
  3. O processamento quântico de informações permite protocolos de informações teoricamente seguras para uma ampla gama de problemas do que é classicamente possível. Certamente, o QKD não requer que um computador quântico universal seja implementado, mas muitos protocolos para outras tarefas exigem.
  4. O pré e pós-processamento de grandes estados quânticos emaranhados permite violar o limite de ruído de tiro na metrologia, resultando em medições mais precisas.

Além dos argumentos de complexidade, há outro motivo prático para querer computadores quânticos. Atualmente, muitos dos dados processados ​​em computadores clássicos são derivados da detecção do mundo natural (por exemplo, através do CCD em uma câmera digital). No entanto, essas medições necessariamente descartam algumas informações sobre o sistema, a fim de renderizar o resultado da medição como uma sequência de bits clássica (por exemplo, colapsando superposições espaciais de fótons), e nem sempre é claro que informação será considerada mais importante quando inicialmente gravando os dados. Portanto, é razoável acreditar que a capacidade de armazenar e processar estados quânticos diretamente, em vez de colapsá-los em alguma base antes do processamento, se tornará cada vez mais desejável.

Joe Fitzsimons
fonte
4

Abordando a parte prática.

P=NPO(n2103)

O(n1010000)

Até onde eu sei, o computador quântico suficientemente poderoso será de interesse prático neste caso.

joro
fonte
n2103
@SashoNikolov eu me dirigi prático . O computador quântico que fatorar inteiros de 2048 bits com eficiência seria de interesse prático para mim a partir de agora por causa das chaves RSA;).
joro
Acredito que é possível obter algoritmos lineares de classificação de tempo com computadores quânticos.
Baby Dragon
2

Existem estudos na relação entre o BQP e a hierarquia polinomial da HP. Por exemplo, há um problema relativo ao qual o BQP não está contido no PH ( http://arxiv.org/abs/0910.4698 ) e uma conjectura que comprova o mesmo resultado em um mundo não relativizado ( http://arxiv.org /abs/1007.0305P#PBPPPH

Em conclusão, não sabemos qual é o poder exato dos computadores quânticos, mas há resultados sugerindo que o BQP pode estar fora do PH.

neófito
fonte