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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the complexity of a class of problems involving satisfyingconstraints which remain the same under translations in one or more spatialdirections. In this paper, we show hardness of a classical tiling problem on anN x N 2-dimensional grid and a quantum problem involving finding the groundstate energy of a 1-dimensional quantum system of N particles. In both cases,the only input is N, provided in binary. We show that the classical problem isNEXP-complete and the quantum problem is QMA_EXP-complete. Thus, an algorithmfor these problems which runs in time polynomial in N (exponential in the inputsize) would imply that EXP = NEXP or BQEXP = QMA_EXP, respectively. Althoughtiling in general is already known to be NEXP-complete, to our knowledge, allprevious reductions require that either the set of tiles and their constraintsor some varying boundary conditions be given as part of the input. In theproblem considered here, these are fixed, constant-sized parameters of theproblem. Instead, the problem instance is encoded solely in the size of thesystem.

The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems