Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLimiting the complexity of quantum states: a toy theory
480
0
0.0
(
0
)
Authors
Valerio Scarani
Ask ChatGPT about the research
No Arabic abstract
This paper discusses a restriction of quantum theory, in which very complex states would be excluded. The toy theory is phrased in the language of the circuit model for quantum computing, its key ingredient being a limitation on the number of interactions that textit{each} qubit may undergo. As long as one stays in the circuit model, the toy theory is consistent and may even match what we shall be ever able to do in a controlled laboratory experiment. The direct extension of the restriction beyond the circuit model conflicts with observed facts: the possibility of restricting the complexity of quantum state, while saving phenomena, remains an open question.
rate research
Read More
We analyze relationships between quantum computation and a family of generalizations of the Jones polynomial. Extending recent work by Aharonov et al., we give efficient quantum circuits for implementing the unitary Jones-Wenzl representations of the braid group. We use these to provide new quantum algorithms for approximately evaluating a family of specializations of the HOMFLYPT two-variable polynomial of trace closures of braids. We also give algorithms for approximating the Jones polynomial of a general class of closures of braids at roots of unity. Next we provide a self-contained proof of a result of Freedman et al. that any quantum computation can be replaced by an additive approximation of the Jones polynomial, evaluated at almost any primitive root of unity. Our proof encodes two-qubit unitaries into the rectangular representation of the eight-strand braid group. We then give QCMA-complete and PSPACE-complete problems which are based on braids. We conclude with direct proofs that evaluating the Jones polynomial of the plat closure at most primitive roots of unity is a #P-hard problem, while learning its most significant bit is PP-hard, circumventing the usual route through the Tutte polynomial and graph coloring.
QMA (Quantum Merlin-Arthur) is the quantum analogue of the class NP. There are a few QMA-complete problems, most notably the ``Local Hamiltonian problem introduced by Kitaev. In this dissertation we show some new QMA-complete problems. The first one is ``Consistency of Local Density Matrices: given several density matrices describing different (constant-size) subsets of an n-qubit system, decide whether these are consistent with a single global state. This problem was first suggested by Aharonov. We show that it is QMA-complete, via an oracle reduction from Local Hamiltonian. This uses algorithms for convex optimization with a membership oracle, due to Yudin and Nemirovskii. Next we show that two problems from quantum chemistry, ``Fermionic Local Hamiltonian and ``N-representability, are QMA-complete. These problems arise in calculating the ground state energies of molecular systems. N-representability is a key component in recently developed numerical methods using the contracted Schrodinger equation. Although these problems have been studied since the 1960s, it is only recently that the theory of quantum computation has allowed us to properly characterize their complexity. Finally, we study some special cases of the Consistency problem, pertaining to 1-dimensional and ``stoquastic systems. We also give an alternative proof of a result due to Jaynes: whenever local density matrices are consistent, they are consistent with a Gibbs state.
Topological entanglement entropy has been extensively used as an indicator of topologically ordered phases. We study the conditions needed for two-dimensional topologically trivial states to exhibit spurious contributions that contaminates topological entanglement entropy. We show that if the state at the boundary of a subregion is a stabilizer state, then it has a non-zero spurious contribution to the region if and only if, the state is in a non-trivial one-dimensional $G_1times G_2$ symmetry-protected-topological (SPT) phase. However, we provide a candidate of a boundary state that has a non-zero spurious contribution but does not belong to any such SPT phase.
We consider a toy model for emergence of chaos in a quantum many-body short-range-interacting system: two one-dimensional hard-core particles in a box, with a small mass defect as a perturbation over an integrable system, the latter represented by two equal mass particles. To that system, we apply a quantum generalization of Chirikovs criterion for the onset of chaos, i.e. the criterion of overlapping resonances. There, classical nonlinear resonances translate almost verbatim to the quantum language. Quantum mechanics intervenes at a later stage: the resonances occupying less than one Hamiltonian eigenstate are excluded from the chaos criterion. Resonances appear as contiguous patches of low purity unperturbed eigenstates, separated by the groups of undestroyed states---the quantum analogues of the classical KAM tori.
The negative weight adversary method, $mathrm{ADV}^pm(g)$, is known to characterize the bounded-error quantum query complexity of any Boolean function $g$, and also obeys a perfect composition theorem $mathrm{ADV}^pm(f circ g^n) = mathrm{ADV}^pm(f) mathrm{ADV}^pm(g)$. Belovs gave a modified version of the negative weight adversary method, $mathrm{ADV}_{rel}^pm(f)$, that characterizes the bounded-error quantum query complexity of a relation $f subseteq {0,1}^n times [K]$, provided the relation is efficiently verifiable. A relation is efficiently verifiable if $mathrm{ADV}^pm(f_a) = o(mathrm{ADV}_{rel}^pm(f))$ for every $a in [K]$, where $f_a$ is the Boolean function defined as $f_a(x) = 1$ if and only if $(x,a) in f$. In this note we show a perfect composition theorem for the composition of a relation $f$ with a Boolean function $g$ [ mathrm{ADV}_{rel}^pm(f circ g^n) = mathrm{ADV}_{rel}^pm(f) mathrm{ADV}^pm(g) enspace . ] For an efficiently verifiable relation $f$ this means $Q(f circ g^n) = Theta( mathrm{ADV}_{rel}^pm(f) mathrm{ADV}^pm(g) )$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
