Problema de contagem aproximado na captura de BQP

No modelo de caixa preta, o problema de determinar a saída de uma máquina BPP na entrada é o problema de contagem aproximado de determinar com erro aditivo 1/3 (digamos).$M(x,r)$$x$$E_r M(x,r)$

Existe um problema semelhante para o BQP? Este comentário de Ken Regan sugere um problema

Você pode reduzir uma questão BPP para aproximar uma única função #P, mas com BQP que você recebe é a diferença de duas funções #P, chamá-los de e . Aproximando e separadamente não ajudá-lo aproximado quando é quase zero!$f$$g$$f$$g$$f - g$$f - g$

O BQP fornece uma pequena ajuda: quando a resposta à pergunta do BQP em uma entrada é sim, você obtém que está próximo da raiz quadrada de , onde a contagem predica a definição e têm m variáveis ​​binárias após você substituir . (Não há barras de valor absoluto; “magicamente” você sempre obtém . Sob representações comuns de circuitos quânticos para BQP, se torna o número de portas Hadamard.) Quando a resposta é não, a a diferença é próxima de 0.$x$$f(x) - g(x)$$2^m$$f$$g$$x$$f(x) > g(x)$$m$

Você pode formular com precisão esse problema o mais próximo possível do BQP? Espero algo como: dado acesso à caixa preta para as funções mapeando para , com a promessa de que ..., estime para dentro de .$f,g$$X$$Y$$f-g$$\varepsilon$

Emanuele: Infelizmente, não conhecemos nenhum problema de caixa preta ao capturar BQP tão simples quanto o que você mencionou ao capturar BPP.

Intuitivamente, isso ocorre porque é difícil falar sobre BQP sem trazer a unitariedade de uma forma ou de outra. A capacidade de somar números positivos e negativos é o que torna o BQP mais poderoso que o BPP, mas a unitariedade é o que torna o BQP menos poderoso que o #P! :-)

Dito isto, além de Dawson et al. No artigo a que Martin Schwarz vinculou, você definitivamente deveria verificar isso e isso por Janzing e Wocjan, que dão problemas de promessa "surpreendentemente clássicos" que capturam BQP.

Além disso, deixe S ⊆ {0,1} ⁿ e considere uma função booleana f: S → {0,1}. Então, eu tenho uma conjectura de anos atrás, que diz que Q (f), a complexidade da consulta quântica de erro delimitado de f, é polinomialmente relacionada ao grau mínimo de um polinômio real p: R ⁿ → R tal que

(i) p (x) ∈ [0,1] para todos os x∈ {0,1} ⁿ , e

(ii) | p (x) -f (x) | ≤ ε para todos os x∈S.

Se essa conjectura se mantiver, um "problema aproximado de contagem capturando BQP" seria simplesmente aproximar o valor de um polinômio polilog (n) de grau p: R ⁿ → R, em um ponto especificado no cubo booleano, dado que p é limitado em todos os lugares no cubo booleano. Isso pode ser o mais próximo possível da resposta à sua pergunta.

Este artigo elabora as idéias esboçadas acima em detalhes.