Term Grouping and Travelling Salesperson for Digital Quantum Simulation
- URL: http://arxiv.org/abs/2001.05983v3
- Date: Fri, 12 Mar 2021 16:34:15 GMT
- Title: Term Grouping and Travelling Salesperson for Digital Quantum Simulation
- Authors: Kaiwen Gui, Teague Tomesh, Pranav Gokhale, Yunong Shi, Frederic T.
Chong, Margaret Martonosi, Martin Suchara
- Abstract summary: Digital simulation of quantum dynamics by evaluating the time evolution of a Hamiltonian is the initially proposed application of quantum computing.
The large number of quantum gates required for emulating the complete second quantization form of the Hamiltonian makes such an approach unsuitable for near-term devices.
We propose a new term ordering strategy, max-commute-tsp, that simultaneously mitigates both algorithmic and physical errors.
- Score: 6.945601123742983
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Digital simulation of quantum dynamics by evaluating the time evolution of a
Hamiltonian is the initially proposed application of quantum computing. The
large number of quantum gates required for emulating the complete second
quantization form of the Hamiltonian, however, makes such an approach
unsuitable for near-term devices with limited gate fidelities that cause high
physical errors. In addition, Trotter error caused by noncommuting terms can
accumulate and harm the overall circuit fidelity, thus causing algorithmic
errors. In this paper, we propose a new term ordering strategy, max-commute-tsp
(MCTSP), that simultaneously mitigates both algorithmic and physical errors.
First, we improve the Trotter fidelity compared with previously proposed
optimization by reordering Pauli terms and partitioning them into commuting
families. We demonstrate the practicality of this method by constructing and
evaluating quantum circuits that simulate different molecular Hamiltonians,
together with theoretical explanations for the fidelity improvements from our
term grouping method. Second, we describe a new gate cancellation technique
that reduces the high gate counts by formulating the gate cancellation problem
as a travelling salesperson problem, together with benchmarking experiments.
Finally, we also provide benchmarking results that demonstrate the combined
advantage of max-commute-tsp to mitigate both physical and algorithmic errors
via quantum circuit simulation under realistic noise models.
Related papers
- Randomized term grouping over physical law on digital quantum simulation [0.0]
We introduce a randomized algorithm based on qDrift to compute Hamiltonian dynamics on digital quantum computers.
We frame it as physDrift because conservation laws in physics are obeyed during evolution of arbitrary quantum states.
arXiv Detail & Related papers (2023-09-24T13:15:39Z) - Improved Digital Quantum Simulation by Non-Unitary Channels [0.5999777817331317]
We study the performance of non-unitary simulation channels and consider the error structure of channels constructed from a weighted average of unitary circuits.
We show that averaging over just a few simulation circuits can significantly reduce the Trotterization error for both single-step short-time and multi-step long-time simulations.
arXiv Detail & Related papers (2023-07-24T18:00:02Z) - Numerical Simulations of Noisy Quantum Circuits for Computational
Chemistry [51.827942608832025]
Near-term quantum computers can calculate the ground-state properties of small molecules.
We show how the structure of the computational ansatz as well as the errors induced by device noise affect the calculation.
arXiv Detail & Related papers (2021-12-31T16:33:10Z) - Simulating the Mott transition on a noisy digital quantum computer via
Cartan-based fast-forwarding circuits [62.73367618671969]
Dynamical mean-field theory (DMFT) maps the local Green's function of the Hubbard model to that of the Anderson impurity model.
Quantum and hybrid quantum-classical algorithms have been proposed to efficiently solve impurity models.
This work presents the first computation of the Mott phase transition using noisy digital quantum hardware.
arXiv Detail & Related papers (2021-12-10T17:32:15Z) - Quantum algorithms for quantum dynamics: A performance study on the
spin-boson model [68.8204255655161]
Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator.
variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware.
We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
arXiv Detail & Related papers (2021-08-09T18:00:05Z) - Algebraic Compression of Quantum Circuits for Hamiltonian Evolution [52.77024349608834]
Unitary evolution under a time dependent Hamiltonian is a key component of simulation on quantum hardware.
We present an algorithm that compresses the Trotter steps into a single block of quantum gates.
This results in a fixed depth time evolution for certain classes of Hamiltonians.
arXiv Detail & Related papers (2021-08-06T19:38:01Z) - Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
We present a constructive algorithm for generating quantum circuits with time-independent depth.
We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model.
In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
arXiv Detail & Related papers (2021-04-01T19:06:00Z) - Low-depth Hamiltonian Simulation by Adaptive Product Formula [3.050399782773013]
Various Hamiltonian simulation algorithms have been proposed to efficiently study the dynamics of quantum systems on a quantum computer.
Here, we propose an adaptive approach to construct a low-depth time evolution circuit.
Our work sheds light on practical Hamiltonian simulation with noisy-intermediate-scale-quantum devices.
arXiv Detail & Related papers (2020-11-10T18:00:42Z) - Simulating nonnative cubic interactions on noisy quantum machines [65.38483184536494]
We show that quantum processors can be programmed to efficiently simulate dynamics that are not native to the hardware.
On noisy devices without error correction, we show that simulation results are significantly improved when the quantum program is compiled using modular gates.
arXiv Detail & Related papers (2020-04-15T05:16:24Z) - Hamiltonian Simulation Algorithms for Near-Term Quantum Hardware [6.445605125467574]
We develop quantum algorithms for Hamiltonian simulation "one level below" the circuit model.
We analyse the impact of these techniques under the standard error model.
We derive analytic circuit identities for efficiently synthesising multi-qubit evolutions from two-qubit interactions.
arXiv Detail & Related papers (2020-03-15T18:22:02Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.