Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1703.05640 · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences

Two-dimensional translation-invariant probability distributions: approximations, characterizations and no-go theorems

Zizhu Wang, Miguel Navascués

Published Sep 1, 2018• 8 citations
arXivHTMLPDF

Abstract

We study the properties of the set of marginal distributions of infinite translation-invariant systems in the two-dimensional square lattice. In cases where the local variables can only take a small number d of possible values, we completely solve the marginal or membership problem for nearest-neighbours distributions ( d = 2, 3) and nearest and next-to-nearest neighbours distributions ( d = 2). Remarkably, all these sets form convex polytopes in probability space. This allows us to devise an algorithm to compute the minimum energy per site of any TI Hamiltonian in these scenarios exactly. We also devise a simple algorithm to approximate the minimum energy per site up to arbitrary accuracy for the cases not covered above. For variables of a higher (but finite) dimensionality, we prove two no-go results. To begin, the exact computation of the energy per site of arbitrary TI Hamiltonians with only nearest-neighbour interactions is an undecidable problem. In addition, in scenarios with d ≥2947, the boundary of the set of nearest-neighbour marginal distributions contains both flat and smoothly curved surfaces and the set itself is not semi-algebraic. This implies, in particular, that it cannot be characterized via semidefinite programming, even if we allow the input of the programme to include polynomials of nearest-neighbour probabilities.

DOI
10.1098/rspa.2017.0822

Related papers

Universal Translationally-Invariant Hamiltonians

Stephen Piddock, Johannes Bausch

In this work we extend the notion of universal quantum Hamiltonians to the setting of translationally-invariant systems. We present a construction that allows a two-dimensional spin lattice with nearest-neighbour interactions, open boundaries, and translational symmetry to simulate any local target Hamiltonian---i.e. to reproduce the whole of the target system within its low-energy subspace to arbitrarily-high precision. Since this implies the capability to simulate non-translationally-invariant many-body systems with translationally-invariant couplings, any effect such as characteristics commonly associated to systems with external disorder, e.g. many-body localization, can also occur within the low-energy Hilbert space sector of translationally-invariant systems. Then we sketch a variant of the universal lattice construction optimized for simulating translationally-invariant target Hamiltonians. Finally we prove that qubit Hamiltonians consisting of Heisenberg or XY interactions of varying interaction strengths restricted to the edges of a connected translationally-invariant graph embedded in $\mathbb{R}^D$ are universal, and can efficiently simulate any geometrically local Hamiltonian in $\mathbb{R}^D$.

arXiv:2001.08050•Jan 22, 2020•3 citations

Symmetrized Block-Product Periodic Marginals in Infinite Translation-Invariant Quantum Chains

Xiao Zeng, Kaiyan Yang, Lingxia Zhang +1 more

We study local marginals in one-dimensional translation-invariant quantum systems that may hide finite-period structure. Given an $n$-site reduced density matrix, we ask whether it can be obtained by repeating a finite $p$-site block state along the chain and averaging over the $p$ lattice translations. This defines a symmetrized block-product periodic marginal problem, which provides a route both to diagnosing hidden periodic order from local data and to upper bounding ground-state energy densities of infinite translation-invariant local Hamiltonians. We develop two complementary methods. The first is a semidefinite-programming relaxation based on block permutation symmetry and positive partial transpose constraints, which outer-approximates the convex hull of such marginals and yields certified infeasibility tests. The second is a symmetrized matrix product state ansatz, which constructs explicit block-product periodic states and gives variational upper bounds. We benchmark the framework on the Majumdar-Ghosh model, transverse-field Ising, XX, XXZ, and contextuality-related spin models. The results show that the method captures the expected finite-period structure in exactly solvable cases and gives systematically improving variational energies as the period and bond dimension increase. We also formulate a periodic-NPA relaxation for translation-invariant contextuality witnesses and recover the known quantum limits in the tested examples.

quant-pharXiv:2608.10365•Aug 12, 2026•0 citations

Entanglement marginal problems

Miguel Navascués, F. Baccari, Antonio Acín

We consider the entanglement marginal problem, which consists of deciding whether a number of reduced density matrices are compatible with an overall separable quantum state. To tackle this problem, we propose hierarchies of semidefinite programming relaxations of the set of quantum state marginals admitting a fully separable extension. We connect the completeness of each hierarchy to the resolution of an analog classical marginal problem and thus identify relevant experimental situations where the hierarchies are complete. For finitely many parties on a star configuration or a chain, we find that we can achieve an arbitrarily good approximation to the set of nearest-neighbour marginals of separable states with a time (space) complexity polynomial (linear) on the system size. Our results even extend to infinite systems, such as translation-invariant systems in 1D, as well as higher spatial dimensions with extra symmetries.

arXiv:2006.09064•Quantum•Nov 25, 2021•21 citations

Entanglement and Nonlocality in Infinite 1D Systems

Zizhu Wang, Sukhwinder Singh, Miguel Navascués

We consider the problem of detecting entanglement and nonlocality in one-dimensional (1D) infinite, translation-invariant (TI) systems when just near-neighbor information is available. This issue is deeper than one might think a priori, since, as we show, there exist instances of local separable states (classical boxes) which admit only entangled (nonclassical) TI extensions. We provide a simple characterization of the set of local states of multiseparable TI spin chains and construct a family of linear witnesses which can detect entanglement in infinite TI states from the nearest-neighbor reduced density matrix. Similarly, we prove that the set of classical TI boxes forms a polytope and devise a general procedure to generate all Bell inequalities which characterize it. Using an algorithm based on matrix product states, we show how some of them can be violated by distant parties conducting identical measurements on an infinite TI quantum state. All our results can be easily adapted to detect entanglement and nonlocality in large (finite, not TI) 1D condensed matter systems.

arXiv:1608.03485•Physical Review Letters•Jun 8, 2017•28 citations

Entanglement and Nonlocality of 1D Macroscopic Systems

Zizhu Wang, Sukhwinder Singh, Miguel Navascués

We consider the problem of certifying entanglement and nonlocality in one-dimensional macroscopic systems when just averaged near-neighbor correlators are available. We map this question to the characterization of the set of all quantum states (distributions) which admit a separable (classical) Translation-Invariant (TI) extension to infinitely many sites. We advance the first problem by constructing a family of witnesses which can detect entanglement in infinite TI states from the nearest-neighbor reduced density matrix. Along the way, we identify a set of separable twoqubit states which only admit entangled TI extensions. For nonlocality detection, we show that the set of classical TI boxes forms a polytope and devise a general procedure to generate all Bell inequalities which characterize it. Through a Matrix Product State-based method, we show how some of them can be violated by distant parties conducting identical measurements on an infinite TI quantum state.

•Aug 11, 2016•0 citations

Uncomputable finite-size gap exponents

Seth Douglas, Nidhal Mghirbi

We classify the nonnegative finite-size spectral-gap exponents of translation-invariant nearest-neighbour Hamiltonians on the square lattice, with finite local dimension, integer interaction matrices and open boundaries. The gap is measured above the entire ground space on an $L\times L$ box. The existing exponents in $\Delta(L)=L^{-z+o(1)}$ are exactly the nonnegative limit-computable ($\Delta^0_2$) reals. The finite nonnegative lower/upper exponent pairs are exactly the ordered pairs consisting of a left-$\Sigma^0_2$ real and a left-$\Pi^0_2$ real. In particular, one fixed integer-valued model has exponent equal to the halting probability of any chosen prefix-universal machine. A classical boundary preference fixes a size counter and a computation tableau; a reversible mixed-radix counter supplies the small gap. We bound every sector of the full Hilbert space. The closing modes live on a boundary segment of length $O(\log L)$, and the local dimension may depend on the prescribed pair. These are finite-box exponents, with no assertion about bulk dispersion or stability of thermodynamic critical exponents.

