De onde vem a vantagem quântica?

Dando um passo atrás, podemos perguntar por que converter problemas de otimização em problemas de decodificação deveria ser vantajoso em primeiro lugar? Ao compreender isso mais profundamente, pode-se esperar obter intuição para orientar a busca por problemas de otimização adicionais nos quais os computadores quânticos possam oferecer vantagem.

Tanto os problemas de otimização com os quais começamos quanto os problemas de decodificação nos quais os convertemos são algo chamado Problemas NP-difíceis. Isto sugere que é impossível encontrar de forma eficiente soluções exatas para todas as instâncias destes problemas, mesmo com a ajuda de computadores quânticos. Ao usar efeitos quânticos, o DQI converteu um problema difícil em outro problema difícil. Como isso consegue alguma coisa? A chave é que a dureza NP fala da dificuldade do casos muito difíceis de um determinado problema. Se as instâncias do problema estiverem restritas a ter alguma estrutura adicional, isso pode torná-los mais fáceis. A promessa do DQI é que certos tipos de estrutura podem tornar o problema de decodificação muito mais fácil, sem também tornar o problema de otimização mais fácil de resolver usando computadores convencionais.

No problema OPI, a rede que surge é estruturada algebricamente; as componentes dos vetores de base, em vez de serem arbitrárias, são obtidas elevando um número a potências sucessivamente superiores. Essa estrutura algébrica se reflete tanto no problema de otimização original (OPI) quanto no problema de decodificação em que os computadores quânticos podem convertê-lo (decodificação Reed-Solomon). Essa estrutura facilita muito o problema de decodificação, mas até onde sabemos não facilita o problema de otimização para computadores convencionais. Nesta circunstância, a capacidade de converter o problema de otimização em problema de decodificação, utilizando o poder da computação quântica, oferece vantagem.