BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Toby S. Cubitt

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

ResearcherUnclaimed source record
quant-phInformation Theorymath.ITmath-phmath.MPComputational Complexitycond-mat.othercond-mat.stat-mech

Catalog footprint

What is connected

18works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

18 published item(s)

preprint2021arXiv

Uncomputability of Phase Diagrams

The phase diagram of a material is of central importance to describe the properties and behaviour of a condensed matter system. We prove that the general task of determining the quantum phase diagram of a many-body Hamiltonian is uncomputable, by explicitly constructing a one-parameter family of Hamiltonians for which this is the case. This work builds off recent results from Cubitt et al. and Bausch et al., proving undecidability of the spectral gap problem. However, in all previous constructions, the Hamiltonian was necessarily a discontinuous function of its parameters, making it difficult to derive rigorous implications for phase diagrams or related condensed matter questions. Our main technical contribution is to prove undecidability of the spectral gap for a continuous, single-parameter family of translationally invariant, nearest-neighbour spin-lattice Hamiltonians on a 2D square lattice: $H(φ)$ where $φ\in \mathbb R$. As well as implying uncomputablity of phase diagrams, our result also proves that undecidability can hold for a set of positive measure of a Hamiltonian's parameter space, whereas previous results only implied undecidability on a zero measure set.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Comment on "On the uncomputability of the spectral gap"

The aim of this short note is to clarify some of the claims made in the comparison made in [S. Lloyd, On the uncomputability of the spectral gap, arXiv:1602.05924] between our recent result [T.S. Cubitt, D. Perez-Garcia, M.M. Wolf, Undecidability of the spectral gap, Nature 528, 207-211 (2015), arXiv:1502.04573] and his 1994 paper [S. Lloyd, Necessary and sufficient conditions for quantum computation, J. Mod. Opt. 41(12), 2503-2520 (1994)].

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Simple universal models capture all classical spin physics

