Hamiltonian Quantum Computer in 1D

Hamiltonian quantum computer Hamiltonian quantum computer in one dimension in one dimension Tzu-Chieh Wei C.N. Yang Institute for Theoretical Physics Department of Physics & Astronomy John C Liang Rumson-Fair High School Stanford University Supported by AQIS, Taipei, 8/30/2016

Outline I. Introduction: Hamiltonian quantum computer II. 1D 3-local 5-state construction (not translation invariant) III. 1D 3-local 8-state construction (translation invariant) [will not have much time for this part] IV. Summary

Quantum computation: circuit Measurement n qubits (initialized) round R of gates round 2 round 1 3 steps: (1) Initialization, (2) Gate operations (3) Measurement Gates: a finite (universal) set of unitary transformations are sufficient 1-qubit gates: 2-qubit gate: Note 1-qubit gates are special case of 2-qubit gates:

Simulating circuit with Hamiltonian Measurement u v n qubits (initialized) round R of gates round 2 round 1 First Hamiltonian Quantum Computer by Feynman in 1984 Unary Clock: t=1: 00 .001, t=2: 00 .010, t=3: 00 .100 (using s to flip) Ai applies to pair (u,v) of qubits (e.g. from circuit) clock Each term is a 4-body (but not geometrically local) qubits u v

1D Hamiltonian Quantum Computer Can we do this with a one-dimensional Hamiltonian? (Feynman s not 1D) Yes: but requires large local dimension for short-ranged, e.g. nearest-neighbor: Vollbrecht & Cirac: translation invariant, 30-state Kay: translation invariant, 31-state Nagaj & Wocjan: translation invariant, (1) 10-state (2) 20-state Aharonov et al. has one construction that (can be interpreted in terms of Hamiltonian QC) is non-translation invariant with 9-state Chase & Landahl: non-translation invariant, 8-state

Locality k vs local dimension d 1D Local Hamiltonians (non-translationally invariant) Aharonov et al. 9 d Chase & Landahl ? 8 Local dimension 7 Not Universal 6 This work 5 4 Implied by Chase & Landahl 3 2 4 2 3 5 1 6 k Locality

Outline I. Introduction: Hamiltonian quantum computer II. 1D 3-local 5-state construction (not translation invariant) III. 1D 3-local 8-state construction (translation invariant) IV. Summary

Universal Circuit n qubits round R of gates round 2 round 1 How do we simulate such circuit on 1D chain? (How to modify Feynman s construction?) clock qubits u v Can we get rid of clock qubits? How to apply different gates on the same pair of qubits?

Simulate circuit with 1D chain n qubits round R of gates round 2 round 1 Solution inspired by 1D QMA LHP: (1) Replace clock by pattern of symbols (2) Each gate is applied at specific & distinct location [Aharonov, Gottesman, Irani & Kempe 09] Example: n=3 qubits, R=2 rounds (initial state shown) 2 gates in one round [applied between neighboring qubits] qubits need to be moved from block to block for next round of gates

Local Hilbert space & transition rules Two different types of sites: : two kinds of qubits A: 5-state : unborn/dead (1 dim) B: 5-state : spacer btwn qubits or unborn turn -around right/ left : movement & direction change Transition rules: 1 (backward): 1: 2: 6a: boundary 3: 6b: 4: NOT boundary 7a: 5a: 7b: 5b:

Transitions history states [w qubits properly initialized in 0 or 1] U1 U3 (initial state) U2 U4 6a 1: U1 1 U2 2: 1 2 3: 3 4: 4 5a: 5a 5b: 4 6a: 5a 4 6b: 5b 7a: 6b 7b:

Transitions history states U1 U3 U2 U4 6b 1: 7a 7b 2: 3 3: 4 4: 5a 5a: 5a 5b: 4 6a: 5b 6a 6b: U3 1 7a: U4 1 (final) 7b:

Computation at discrete time & history states U1 U3 U2 U4 Unique forward/backward transition (except at initial and final state) 6a U1 1 U2 Transition rules uniquely connect history states (of computation) 1 2 3 5a But isn t our computer run by continuous-time evolution? Hamiltonian? 4 5b 6a U3 1 U4 1

Transition rules 1 (backward): 1: 2: 6a: 3: 6b: 4: 7a: 5a: 7b: 5b: Yes, but can turn these rules into a Hamiltonian

Hamiltonian Constructed from the transition rules: In the basis of valid history (via transition rules): Effective Hamiltonian:

Run your Hamiltonian computer [@| + + + + .|O.O.O.O.O.|O.O.O.O.O.|O.O.O.O.O.|O.O.O.O.O.|O.O.O.O.O.] With qubits appropriately initialized (e.g. 00000) Quantum computation: evolve by Schrodinger equation via Hamiltonian Readout: measure in the computational basis Problems: But at what time t ? We want it to evolve to final state! Na ve counting: probability 1/T to land onto the final state!!

Raising probability to finish goal Trick: set your training goal higher pad a lot of identity gates I after desired rounds finished I II I I I I I desired goal training goal Then there is high probability of success in getting the correct outcome [.|O.O.O.O.O.|O.O.O.O.O.|O.O.O.O.O.|O.O. + + <|O+ + .O.O.|O.O.O.O.O.] Remaining gates are identity computation finished

Effective Hamiltonian: 1D quantum walk or tight-binding model has eigenvalues with eigenstates Starting at |0 , probability of arriving at |m after time

Analysis for success probability Starting at |0 , probability of arriving at |m after time Can show that [Nagaj & Wocjan, PRA 2008] Pad sufficient identity gates (e.g. 5 times as many) so that for m T/6, desired computation is done Readout: measure in the basis at random time B: A: e.g. [.|O.O.O.O.O.|O.O.O.O.O.|O.O.O.O.O.|O.O. + + <|O+ + .O.O.|O.O.O.O.O.] Take finite and high probability of success

So we have demonstrated a 1D 3-local 5-state (spin-2) Hamiltonian capable of universal QC Classical simulation of such spin-2 Hamiltonian is BQP-complete

What if translational invariance is imposed? 1D Local Hamiltonians (translationally invariant w.r.t. unit cells) 10 Nagaj & Wocjan ? 9 d 8 This work Local dimension 7 Not Universal 6 5 Implied by Nagaj & Wocjan 4 3 2 4 2 5 3 1 6 k Locality

Summary & open questions 1D 3-local 5-state (spin-2) Hamiltonian (not translationally invariant) universal for Hamiltonian quantum computation 1D 3-local 8-state (spin-7/2) Hamiltonian (translationally invariant) universal for Hamiltonian quantum computation Open: are the above results optimal? What about 1D 3-local QMA Hamiltonians? Minimum local dim?