PhD Seminar • Quantum Computing — A Quantum Algorithm for Simulating Non-sparse HamiltoniansExport this event to calendar

Tuesday, April 24, 2018 — 2:00 PM EDT

Chunhao Wang, PhD candidate
David R. Cheriton School of Computer Science

We present a quantum algorithm for simulating the dynamics of Hamiltonians that are not necessarily sparse. Our algorithm is based on the assumption that the entries of the Hamiltonian are stored in a data structure that allows for the efficient preparation of states that encode the rows of the Hamiltonian. We use a linear combination of quantum walks to achieve a poly-logarithmic dependence on the precision. 

The time complexity measured in terms of circuit depth of our algorithm is $O(t\sqrt{N}\norm{H}\polylog(N, t\norm{H}, 1/\epsilon))$, where $t$ is the evolution time, $N$ is the dimension of the system, and $\epsilon$ is the precision. Our algorithm can directly be applied as a subroutine for unitary implementations and solving linear systems, achieving a $\widetilde{O}(\sqrt{N})$ dependence for both applications.

Location 
QNC - Quantum Nano Centre
1201
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
  1. 2020 (181)
    1. October (2)
    2. September (19)
    3. August (28)
    4. July (14)
    5. June (18)
    6. May (17)
    7. April (20)
    8. March (16)
    9. February (25)
    10. January (22)
  2. 2019 (255)
    1. December (21)
    2. November (25)
    3. October (16)
    4. September (20)
    5. August (18)
    6. July (12)
    7. June (23)
    8. May (23)
    9. April (32)
    10. March (25)
    11. February (16)
    12. January (24)
  3. 2018 (220)
  4. 2017 (36)
  5. 2016 (21)
  6. 2015 (36)
  7. 2014 (33)
  8. 2013 (23)
  9. 2012 (4)
  10. 2011 (1)
  11. 2010 (1)
  12. 2009 (1)
  13. 2008 (1)