Complexidade computacional da óptica quântica

Em "Requisito para computação quântica" , Bartlett e Sanders resumem alguns dos resultados conhecidos para computação quântica variável contínua na tabela a seguir:

MINHA pergunta é tripla:

1. Nove anos depois, a última célula pode ser preenchida?
2. Se uma coluna for adicionada com o título "Universal for BQP", como seria o restante da coluna?
3. A obra-prima de 95 páginas de Aaronson e Arkhipov pode ser resumida em uma nova linha?

Com relação à sua terceira pergunta, Aaronson e Arkhipov (A&A por brevidade) usam uma construção da computação quântica óptica linear muito intimamente relacionada à construção da KLM. Em particular, consideram o caso de fótons não interagentes idênticos em um espaço dos modos poli ( n ) ≥ m ≥ n , iniciando no estado inicial | 1 n ⟩ = | 1 , ... , 1 , 0 , ... , 0 $n$$\text{poly}(n) \ge m \ge n$ Além disso, A & A permitir beamsplitters e phaseshifters, que são suficientes para gerar todos m × m operadores unitários no espaço de modos (importante, porém, não no espaço de estado total do sistema). A medição é realizada contando o número de fótons em cada modo, produzindo uma tupla ( s 1 , s 2 , … , s m ) de números de ocupação de modo que ∑ i s i = n e s i ≥ 0 para cada

Assim, no idioma da tabela, o modelo A&A BosonSampling provavelmente seria melhor descrito como " fótons, óptica linear e contagem de fótons". Embora a eficiência clássica da amostragem desse modelo seja, a rigor, desconhecida, a capacidade de amostrar classicamente do modelo de A&A implicaria um colapso da hierarquia polinomial. Como qualquer colapso do PH é geralmente considerado extremamente improvável, não é exagero dizer que o BosonSampling provavelmente não é simulável de forma eficiente e clássica.$n$

$1/16^\Gamma$$\Gamma$

Aaronson explora o caso da óptica linear pós-selecionada mais em seu artigo de acompanhamento sobre a dureza # P da permanente. Esse resultado foi comprovado anteriormente por Valiant, mas Aaronson apresenta uma nova prova baseada no teorema da KLM. Como uma observação lateral, acho que este artigo faz uma introdução muito agradável a muitos dos conceitos que a A&A usa em sua obra-prima BosonSampling.

$\cos^2(\frac\pi8)$

1. Eu acredito que é justo dizer que a última entrada na tabela é um "X" devido à Computação Quântica com Clusters Variáveis ​​Contínuas por Gu et al . Eles mostram que estados de cluster não gaussianos podem ser afetados por medições homodinas para UQC.
2. A coluna hipotética "Universal para BQP" teria um "X" para a primeira linha e "verificações" para descanso - exceto a linha hipotética no resultado de Aaronson e Arkhipov, que teria um "?" (embora seja provavelmente um "X" de acordo com os autores).
3. Veja a resposta de Chris Granade acima.

UPDATE: Eu também deveria ter perguntado se novas linhas podem ser adicionadas. De qualquer forma, é possível:

Isso é de Veitch et al . Veja também Mari e Eisert .