# Presentation: 118067

## Perturbative gadgets with constant-bounded interactions 

*Sergey Bravyi**1**David DiVincenzo**1**Daniel Loss**2** **Barbara Terhal**1*

*Classical and Quantum Information Theory**Santa Fe, March 27, 2008 *

- 1 IBM Watson Research Center
- 2 University of Basel

-  arXiv:0803.2686

## Outline:

-  Effective low-energy  Hamiltonian Heff                   (complex)

- High-energy simulator Hamiltonian H            (simple)

-  Low-energy target   Hamiltonian Htarget                     (complex)

- Physics

- Perturbative gadgets

- Goal: develop a rigorous formalism for constructinga simulator Hamiltonian within a physical range of parameters

-  *Rigorous, but  unphysical scaling of    interactions*

-  *Non-rigorous**     territory*

## Motivation:

- 1. Htarget is chosen for some interesting ground-state properties

- Toric code model

- Quantum loop models

- Briegel-Raussendorf cluster state

- 2. Htarget is chosen for some computational hardness properties

- Quantum NP-hard Hamiltonians

- Adiabatic quantum computation

## What is realistic simulator Hamiltonian ?

- Only two-qubit interactions
- Norm of the interactions is bounded by a constant (independent of the system size)
- Each qubit can interact with a constant number of otherqubits  (bounded degree)
- Nearest-neighbor interactions on a regular lattice(desirable but not necessary)

- Main question: given a target Hamiltonian, what groundstate  properties can be reproduced by a realistic
- simulator Hamiltonian?

## Wish list:

- Main question: given a target Hamiltonian, what groundstate  properties can be reproduced by a realistic
- simulator Hamiltonian?

- Ground-state energy; small ``extensive’’ error
- Expectation values of extensive observables (e.g. average magnetization) small extensive error
- Expectation values of local observables
- Spectral gap
- Topological Quantum Order

- Gapped Hamiltonians ?

- Today’s talk

## Some Terminology:

## Example:  2D Heisenberg model

- 2-local

- Pauli degree =12+1=13

- Interaction strength

## Main result

- *Can be improved to Pauli degree = 3

## Main improvement: interaction strength of the simulator                                is reduced from J poly(n) to O(J) 

- [Oliveira, Terhal 05]   k-local to 2-local on 2D lattice

- [Bravyi, DiVincenzo, Oliveira, Terhal 06]  k-local to 2-local for                                                            stoquastic Hamiltonians

- [Biamonte, Love 07]  simulator with XZ,X,Z only

- [Jordan, Farhi 08]   k-th order perturbative gadgets

- [Schuch, Verstraete 07]   simulator with Heisenberg interactions

- Idea of perturbation          gadget

- Main improvement: interaction strength of the simulator                                is reduced from J poly(n) to O(J)

- Shortcoming: can not go beyond a small extensive error

## Hardness of Approximation = PCP theorem

- energy, why don’t we “simulate” Htarget simply by computing its ground
- state energy with a small extensive error ?

- 1.  We *hope* that H reproduces more than just the ground state energy      (for example, expectation values of extensive observables)

- 2.  Computing the ground state energy of Htarget with a small extensive      error is NP-hard problem even for classical Hamiltonians

- [see Vijay Vazirani, “Approximation Algorithms”, Chapter 29]

## Our result:

## Hamiltonians on a regular lattice

## The Simulation Theorem: plan of the proof

- Add ancillary high-energy “mediator” qubits to the“logical” qubits acted on by Htarget
- Choose appropriate couplings between the mediatorand the logical qubits
- Construct a unitary operator generating an effectivelow-energy Hamiltonian acting on the system qubits
- Apply Lieb-Robinson type arguments to bound the error

- new

- Follows old ideas

## perturbation

- unpertubed Hamiltonian

## Slide 15

## Slide 16

## Toy model: why interesting ? Perturbation gadgets

## 2nd order Lemma: the lower bound 

## 2nd order Lemma: the upper bound 

## Slide 20

## Slide 21

## Slide 22

## Slide 23

## Local block-diagonalization: Schrieffer-Wolff transformation

## Basic properties:

## Global  block-diagonalization

## Generalization: combining SW-formalism with the coupled cluster method

- Coupled cluster method [F. Coester 1958]: heuristic simulation algorithm formany-body quantum systems. One of the most powerful techniques in the
- modern quantum chemistry. Main idea: use variational states

- Where *C* is so called creation operator

- It is expected that ground states of realistic Hamiltonians can be approximated by taking into account only subsets *Γ** *of small size (*C* is a local operator)

## Generalization: combining SW-formalism with the coupled cluster method

## Generalization: combining SW-formalism with the coupled cluster method

## Wish list:

- Main question: given a target Hamiltonian, what groundstate  properties can be reproduced by a realistic
- simulator Hamiltonian? Remains largely open...

- Ground-state energy; small ``extensive’’ error
- Expectation values of extensive observables;small extensive error
- Expectation values of local observables
- Spectral gap
- Topological Quantum Order

- Gapped Hamiltonians ?

- Today’s talk