Corrected quantum walk for optimal Hamiltonian simulation

Dominic Berry, Leonardo Novo

Research output: Contribution to journalArticleResearchpeer-review

Abstract

We describe a method to simulate Hamiltonian evolution on a quantum computer by repeatedly using a superposition of steps of a quantum walk, then applying a correction to the weightings for the numbers of steps of the quantum walk. This correction enables us to obtain complexity which is the same as the lower bound up to double-logarithmic factors for all parameter regimes. The scaling of the query complexity is O (τ (log logτ/log log logτ) + log(1/ε)) where τ := t||H||maxd, for ε the allowable error, t the time, ||H||max the max-norm of the Hamiltonian, and d the sparseness. This technique should also be useful for improving the scaling of the Taylor series approach to simulation, which is relevant to applications such as quantum chemistry.

LanguageEnglish
Pages1295–1317
Number of pages23
JournalQuantum Information and Computation
Volume16
Issue number15&16
Publication statusPublished - Nov 2016

Fingerprint

Quantum Walk
Hamiltonians
Scaling
scaling
Quantum Chemistry
Quantum chemistry
Quantum computers
Query Complexity
Quantum Computer
Taylor series
quantum computers
quantum chemistry
norms
Superposition
Weighting
Logarithmic
Simulation
simulation
Lower bound
Norm

Keywords

  • quantum algorithms
  • quantum query complexity
  • Hamiltonian simulation
  • quantum walk

Cite this

Berry, Dominic ; Novo, Leonardo. / Corrected quantum walk for optimal Hamiltonian simulation. In: Quantum Information and Computation. 2016 ; Vol. 16, No. 15&16. pp. 1295–1317.
@article{81c25dc2360346c9aa5fb182046fe369,
title = "Corrected quantum walk for optimal Hamiltonian simulation",
abstract = "We describe a method to simulate Hamiltonian evolution on a quantum computer by repeatedly using a superposition of steps of a quantum walk, then applying a correction to the weightings for the numbers of steps of the quantum walk. This correction enables us to obtain complexity which is the same as the lower bound up to double-logarithmic factors for all parameter regimes. The scaling of the query complexity is O (τ (log logτ/log log logτ) + log(1/ε)) where τ := t||H||maxd, for ε the allowable error, t the time, ||H||max the max-norm of the Hamiltonian, and d the sparseness. This technique should also be useful for improving the scaling of the Taylor series approach to simulation, which is relevant to applications such as quantum chemistry.",
keywords = "quantum algorithms, quantum query complexity, Hamiltonian simulation, quantum walk",
author = "Dominic Berry and Leonardo Novo",
year = "2016",
month = "11",
language = "English",
volume = "16",
pages = "1295–1317",
journal = "Quantum Information and Computation",
issn = "1533-7146",
publisher = "Rinton Press Inc.",
number = "15&16",

}

Corrected quantum walk for optimal Hamiltonian simulation. / Berry, Dominic; Novo, Leonardo.

In: Quantum Information and Computation, Vol. 16, No. 15&16, 11.2016, p. 1295–1317.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Corrected quantum walk for optimal Hamiltonian simulation

AU - Berry, Dominic

AU - Novo, Leonardo

PY - 2016/11

Y1 - 2016/11

N2 - We describe a method to simulate Hamiltonian evolution on a quantum computer by repeatedly using a superposition of steps of a quantum walk, then applying a correction to the weightings for the numbers of steps of the quantum walk. This correction enables us to obtain complexity which is the same as the lower bound up to double-logarithmic factors for all parameter regimes. The scaling of the query complexity is O (τ (log logτ/log log logτ) + log(1/ε)) where τ := t||H||maxd, for ε the allowable error, t the time, ||H||max the max-norm of the Hamiltonian, and d the sparseness. This technique should also be useful for improving the scaling of the Taylor series approach to simulation, which is relevant to applications such as quantum chemistry.

AB - We describe a method to simulate Hamiltonian evolution on a quantum computer by repeatedly using a superposition of steps of a quantum walk, then applying a correction to the weightings for the numbers of steps of the quantum walk. This correction enables us to obtain complexity which is the same as the lower bound up to double-logarithmic factors for all parameter regimes. The scaling of the query complexity is O (τ (log logτ/log log logτ) + log(1/ε)) where τ := t||H||maxd, for ε the allowable error, t the time, ||H||max the max-norm of the Hamiltonian, and d the sparseness. This technique should also be useful for improving the scaling of the Taylor series approach to simulation, which is relevant to applications such as quantum chemistry.

KW - quantum algorithms

KW - quantum query complexity

KW - Hamiltonian simulation

KW - quantum walk

UR - http://www.rintonpress.com/journals/qiconline.html#v16n1516

UR - https://doi.org/10.26421/QIC16.15-16

M3 - Article

VL - 16

SP - 1295

EP - 1317

JO - Quantum Information and Computation

T2 - Quantum Information and Computation

JF - Quantum Information and Computation

SN - 1533-7146

IS - 15&16

ER -