skip to main content
Idioma:

Limitations of quantum advice and one-way communication

Aaronson, S.

Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004, 2004, p.320-332

Los Alamitos CA: IEEE

Texto completo disponível

Citações Citado por
  • Título:
    Limitations of quantum advice and one-way communication
  • Autor: Aaronson, S.
  • Assuntos: Boolean functions ; Classical and quantum physics: mechanics and fields ; Complexity theory ; Exact sciences and technology ; Fingerprint recognition ; Physics ; Physics computing ; Polynomials ; Protocols ; Quantum communication ; Quantum computing ; Quantum information ; Quantum mechanics ; Sorting ; Teleportation
  • É parte de: Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004, 2004, p.320-332
  • Descrição: Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP/qpoly /spl sube/ PP/poly, where BQP/qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size "quantum advice state " that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which NP /spl nsub/ BQP/qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has many other applications; for example, it can be used to fix and even improve on a flawed result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols.
  • Editor: Los Alamitos CA: IEEE
  • Idioma: Inglês
Links
Voltar para lista de resultados
Ir para página anteriorAnterior Resultado  2 AvançarIr para próxima página

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.