Distribuições de probabilidade de profundidade limitada

Duas perguntas relacionadas à computação em profundidade limitada:

1) Suponha que você comece com n bits e, para começar com o bit i, pode ser 0 ou 1 com alguma probabilidade p (i), independentemente. (Se isso simplificar o problema, podemos assumir que todos os p (i) s são 0,1 ou 1/2.ou mesmo que todos eles sejam 1/2.)

Agora você faz um número limitado de rodadas de computação. Em cada rodada, você aplica portões clássicos reversíveis em conjuntos de bits separados. (Corrija seu conjunto favorito de portões reversíveis clássicos universais.)

No final, você obtém uma distribuição de probabilidade em strings em n bits. Existem resultados sobre a restrição de tais distribuições?

Eu estou olhando para algo análogo ao Hastad chaveando-me, o resultado de Boppana é que a influência total é pequena ou o teorema do LMN.

2) A mesma pergunta que 1) mas com circuitos quânticos de profundidade limitada.

Existem alguns trabalhos relativamente recentes de Emanuele Viola et al., Que tratam da complexidade das distribuições de amostras. Eles se concentram no modelo restrito de cálculos, como árvores de decisão de profundidade limitada ou circuitos de profundidade limitada.

Infelizmente, eles não discutem portões reversíveis. Pelo contrário, muitas vezes há perda no comprimento da saída. No entanto, esses documentos podem ser um bom ponto de partida.

Circuitos com profundidade limitada não podem obter exemplos de bons códigos

A complexidade das distribuições

Resposta curta.

Para circuitos quânticos, há pelo menos um resultado de não- limitação: é improvável que os circuitos quânticos de profundidade limitada arbitrária sejam simuláveis ​​com pequeno erro multiplicativo na probabilidade do resultado, mesmo para circuitos clássicos com profundidade polinomial .

$\mathsf{QNC^0}$

Detalhes

Podemos considerar a definição de circuitos quânticos de profundidade polilogênica, conforme dada por Fenner et al. (2005) :

$\mathsf{QNC^k}$$\{C_n\}_{n\geqslant0}$$p$$C_n$$n$$p(n)$$O(\log^k(n))$

As portas de um qubit único devem ser de um conjunto finito fixo, embora isso seja suficiente para simular qualquer unidade fixa em um número constante de qubits para qualquer precisão fixa. Também permitimos que qualquer subconjunto de qubits no final do circuito seja usado para representar a saída da família de circuitos (por exemplo, um único qubit para funções booleanas).

Bremner, Jozsa e Sheppard (2010) observam (consulte a Seção 4) que, usando uma adaptação da técnica de teletransporte de porta devido a Terhal e DiVincenzo (2004) , pós-seleção em alguns dos qubits em um permite resolver problemas em . Usando seus resultados na simulação de circuitos pós-selecionados, isso implica que o problema de amostragem clássica da distribuição de saída de um circuito arbitrário com saída booleana, com erro multiplicativo no máximo na probabilidade de amostragem, está em impossível com circuitos aleatórios de profundidade polinomial, a menos que a hierarquia polinomial colapsar parcialmente (especificamente$\mathsf{QNC^0}$$\mathsf{PostBQP = PP}$$\mathsf{QNC^0}$$\sqrt 2$$\mathsf{PH} \subseteq \Delta_3$ ).