Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA compressed classical description of quantum states
112
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 mathrm{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 Razs protocol in terms of computational efficiency.
rate research
Read More
We present a classical interactive protocol that verifies the validity of a quantum witness state for the local Hamiltonian problem. It follows from this protocol that approximating the non-local value of a multi-player one-round game to inverse polynomial precision is QMA-hard. Our work makes an interesting connection between the theory of QMA-completeness and Hamiltonian complexity on one hand and the study of non-local games and Bell inequalities on the other.
We construct a quantum oracle relative to which $mathsf{BQP} = mathsf{QMA}$ but cryptographic pseudorandom quantum states and pseudorandom unitary transformations exist, a counterintuitive result in light of the fact that pseudorandom states can be broken by quantum Merlin-Arthur adversaries. We explain how this nuance arises as the result of a distinction between algorithms that operate on quantum and classical inputs. On the other hand, we show that some computational complexity assumption is needed to construct pseudorandom states, by proving that pseudorandom states do not exist if $mathsf{BQP} = mathsf{PP}$. We discuss implications of these results for cryptography, complexity theory, and quantum tomography.
We consider the task of estimating the expectation value of an $n$-qubit tensor product observable $O_1otimes O_2otimes cdots otimes O_n$ in the output state of a shallow quantum circuit. This task is a cornerstone of variational quantum algorithms for optimization, machine learning, and the simulation of quantum many-body systems. Here we study its computational complexity for constant-depth quantum circuits and three types of single-qubit observables $O_j$ which are (a) close to the identity, (b) positive semidefinite, (c) arbitrary. It is shown that the mean value problem admits a classical approximation algorithm with runtime scaling as $mathrm{poly}(n)$ and $2^{tilde{O}(sqrt{n})}$ in cases (a,b) respectively. In case (c) we give a linear-time algorithm for geometrically local circuits on a two-dimensional grid. The mean value is approximated with a small relative error in case (a), while in cases (b,c) we satisfy a less demanding additive error bound. The algorithms are based on (respectively) Barvinoks polynomial interpolation method, a polynomial approximation for the OR function arising from quantum query complexity, and a Monte Carlo method combined with Matrix Product State techniques. We also prove a technical lemma characterizing a zero-free region for certain polynomials associated with a quantum circuit, which may be of independent interest.
A locking protocol between two parties is as follows: Alice gives an encrypted classical message to Bob which she does not want Bob to be able to read until she gives him the key. If Alice is using classical resources, and she wants to approach unconditional security, then the key and the message must have comparable sizes. But if Alice prepares a quantum state, the size of the key can be comparatively negligible. This effect is called quantum locking. Entanglement does not play a role in this quantum advantage. We show that, in this scenario, the quantum discord quantifies the advantage of the quantum protocol over the corresponding classical one for any classical-quantum state.
We give a pedagogical introduction of the stochastic variational method and show that this generalized variational principle describes classical and quantum mechanics in a unified way.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
