English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

All known examples confirming the possibility of an exponential separationbetween classical simulation algorithms and stoquastic adiabatic quantumcomputing (AQC) exploit symmetries that constrain adiabatic dynamics toeffective, symmetric subspaces. The symmetries produce large effectiveeigenvalue gaps, which in turn make adiabatic computation efficient. We presenta classical algorithm to efficiently sample from the effective subspace of a$k$-local stoquastic Hamiltonian $H$, without a priori knowledge of itssymmetries (or near-symmetries). Our algorithm maps any $k$-local Hamiltonianto a graph $G=(V,E)$ with $\lvert V \rvert = O\left(\mathrm{poly}(n)\right)$where $n$ is the number of qubits. Given the well-known result of Babai, weexploit graph isomorphism to study the automorphisms of $G$ and arrive at analgorithm quasi-polynomial in $\lvert V\rvert$ for producing samples from theeffective subspace eigenstates of $H$. Our results rule out exponentialseparations between stoquastic AQC and classical computation that arise fromhidden symmetries in $k$-local Hamiltonians. Furthermore, our graphrepresentation of $H$ is not limited to stoquastic Hamiltonians and may ruleout corresponding obstructions in non-stoquastic cases, or be useful instudying additional properties of $k$-local Hamiltonians.

Effective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians