Source author record

Stephen Piddock

Stephen Piddock appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

quant-ph Computational Complexity

Catalog footprint

What is connected

5works

2topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

General conditions for universality of Quantum Hamiltonians

Recent work has demonstrated the existence of universal Hamiltonians - simple spin lattice models that can simulate any other quantum many body system to any desired level of accuracy. Until now proofs of universality have relied on explicit constructions, tailored to each specific family of universal Hamiltonians. In this work we go beyond this approach, and completely classify the simulation ability of quantum Hamiltonians by their complexity classes. We do this by deriving necessary and sufficient complexity theoretic conditions characterising universal quantum Hamiltonians. Although the result concerns the theory of analogue Hamiltonian simulation - a promising application of near-term quantum technology - the proof relies on abstract complexity theoretic concepts and the theory of quantum computation. As well as providing simplified proofs of previous Hamiltonian universality results, and offering a route to new universal constructions, the results in this paper give insight into the origins of universality. For example, finally explaining the previously noted coincidences between families of universal Hamiltonian and classes of Hamiltonians appearing in complexity theory.

preprint2022arXiv

Termwise versus globally stoquastic local Hamiltonians: questions of complexity and sign-curing

We elucidate the distinction between global and termwise stoquasticity for local Hamiltonians and prove several complexity results. We show that the stoquastic local Hamiltonian problem is $\textbf{StoqMA}$-complete even for globally stoquastic Hamiltonians. We study the complexity of deciding whether a local Hamiltonian is globally stoquastic or not. In particular, we prove $\textbf{coNP}$-hardness of deciding global stoquasticity in a fixed basis and $Σ_2^p$-hardness of deciding global stoquasticity under single-qubit transformations. As a last result, we expand the class of sign-curing transformations by showing how Clifford transformations can sign-cure a class of disordered 1D $XYZ$ Hamiltonians.

preprint2020arXiv

Hardness and Ease of Curing the Sign Problem for Two-Local Qubit Hamiltonians

We examine the problem of determining whether a multi-qubit two-local Hamiltonian can be made stoquastic by single-qubit unitary transformations. We prove that when such a Hamiltonian contains one-local terms, then this task can be NP-hard. This is shown by constructing a class of Hamiltonians for which performing this task is equivalent to deciding $3$-SAT. In contrast, we show that when such a Hamiltonian contains no one-local terms then this task is easy, namely we present an algorithm which decides, in a number of arithmetic operations over $\mathbb{R}$ which is polynomial in the number of qubits, whether the sign problem of the Hamiltonian can be cured by single-qubit rotations.

preprint2020arXiv

Universal Translationally-Invariant Hamiltonians

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$.

preprint2015arXiv

The complexity of antiferromagnetic interactions and 2D lattices

Estimation of the minimum eigenvalue of a quantum Hamiltonian can be formalised as the Local Hamiltonian problem. We study the natural special case of the Local Hamiltonian problem where the same 2-local interaction, with differing weights, is applied across each pair of qubits. First we consider antiferromagnetic/ferromagnetic interactions, where the weights of the terms in the Hamiltonian are restricted to all be of the same sign. We show that for symmetric 2-local interactions with no 1-local part, the problem is either QMA-complete or in StoqMA. In particular the antiferromagnetic Heisenberg and antiferromagnetic XY interactions are shown to be QMA-complete. We also prove StoqMA-completeness of the antiferromagnetic transverse field Ising model. Second, we study the Local Hamiltonian problem under the restriction that the interaction terms can only be chosen to lie on a particular graph. We prove that nearly all of the QMA-complete 2-local interactions remain QMA-complete when restricted to a 2D square lattice. Finally we consider both restrictions at the same time and discover that, with the exception of the antiferromagnetic Heisenberg interaction, all of the interactions which are QMA-complete with positive coefficients remain QMA-complete when restricted to a 2D triangular lattice.