Spin models are used in many studies of complex systems---be it condensed matter physics, neural networks, or economics---as they exhibit rich macroscopic behaviour despite their microscopic simplicity. Here we prove that all the physics of every classical spin model is reproduced in the low-energy sector of certain `universal models'. This means that (i) the low energy spectrum of the universal model reproduces the entire spectrum of the original model to any desired precision, (ii) the corresponding spin configurations of the original model are also reproduced in the universal model, (iii) the partition function is approximated to any desired precision, and (iv) the overhead in terms of number of spins and interactions is at most polynomial. This holds for classical models with discrete or continuous degrees of freedom. We prove necessary and sufficient conditions for a spin model to be universal, and show that one of the simplest and most widely studied spin models, the 2D Ising model with fields, is universal.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Universal Refocusing of Systematic Quantum Noise

Refocusing of a quantum system in NMR and quantum information processing can be achieved by application of short pulses according to the methods of spin echo and dynamical decoupling. However, these methods are strongly limited by the requirement that the evolution of the system between pulses be suitably small. Here we show how refocusing may be achieved for arbitrary (but time-independent) evolution of the system between pulses. We first illustrate the procedure with one-qubit systems, and then generalize to $d$-dimensional quantum systems. We also give an application of this result to quantum computation, proving a new version of the Solovay-Kitaev theorem that does not require inverse gates.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Rapid mixing and stability of quantum dissipative systems

The physics of many materials is modeled by quantum many-body systems with local interactions. If the model of the system is sensitive to noise from the environment, or small perturbations to the original interactions, it will not properly model the robustness of the real physical system it aims to describe, or be useful when engineering novel systems for quantum information processing. We show that local observables and correlation functions of local Liouvillians are stable to local perturbations if the dynamics is rapidly mixing and has a unique fixed point. No other condition is required.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Stability of local quantum dissipative systems

Open quantum systems weakly coupled to the environment are modeled by completely positive, trace preserving semigroups of linear maps. The generators of such evolutions are called Lindbladians. In the setting of quantum many-body systems on a lattice it is natural to consider Lindbladians that decompose into a sum of local interactions with decreasing strength with respect to the size of their support. For both practical and theoretical reasons, it is crucial to estimate the impact that perturbations in the generating Lindbladian, arising as noise or errors, can have on the evolution. These local perturbations are potentially unbounded, but constrained to respect the underlying lattice structure. We show that even for polynomially decaying errors in the Lindbladian, local observables and correlation functions are stable if the unperturbed Lindbladian has a unique fixed point and a mixing time which scales logarithmically with the system size. The proof relies on Lieb-Robinson bounds, which describe a finite group velocity for propagation of information in local systems. As a main example, we prove that classical Glauber dynamics is stable under local perturbations, including perturbations in the transition rates which may not preserve detailed balance.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A constructive commutative quantum Lovasz Local Lemma, and beyond

The recently proven Quantum Lovasz Local Lemma generalises the well-known Lovasz Local Lemma. It states that, if a collection of subspace constraints are "weakly dependent", there necessarily exists a state satisfying all constraints. It implies e.g. that certain instances of the kQSAT quantum satisfiability problem are necessarily satisfiable, or that many-body systems with "not too many" interactions are always frustration-free. However, the QLLL only asserts existence; it says nothing about how to find the state. Inspired by Moser's breakthrough classical results, we present a constructive version of the QLLL in the setting of commuting constraints, proving that a simple quantum algorithm converges efficiently to the required state. In fact, we provide two different proofs, one using a novel quantum coupling argument, the other a more explicit combinatorial analysis. Both proofs are independent of the QLLL. So these results also provide independent, constructive proofs of the commutative QLLL itself, but strengthen it significantly by giving an efficient algorithm for finding the state whose existence is asserted by the QLLL. We give an application of the constructive commutative QLLL to convergence of CP maps. We also extend these results to the non-commutative setting. However, our proof of the general constructive QLLL relies on a conjecture which we are only able to prove in special cases.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

An Information-Theoretic Proof of the Constructive Commutative Quantum Lovász Local Lemma

The Quantum Lovász Local Lemma (QLLL) [AKS12] establishes non-constructively that any quantum system constrained by a local Hamiltonian has a zero-energy ground state, if the local Hamiltonian terms overlap only in a certain restricted way. In this paper, we present an efficient quantum algorithm to prepare this ground state for the special case of commuting projector terms. The related classical problem has been open for more than 34 years. Our algorithm follows the breakthrough ideas of Moser's [Moser09] classical algorithm and lifts his information theoretic argument to the quantum setting. A similar result has been independently published by Arad and Sattath [AS13] recently.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Extracting dynamical equations from experimental data is NP-hard

The behavior of any physical system is governed by its underlying dynamical equations. Much of physics is concerned with discovering these dynamical equations and understanding their consequences. In this work, we show that, remarkably, identifying the underlying dynamical equation from any amount of experimental data, however precise, is a provably computationally hard problem (it is NP-hard), both for classical and quantum mechanical systems. As a by-product of this work, we give complexity-theoretic answers to both the quantum and classical embedding problems, two long-standing open problems in mathematics (the classical problem, in particular, dating back over 70 years).

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Preparing topological PEPS on a quantum computer

Simulating of exotic phases of matter that are not amenable to classical techniques is one of the most important potential applications of quantum information processing. We present an efficient algorithm for preparing a large class of topological quantum states -- the G-injective Projected Entangled Pair States (PEPS) -- on a quantum computer. Important examples include the resonant valence bond (RVB) states, conjectured to be topological spin liquids. The runtime of the algorithm scales polynomially with the condition number of the PEPS projectors, and inverse-polynomially in the spectral gap of the PEPS parent Hamiltonian.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

An Extreme form of Superactivation for Quantum Zero-Error Capacities

The zero-error capacity of a channel is the rate at which it can send information perfectly, with zero probability of error, and has long been studied in classical information theory. We show that the zero-error capacity of quantum channels exhibits an extreme form of non-additivity, one which is not possible for classical channels, or even for the usual capacities of quantum channels. By combining probabilistic arguments with algebraic geometry, we prove that there exist channels E1 and E2 with no zero-error classical capacity whatsoever, C_0(E1) = C_0(E2) = 0, but whose joint zero-error quantum capacity is positive, Q_0(E1 x E2) >= 1. This striking effect is an extreme from of the superactivation phenomenon, as it implies that both the classical and quantum zero-error capacities of these channels can be superactivated simultaneously, whilst being a strictly stronger property of capacities. Superactivation of the quantum zero-error capacity was not previously known.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Are problems in Quantum Information Theory (un)decidable?

This note is intended to foster a discussion about the extent to which typical problems arising in quantum information theory are algorithmically decidable (in principle rather than in practice). Various problems in the context of entanglement theory and quantum channels turn out to be decidable via quantifier elimination as long as they admit a compact formulation without quantification over integers. For many asymptotically defined properties which have to hold for all or for one integer N, however, effective procedures seem to be difficult if not impossible to find. We review some of the main tools for (dis)proving decidability and apply them to problems in quantum information theory. We find that questions like "can we overcome fidelity 1/2 w.r.t. a two-qubit singlet state?" easily become undecidable. A closer look at such questions might rule out some of the "single-letter" formulas sought in quantum information theory.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Entanglement can completely defeat quantum noise

We describe two quantum channels that individually cannot send any information, even classical, without some chance of decoding error. But together a single use of each channel can send quantum information perfectly reliably. This proves that the zero-error classical capacity exhibits superactivation, the extreme form of the superadditivity phenomenon in which entangled inputs allow communication over zero capacity channels. But our result is stronger still, as it even allows zero-error quantum communication when the two channels are combined. Thus our result shows a new remarkable way in which entanglement across two systems can be used to resist noise, in this case perfectly. We also show a new form of superactivation by entanglement shared between sender and receiver.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Superactivation of the Asymptotic Zero-Error Classical Capacity of a Quantum Channel

The zero-error classical capacity of a quantum channel is the asymptotic rate at which it can be used to send classical bits perfectly, so that they can be decoded with zero probability of error. We show that there exist pairs of quantum channels, neither of which individually have any zero-error capacity whatsoever (even if arbitrarily many uses of the channels are available), but such that access to even a single copy of both channels allows classical information to be sent perfectly reliably. In other words, we prove that the zero-error classical capacity can be superactivated. This result is the first example of superactivation of a classical capacity of a quantum channel.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Complexity of Relating Quantum Channels to Master Equations

Completely positive, trace preserving (CPT) maps and Lindblad master equations are both widely used to describe the dynamics of open quantum systems. The connection between these two descriptions is a classic topic in mathematical physics. One direction was solved by the now famous result due to Lindblad, Kossakowski Gorini and Sudarshan, who gave a complete characterisation of the master equations that generate completely positive semi-groups. However, the other direction has remained open: given a CPT map, is there a Lindblad master equation that generates it (and if so, can we find it's form)? This is sometimes known as the Markovianity problem. Physically, it is asking how one can deduce underlying physical processes from experimental observations. We give a complexity theoretic answer to this problem: it is NP-hard. We also give an explicit algorithm that reduces the problem to integer semi-definite programming, a well-known NP problem. Together, these results imply that resolving the question of which CPT maps can be generated by master equations is tantamount to solving P=NP: any efficiently computable criterion for Markovianity would imply P=NP; whereas a proof that P=NP would imply that our algorithm already gives an efficiently computable criterion. Thus, unless P does equal NP, there cannot exist any simple criterion for determining when a CPT map has a master equation description. However, we also show that if the system dimension is fixed (relevant for current quantum process tomography experiments), then our algorithm scales efficiently in the required precision, allowing an underlying Lindblad master equation to be determined efficiently from even a single snapshot in this case. Our work also leads to similar complexity-theoretic answers to a related long-standing open problem in probability theory.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Improving zero-error classical communication with entanglement

Given one or more uses of a classical channel, only a certain number of messages can be transmitted with zero probability of error. The study of this number and its asymptotic behaviour constitutes the field of classical zero-error information theory, the quantum generalisation of which has started to develop recently. We show that, given a single use of certain classical channels, entangled states of a system shared by the sender and receiver can be used to increase the number of (classical) messages which can be sent with no chance of error. In particular, we show how to construct such a channel based on any proof of the Bell-Kochen-Specker theorem. This is a new example of the use of quantum effects to improve the performance of a classical task. We investigate the connection between this phenomenon and that of ``pseudo-telepathy'' games. The use of generalised non-signalling correlations to assist in this task is also considered. In this case, a particularly elegant theory results and, remarkably, it is sometimes possible to transmit information with zero-error using a channel with no unassisted zero-error capacity.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Zero-error channel capacity and simulation assisted by non-local correlations

Shannon's theory of zero-error communication is re-examined in the broader setting of using one classical channel to simulate another exactly, and in the presence of various resources that are all classes of non-signalling correlations: Shared randomness, shared entanglement and arbitrary non-signalling correlations. Specifically, when the channel being simulated is noiseless, this reduces to the zero-error capacity of the channel, assisted by the various classes of non-signalling correlations. When the resource channel is noiseless, it results in the "reverse" problem of simulating a noisy channel exactly by a noiseless one, assisted by correlations. In both cases, 'one-shot' separations between the power of the different assisting correlations are exhibited. The most striking result of this kind is that entanglement can assist in zero-error communication, in stark contrast to the standard setting of communicaton with asymptotically vanishing error in which entanglement does not help at all. In the asymptotic case, shared randomness is shown to be just as powerful as arbitrary non-signalling correlations for noisy channel simulation, which is not true for the asymptotic zero-error capacities. For assistance by arbitrary non-signalling correlations, linear programming formulas for capacity and simulation are derived, the former being equal (for channels with non-zero unassisted capacity) to the feedback-assisted zero-error capacity originally derived by Shannon to upper bound the unassisted zero-error capacity. Finally, a kind of reversibility between non-signalling-assisted capacity and simulation is observed, mirroring the famous "reverse Shannon theorem".

0 citations0 reviewsNo code linkedOpen access