•Oct 29, 2026•0 citations
We study the properties of the set of marginal distributions of infinite translation-invariant systems in the two-dimensional square lattice. In cases where the local variables can only take a small number d of possible values, we completely solve the marginal or membership problem for nearest-neighbours distributions ( d = 2, 3) and nearest and next-to-nearest neighbours distributions ( d = 2). Remarkably, all these sets form convex polytopes in probability space. This allows us to devise an algorithm to compute the minimum energy per site of any TI Hamiltonian in these scenarios exactly. We also devise a simple algorithm to approximate the minimum energy per site up to arbitrary accuracy for the cases not covered above. For variables of a higher (but finite) dimensionality, we prove two no-go results. To begin, the exact computation of the energy per site of arbitrary TI Hamiltonians with only nearest-neighbour interactions is an undecidable problem. In addition, in scenarios with d ≥2947, the boundary of the set of nearest-neighbour marginal distributions contains both flat and smoothly curved surfaces and the set itself is not semi-algebraic. This implies, in particular, that it cannot be characterized via semidefinite programming, even if we allow the input of the programme to include polynomials of nearest-neighbour probabilities.
In this work we extend the notion of universal quantum Hamiltonians to the setting of translationally-invariant systems. We present a construction that allows a two-dimensional spin lattice with nearest-neighbour interactions, open boundaries, and translational symmetry to simulate any local target Hamiltonian---i.e. to reproduce the whole of the target system within its low-energy subspace to arbitrarily-high precision. Since this implies the capability to simulate non-translationally-invariant many-body systems with translationally-invariant couplings, any effect such as characteristics commonly associated to systems with external disorder, e.g. many-body localization, can also occur within the low-energy Hilbert space sector of translationally-invariant systems. Then we sketch a variant of the universal lattice construction optimized for simulating translationally-invariant target Hamiltonians. Finally we prove that qubit Hamiltonians consisting of Heisenberg or XY interactions of varying interaction strengths restricted to the edges of a connected translationally-invariant graph embedded in RD\mathbb{R}^DRD are universal, and can efficiently simulate any geometrically local Hamiltonian in RD\mathbb{R}^DRD.
We study local marginals in one-dimensional translation-invariant quantum systems that may hide finite-period structure. Given an nnn-site reduced density matrix, we ask whether it can be obtained by repeating a finite ppp-site block state along the chain and averaging over the ppp lattice translations. This defines a symmetrized block-product periodic marginal problem, which provides a route both to diagnosing hidden periodic order from local data and to upper bounding ground-state energy densities of infinite translation-invariant local Hamiltonians. We develop two complementary methods. The first is a semidefinite-programming relaxation based on block permutation symmetry and positive partial transpose constraints, which outer-approximates the convex hull of such marginals and yields certified infeasibility tests. The second is a symmetrized matrix product state ansatz, which constructs explicit block-product periodic states and gives variational upper bounds. We benchmark the framework on the Majumdar-Ghosh model, transverse-field Ising, XX, XXZ, and contextuality-related spin models. The results show that the method captures the expected finite-period structure in exactly solvable cases and gives systematically improving variational energies as the period and bond dimension increase. We also formulate a periodic-NPA relaxation for translation-invariant contextuality witnesses and recover the known quantum limits in the tested examples.
We consider the entanglement marginal problem, which consists of deciding whether a number of reduced density matrices are compatible with an overall separable quantum state. To tackle this problem, we propose hierarchies of semidefinite programming relaxations of the set of quantum state marginals admitting a fully separable extension. We connect the completeness of each hierarchy to the resolution of an analog classical marginal problem and thus identify relevant experimental situations where the hierarchies are complete. For finitely many parties on a star configuration or a chain, we find that we can achieve an arbitrarily good approximation to the set of nearest-neighbour marginals of separable states with a time (space) complexity polynomial (linear) on the system size. Our results even extend to infinite systems, such as translation-invariant systems in 1D, as well as higher spatial dimensions with extra symmetries.
We consider the problem of detecting entanglement and nonlocality in one-dimensional (1D) infinite, translation-invariant (TI) systems when just near-neighbor information is available. This issue is deeper than one might think a priori, since, as we show, there exist instances of local separable states (classical boxes) which admit only entangled (nonclassical) TI extensions. We provide a simple characterization of the set of local states of multiseparable TI spin chains and construct a family of linear witnesses which can detect entanglement in infinite TI states from the nearest-neighbor reduced density matrix. Similarly, we prove that the set of classical TI boxes forms a polytope and devise a general procedure to generate all Bell inequalities which characterize it. Using an algorithm based on matrix product states, we show how some of them can be violated by distant parties conducting identical measurements on an infinite TI quantum state. All our results can be easily adapted to detect entanglement and nonlocality in large (finite, not TI) 1D condensed matter systems.
We consider the problem of certifying entanglement and nonlocality in one-dimensional macroscopic systems when just averaged near-neighbor correlators are available. We map this question to the characterization of the set of all quantum states (distributions) which admit a separable (classical) Translation-Invariant (TI) extension to infinitely many sites. We advance the first problem by constructing a family of witnesses which can detect entanglement in infinite TI states from the nearest-neighbor reduced density matrix. Along the way, we identify a set of separable twoqubit states which only admit entangled TI extensions. For nonlocality detection, we show that the set of classical TI boxes forms a polytope and devise a general procedure to generate all Bell inequalities which characterize it. Through a Matrix Product State-based method, we show how some of them can be violated by distant parties conducting identical measurements on an infinite TI quantum state.
We classify the nonnegative finite-size spectral-gap exponents of translation-invariant nearest-neighbour Hamiltonians on the square lattice, with finite local dimension, integer interaction matrices and open boundaries. The gap is measured above the entire ground space on an L×LL\times LL×L box. The existing exponents in Δ(L)=L−z+o(1)\Delta(L)=L^{-z+o(1)}Δ(L)=L−z+o(1) are exactly the nonnegative limit-computable (Δ20\Delta^0_2Δ20​) reals. The finite nonnegative lower/upper exponent pairs are exactly the ordered pairs consisting of a left-Σ20\Sigma^0_2Σ20​ real and a left-Π20\Pi^0_2Π20​ real. In particular, one fixed integer-valued model has exponent equal to the halting probability of any chosen prefix-universal machine. A classical boundary preference fixes a size counter and a computation tableau; a reversible mixed-radix counter supplies the small gap. We bound every sector of the full Hilbert space. The closing modes live on a boundary segment of length O(log⁡L)O(\log L)O(logL), and the local dimension may depend on the prescribed pair. These are finite-box exponents, with no assertion about bulk dispersion or stability of thermodynamic critical exponents.