2026-07-23T08:48:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10400 2024-03-06T10:46:45Z ddc:004 open_access

A Compressed Classical Description of Quantum States Gosset, David Smolin, John Quantum computation Quantum communication complexity Classical simulation We show how to approximately represent a quantum state using the square root of the usual amount of classical memory. The classical representation of an n-qubit state psi consists of its inner products with O(sqrt{2^n}) stabilizer states. A quantum state initially specified by its 2^n entries in the computational basis can be compressed to this form in time O(2^n poly(n)), and, subsequently, the compressed description can be used to additively approximate the expectation value of an arbitrary observable. Our compression scheme directly gives a new protocol for the vector in subspace problem with randomized one-way communication complexity that matches (up to polylogarithmic factors) the optimal upper bound, due to Raz. We obtain an exponential improvement over Raz’s protocol in terms of computational efficiency. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Gosset and John Smolin 2019 Is Part Of LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2019.8 urn:nbn:de:0030-drops-104005 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.8 eng https://creativecommons.org/licenses/by/3.0/legalcode