Sobre oráculos e problemas insolúveis

Sobre os algoritmos quânticos, e a tal da “vantagem quântica”, um ponto que sempre me incomodou (e a todos que conheço), foi a parte do oráculo.

Por exemplo, o algoritmo de Grover. Supostamente, o esforço computacional tem ordem raiz(N), o que é melhor do que o método tradicional (ordem N).

São raiz(N) chamadas a um oráculo, uma caixa-preta, que processa e dá a resposta. Um porém é que raiz(N) despreza o esforço computacional do oráculo.

Parece que este truque empurra a sujeira para debaixo do tapete.

Ainda mais que o oráculo tem que ter uma série de particularidades. Por exemplo, ele tem que aceitar uma entrada quântica, particularmente, a sobreposição de todos os inputs de entrada.

Ora, se o oráculo demorar N passos para calcular a sobreposição de N entradas, no total o tempo será N*raiz(N), ou seja, vantagem alguma.

Mas, pensando bem, há uma lógica. E é mais ou menos a mesma razão pela qual os carros elétricos podem fazer sentido.

O ponto fraco dos carros elétricos

Também sempre achei estranha a ideia de que carros elétricos vão salvar o planeta. Isto porque, em quase todos os lugares do mundo, a eletricidade vem de uma matriz energética à base de carvão, petróleo, energia nuclear ou outra fonte não renovável.

Se olhar só para o carro elétrico, é fácil falar que é eficiente, mas, no todo, será que vale a pena?

Um ponto em defesa deste, é que um carro elétrico consegue uma taxa muito alta de conversão de energia em movimento. A eficiência de um carro elétrico é de 85% a 90%.

Num carro tradicional, esta parte é convertida em barulho e calor, apenas uns 20% é convertida em movimento.

Para ser justo, teria que colocar na conta a eficiência de conversão do carvão (ou outra fonte) em eletricidade, e perdas na transmissão, mas mesmo assim, é promissor.

A conta só fecha mesmo se tiver, do outro lado da linha, formas renováveis de produzir eletricidade. Energia eólica, solar, hidrelétricas. Ter carro elétrico é um estímulo a mais para que surjam tais fontes renováveis.

Ou seja, o carro elétrico é uma parte da resposta, à espera de que haja avanços significativos em outras áreas.

Sobre problemas insolúveis

Quando temos um problema insolúvel, uma alternativa é falar que não temos solução possível. Ponto final. Mas falar que o problema é insolúvel não ajuda muito.

Outra alternativa é separar o problema em partes, resolver parte do problema, e apostar que as outras partes serão resolvidas num futuro próximo.

É como tentar alcançar um muro alto, e ir construindo pedaços da escada.

Sabemos que o Grover necessita de raiz(N) chamadas ao oráculo. Uma parte do problema é construir o algoritmo de Grover. Outra parte é construir um oráculo que aceite uma sobreposição de todas as alternativas na entrada e resolva o problema de forma eficiente. Construir a caixa-preta.

Muitos outros problemas foram surgindo assim. Digamos, o Youtube, no início, parecia uma loucura. Streaming de vídeo, quando a grande maioria das pessoas tinha conexão discada?

O dia em que o problema do oráculo for efetivamente resolvido, a conta vai fechar, e o desempenho finalmente será assombroso.

Sobre oráculos

O oráculo era uma pessoa que conseguia consultar os deuses e dar uma resposta à uma pergunta difícil. As respostas eram dadas em forma de versos e nem sempre eram muito claras.

Tem um história de um rei, que perguntou o que aconteceria se ele atacasse a Pérsia. O oráculo disse que um reino seria destruído.

Feliz da vida, o rei atacou a Pérsia, sofreu uma derrota apavorante, e voltou a consultar o oráculo. Ele perguntou: “Mas você não disse que a Pérsia seria destruída”.

O oráculo retrucou: “Eu disse que um reino seria destruído, e um reino foi destruído”.

Trilha sonora: Johan Sebastian Bach, Minueto em G minor,

Interpretação de Ji-Hae Park

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google

Você está comentando utilizando sua conta Google. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s