A amostragem do bóson, às vezes estilizada como BosonSampling, é um problema candidato atraente para estabelecer a supremacia quântica; os problemas de engenharia parecem mais superáveis ​​do que aqueles associados a um computador quântico completo de Turing.

No entanto, o Boson Sampling tem uma desvantagem, pois a saída de um computador quântico fotônico capaz de executar o Boson Sampling com apenas um punhado ( ou mais) de qubits pode nem ser capaz de simular clasicamente. Isto é, é claro, ao contrário N P problemas tais como factoring, os aspectos de engenharia de que são significativamente mais difícil.$\le 100$$\mathsf{NP}$

Assim, podemos estabelecer os resultados do Boson de amostragem em ou assim fótons, mas a fim de verificar os resultados, precisamos calcular o permanente de um 100 × 100 matriz. É notoriamente difícil de verificar computacionalmente. $100$$100\times100$

Talvez um supercomputador poderoso o suficiente para calcular a permanente possa fazer o truque. Mas, em seguida, todos teriam de acreditar ambos os resultados do supercomputador e os resultados Boson de amostragem.

Existe algo sobre Boson Sampling que possa ser facilmente verificado?

Eu tive um vôo de fantasia para talvez colocar os recursos de uma rede de mineração de criptomoedas para usar para calcular uma permanente, e confiar em alguns truques / I P para verificação pública, mas não cheguei muito longe.$\mathsf{\#P}$$\mathsf{IP}$

EDITAR

Eu gosto da resposta do @ gIS.

$\mathsf{PCP}$

Sobre a necessidade de verificação por amostragem do bóson

Antes de mais, deixe-me salientar que não é uma necessidade estrita verificar a saída de um amostrador de bósons. Com isso, não pretendo dizer que não seja útil ou interessante tentar fazê-lo, mas sim que, em certo sentido, é mais uma necessidade prática do que fundamental.

Eu acho que você mesmo apresentou um bom argumento quando escreve

Talvez um supercomputador poderoso o suficiente para calcular a permanente possa fazer o truque. Mas então todos teriam que acreditar nos resultados do supercomputador e nos resultados da Amostragem do Bóson.

De fato, existem muitos casos em que alguém resolve um problema e confia em uma solução que realmente não pode ser totalmente verificada. Quero dizer, esqueça a mecânica quântica, basta usar seu computador para multiplicar dois grandes números. Você provavelmente tem uma grande confiança de que o resultado obtido está correto, mas como o verifica sem usar outro computador?

De maneira geral, a confiança nos resultados de um dispositivo vem de várias coisas, como conhecimento do funcionamento interno do dispositivo e teste de unidade do próprio dispositivo (ou seja, teste de funcionamento correto para as instâncias especiais que você pode verificar). com algum outro método).

O problema da certificação de amostragem de bósons não é diferente. Sabemos que, em algum momento, não seremos capazes de verificar completamente a saída de um amostrador de bósons, mas isso não significa que não seremos capazes de confiar nela. Se o dispositivo for construído com a devida precisão, e sua saída for verificada para uma variedade de pequenas instâncias, e outros testes que for possível executar forem todos bem-sucedidos, em algum momento, você ganhará confiança suficiente no dispositivo para criar uma a alegação de supremacia quântica (ou qualquer outra coisa que alguém queira usar o amostrador de bósons) é significativa.

Existe algo sobre BosonSampling que possa ser facilmente verificado?

Sim, existem propriedades que podem ser verificadas. Devido à natureza amostral do problema, o que as pessoas costumam fazer é descartar modelos alternativos que possam ter gerado as amostras observadas. Por exemplo, Aaronson e Arkhipov ( 1309.7460 ) mostraram que a distribuição BosonSampling está longe da distribuição uniforme na distância total de variação (com alta probabilidade sobre as matrizes aleatórias Haar que induzem a distribuição) e forneceu um protocolo para distinguir eficientemente as duas distribuições. Um trabalho mais recente, mostrando como as assinaturas estatísticas podem ser usadas para certificar a distribuição de amostras do bóson contra hipóteses alternativas, é ( Walschaers et al. 2014 ).

Todos os outros trabalhos que eu conheço se concentram na certificação de aspectos específicos de um amostrador de bósons, em vez de abordar diretamente o problema de encontrar distribuições alternativas que estão longe da BosonSampling para interferômetros aleatórios.

Mais especificamente, pode-se isolar duas principais fontes possíveis de erro em um aparelho de amostragem de bósons: as que surgem da implementação incorreta do interferômetro e as que surgem dos fótons de entrada não são o que deveriam (ou seja, totalmente indistinguíveis).

O primeiro caso é (relativamente) fácil de manusear, porque é possível caracterizar eficientemente um interferômetro usando fótons únicos. No entanto, certificar a indistinguibilidade dos fótons de entrada é mais complicado. Uma idéia para fazer isso é mudar o interferômetro para um não aleatório, como o interferômetro QFT, e verificar se algo pode ser verificado com eficiência nesse caso mais simples. Não tentarei adicionar todas as referências relevantes aqui, mas essa direção começou com (Tichy et al. 2010 , 2013 ).

Em relação ao aspecto da verificação pública, não há nada feito nessa direção que eu tenha ouvido falar. Também não tenho certeza se é mesmo uma direção particularmente significativa a ser explorada: por que deveríamos exigir um "alto padrão" de verificação para um amostrador de bósons, quando, para praticamente qualquer outro tipo de experimento, estamos satisfeitos em confiar nas pessoas que fazem o teste? experimentam ser bons no que estão fazendo?

Apenas um pequeno complemento à excelente resposta do @gIS: conheço várias pessoas (inclusive eu) interessadas no aspecto da verificação pública. Até onde eu sei, todas as tentativas falharam, daí a falta de literatura sobre o assunto: assim que se pode provar que o amostrador Boson agiu corretamente, é de fato um regime em que o amostrador Boson pode ser eficientemente simulado classicamente.

$IQP$$IQP$$P$