1 of 43

On the Impossibility of General Parallel Fast-forwarding of Hamiltonian Simulation

Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh,

Han-Hsuan Lin, Yao-Ting Lin, Yu-Ching Shen

2 of 43

 

Quantum mechanics

 

 

 

 

3 of 43

 

Calculating quantum mechanics

 

 

 

 

 

4 of 43

By Copyright Tamiko Thiel 1984 - communication from photographer, CC BY-SA 3.0, �https://commons.wikimedia.org/w/index.php?curid=44950603

Nature isn't classical, dammit, and if you want to make a simulation of nature, you'd better make it quantum mechanical, and by golly it's a wonderful problem, because it doesn't look so easy.

Simulating Physics with Computers

MIT Physics of Computation Conference, 1981

The transcript was printed in International Journal of Theoretical Physics 21, 467.

5 of 43

By Copyright Tamiko Thiel 1984 - communication from photographer, CC BY-SA 3.0, �https://commons.wikimedia.org/w/index.php?curid=44950603

[I]f you want to make a simulation of nature, you’d better make it quantum mechanical, and by golly it’s a wonderful problem, because it doesn’t look so easy.

Simulating Physics with Computers

MIT Physics of Computation Conference, 1981

The transcript was printed in International Journal of Theoretical Physics 21, 467.

6 of 43

Hamiltonian simulation problem

 

7 of 43

 

8 of 43

​

Type of H

Method

Runtime

[Lloyd96]

Local

Trotter

​

[Childs10]

Sparse

PE + Q walk

​

[BCCKS14]

Sparse

LCU + OAA

​

[BCK15]

Sparse

LCU + OAA + Q walk

​

[LC16]

Sparse

Q signal processing

​

[HHKL18]

Geometrically local

LR bound

​

 

9 of 43

 

​

Model

Lower bound

[BACS07]

​

​

[AA17]

​

​

[HHKL21]

​

​

D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders. Efficient Quantum Algorithms for Simulating Sparse Hamiltonians. Commun. Math. Phys., 270(2), 359–371 (2007).

Y. Atia and D. Aharonov. Fast-forwarding of Hamiltonians and Exponentially Precise Measurements. Nature Commun., 8(1), 1572  (2017).

J. Haah, M. B. Hastings, R. Kothari, and G. H. Low. Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians. In SIAM Journal on Computing, FOCS18, 350–360 (2018).

Reduction to PARITY

10 of 43

 

Z. Zhang, Q. Wang, and M. Ying. Parallel quantum algorithm for Hamiltonian simulation. arXiv:2105.11889, 2021.

11 of 43

Our result

NO!

12 of 43

  • Sparse

 

  • Geometrically local

 

  • Local

 

The types of Hamiltonian

13 of 43

 

 

 

 

 

 

What is the 1st nonzero entry of row 1?

1

1.0

What is the value of entry (1,1)?

 

 

Models

14 of 43

Proofs

15 of 43

Mathematical definition of parallel fast-forwarding

 

 

 

 

 

16 of 43

Mathematical definition of parallel fast-forwarding

 

 

 

 

17 of 43

Our result

Type

Model

Assumption

​

Sparse

Oracle

-

​

Local

Plain

Random oracle heuristic

​

Geometrically local, time-dependent

Plain

Random oracle heuristic

​

 

 

 

18 of 43

Proof idea:

Hamiltonian evolution

Quantum algorithm

19 of 43

 

 

 

 

 

 

 

20 of 43

 

 

 

 

 

 

 

21 of 43

 

 

 

 

 

 

 

 

22 of 43

 

Proof Sketch

23 of 43

What really appears in our paper

 

 

 

24 of 43

(Query depth) lower bound of sparse Hamiltonian

 

25 of 43

 

 

…

 

…

 

 

 

 

 

 

 

 

 

 

 

 

Query depth: 1 2 3

…

4-parallel query

26 of 43

Proof of the hardness of permutation chain: 2 step hybrid

permutation chain oracle

 

 

Hybrid 1: remove extra permutations

 

 

 

 

 

 

 

 

 

 

 

 

27 of 43

Answer chain oracle

 

Proof of the hardness of permutation chain: 2 step hybrid

 

Hybrid 2: releasing the answer chain step by step

 

 

 

 

 

 

 

 

 

 

 

 

28 of 43

Proof of the hardness of permutation chain: 2 step hybrid

permutation chain oracle

 

 

Hybrid 1: remove extra permutations

 

 

 

 

 

 

 

 

 

 

 

 

29 of 43

Why removing permutations is fine: can simulate the removed permutations with negligible error by adding back a random permutation

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Hard to find

30 of 43

Hybrid 2: proof by induction

 

 

 

 

 

 

 

 

 

This is fine because at the first layer of queries, the algorithm doesn’t know the location of later parts of the chain (green dots), so it can not find the difference between left and right .

 

 

 

 

31 of 43

Hybrid 2: proof by induction

 

 

 

 

 

 

 

 

 

On the second layer of queries, once again the algorithm doesn’t know the location green dots because the first query doesn’t know the green dots, so an algorithm can not find the difference between left and right

32 of 43

Hybrid 2: proof by induction

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

33 of 43

Lower bound of sparse Hamiltonian: a Hamiltonian simulating permutation chain

 

 

 

 

 

 

34 of 43

Twisted Hash Chain

 

 

 

 

 

 

 

 

 

 

 

 

 

 

…

35 of 43

Twisted Hash Chain: why twisted

 

 

 

 

 

 

 

 

…

 

 

 

36 of 43

Twisted Hash Chain

 

 

 

 

 

 

 

 

 

 

 

 

 

…

  • Proof of hardness: Compressed oracle [Zhandry19] [CFHL21]; Quantum analogue of lazy sampling in random oracle model

37 of 43

Lower bound of local Hamiltonian in plain model: a Hamiltonian simulating twisted hash chain

 

 

 

 

 

 

 

 

 

 

 

 

…

 

38 of 43

Outlooks

 

39 of 43

Outlooks

  • Weaker assumptions?
  • Better parameters to match lower bounds?

40 of 43

Thank You!

41 of 43

 

42 of 43

  • Is it possible to fast-forward the simulation?
  • Namely, can we simulate Hamiltonians in time strictly less than the evolution time?

43 of 43

Some specific Hamiltonians can be fast-forwarded

​

Type of H

[AA17]

​

[GSS21]

​

[EDB+22]

Many-body localization system

Y. Atia and D. Aharonov. Fast-forwarding of Hamiltonians and Exponentially Precise Measurements. Nature Commun., 8(1), 1572  (2017).

S. Gu, R. D. Somma, and B. Şahinoğlu. Fast-forwarding quantum evolution. Quantum, 5, 577, (2021).

A. Ehrenberg, A. Deshpande, C. L. Baldwin, D. A. Abanin, and A. V. Gorshkov. Simulation Complexity of Many-Body Localized Systems. arXiv:2205.12967.