Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0203061

Bounds on the number of time steps for simulating arbitrary interaction graphs

Dominik Janzing, Wocjan, Pawel, Beth, Thomas

Published Mar 14, 2002• 0 citations
arXivHTMLPDF

Abstract

In previous papers we have considered mutual simulation of n-partite pair-interaction Hamiltonians. We have focussed on the running time overhead of general simulations, while considering the required number of time steps only for special cases (decoupling and time-reversal). These two complexity measures differ significantly. Here we derive lower bounds on the number of time steps for general simulations. In particular, the simulation of interaction graphs with irrational spectrum requires at least n steps. We discuss as examples graphs that correspond to graph codes and nearest neighbor interactions in 1- and 2-dimensional lattices. In the latter case the lower bounds are almost tight.

DOI
10.48550/arxiv.quant-ph/0203061

Related papers

ON THE COMPUTATIONAL POWER OF PHYSICAL INTERACTIONS: BOUNDS ON THE NUMBER OF TIME STEPS FOR SIMULATING ARBITRARY INTERACTION GRAPHS

Dominik Janzing, Paweł Wocjan, Thomas Beth

The most popular model of quantum computation is the quantum circuit model using single and two qubit gates as elementary transformations. Definitions of quantum complexity usually refer to this model. In contrast, we consider the physical interactions among the qubits as the basic computational resource that allows to carry out complex transformations on the quantum register. One method to compare the computational power of different interactions is to examine the complexity of the so-called mutual simulation of interaction Hamiltonians. The physical interaction can simulate other interactions by interspersing the natural time evolution with external control operations. In previous papers we have considered mutual simulation of n-partite pair-interaction Hamiltonians. We have focussed on the running time overhead of general simulations, while considering the required number of time steps only for special cases (decoupling and time-reversal). These two complexity measures differ significantly. Here we derive lower bounds on the number of time steps for simulations of general interaction graphs. In particular, the simulation of interaction graphs with irrational spectrum requires at least n steps. We discuss as examples graphs that correspond to graph codes and nearest neighbor interactions in 1- and 2-dimensional lattices. In the latter case the lower bounds are almost tight.

International Journal of Foundations of Computer Science•Oct 1, 2003•1 citation

Simulating arbitrary pair-interactions by a given Hamiltonian: graph-theoretical bounds on the time-complexity

Paweł Wocjan, Dominik Janzing, T. Beth

We consider a quantum computer consisting of n spins with an arbitrary but fixed pair-interaction Hamiltonian and describe how to simulate other pair-interactions by interspersing the natural time evolution with fast local transformations. Calculating the minimal time overhead of such a simulation leads to a convex optimization problem. Lower and upper bounds on the minimal time overhead are derived in terms of chromatic indices of interaction graphs and spectral majorization criteria. These results classify Hamiltonians with respect to their computational power. For a specific Hamiltonian, namely \sigma_z\otimes\sigma_z-interactions between all spins, the optimization is mathematically equivalent to a separability problem of n-qubit density matrices. We compare the complexity defined by such a quantum computer with the usual gate complexity.

arXiv:quant-ph/0106077•Quantum Information and Computation•Feb 1, 2002•38 citations

Simulating Hamiltonians in quantum networks: Efficient schemes and complexity bounds

Paweł Wocjan, Martin Rötteler, Dominik Janzing +1 more

We address the problem of simulating pair-interaction Hamiltonians in n-node quantum networks where the subsystems have arbitrary, possibly different, dimensions. We show that any pair interaction can be used to simulate any other by applying sequences of appropriate local control sequences. Conditions on time optimal simulation are formulated in terms of spectral majorization of matrices characterizing the coupling parameters. Efficient schemes for decoupling and time reversal can be constructed from orthogonal arrays provided that the dimensions of all nodes are equal to the same prime power. Moreover, we consider a specific system of n harmonic oscillators with bilinear interaction. In this case, decoupling can efficiently be achieved using the combinatorial concept of difference schemes. For this type of interaction we present optimal schemes for inversion.

arXiv:quant-ph/0109088•Physical Review A•Mar 29, 2002•50 citations

Nearly Optimal Lattice Simulation by Product Formulas

Andrew M. Childs, Yuan Su

We consider simulating an n-qubit Hamiltonian with nearest-neighbor interactions evolving for time t on a quantum computer. We show that this simulation has gate complexity (nt)^{1+o(1)} using product formulas, a straightforward approach that has been demonstrated by several experimental groups. While it is reasonable to expect this complexity-in particular, this was claimed without rigorous justification by Jordan, Lee, and Preskill-we are not aware of a straightforward proof. Our approach is based on an analysis of the local error structure of product formulas, as introduced by Descombes and Thalhammer and significantly simplified here. We prove error bounds for canonical product formulas, which include well-known constructions such as the Lie-Trotter-Suzuki formulas. We also develop a local error representation for time-dependent Hamiltonian simulation, and we discuss generalizations to periodic boundary conditions, constant-range interactions, and higher dimensions. Combined with a previous lower bound, our result implies that product formulas can simulate lattice Hamiltonians with nearly optimal gate complexity.

arXiv:1901.00564•Physical Review Letters•Aug 2, 2019•182 citations

Complexity measure for continuous-time quantum algorithms

Dominik Janzing, T. Beth

We consider unitary dynamical evolutions on n qubits caused by time-dependent pair-interaction Hamiltonians and show that the running time of a parallelized two-qubit gate network simulating the evolution is given by the time integral over the chromatic index of the interaction graph. This defines complexity measures of continuous and discrete quantum algorithms, which are in exact one-to-one correspondence. We prove a lower bound on the complexity of those multiparticle states, which show quantum superpositions on the macroscopic scale.

arXiv:quant-ph/0009094•Physical Review A•Jul 2, 2001•7 citations

Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians

Jeongwan Haah, Matthew B. Hastings, Robin Kothari +1 more

We study the problem of simulating the time evolution of a lattice Hamiltonian, where the qubits are laid out on a lattice and the Hamiltonian only includes geometrically local interactions (i.e., a qubit may only interact with qubits in its vicinity). This class of Hamiltonians is very general and is believed to capture fundamental interactions of physics. Our algorithm simulates the time evolution of such a Hamiltonian on $n$ qubits for time $T$ up to error $\epsilon$ using ${\mathcal O}( nT {polylog} (nT/\epsilon))$ gates with depth ${\mathcal O}(T { polylog} (nT/\epsilon))$. Our algorithm is the first simulation algorithm that achieves gate cost quasilinear in $nT$ and polylogarithmic in $1/\epsilon$. Our algorithm also readily generalizes to time-dependent Hamiltonians and yields an algorithm with similar gate count for any piecewise slowly varying time-dependent bounded local Hamiltonian. We also prove a matching lower bound on the gate count of such a simulation, showing that any quantum algorithm that can simulate a piecewise constant bounded local Hamiltonian in one dimension to constant error requires ${\widetilde{\Omega}}(nT)$ gates in the worst case. The lower bound holds even if we only require the output state to be correct on local measurements. To the best of our knowledge, this is the first nontrivial lower bound on the gate complexity of the simulation problem. Our algorithm is based on a decomposition of the time-evolution unitary into a product of small unitaries using Lieb--Robinson bounds. In the appendix, we prove a Lieb--Robinson bound tailored to Hamiltonians with small commutators between local terms, giving zero Lieb--Robinson velocity in the limit of commuting Hamiltonians. This improves the performance of our algorithm when the Hamiltonian is close to commuting.

arXiv:1801.03922•SIAM Journal on Computing•Jan 12, 2021•148 citations
In previous papers we have considered mutual simulation of n-partite pair-interaction Hamiltonians. We have focussed on the running time overhead of general simulations, while considering the required number of time steps only for special cases (decoupling and time-reversal). These two complexity measures differ significantly. Here we derive lower bounds on the number of time steps for general simulations. In particular, the simulation of interaction graphs with irrational spectrum requires at least n steps. We discuss as examples graphs that correspond to graph codes and nearest neighbor interactions in 1- and 2-dimensional lattices. In the latter case the lower bounds are almost tight.
The most popular model of quantum computation is the quantum circuit model using single and two qubit gates as elementary transformations. Definitions of quantum complexity usually refer to this model. In contrast, we consider the physical interactions among the qubits as the basic computational resource that allows to carry out complex transformations on the quantum register. One method to compare the computational power of different interactions is to examine the complexity of the so-called mutual simulation of interaction Hamiltonians. The physical interaction can simulate other interactions by interspersing the natural time evolution with external control operations. In previous papers we have considered mutual simulation of n-partite pair-interaction Hamiltonians. We have focussed on the running time overhead of general simulations, while considering the required number of time steps only for special cases (decoupling and time-reversal). These two complexity measures differ significantly. Here we derive lower bounds on the number of time steps for simulations of general interaction graphs. In particular, the simulation of interaction graphs with irrational spectrum requires at least n steps. We discuss as examples graphs that correspond to graph codes and nearest neighbor interactions in 1- and 2-dimensional lattices. In the latter case the lower bounds are almost tight.
We consider a quantum computer consisting of n spins with an arbitrary but fixed pair-interaction Hamiltonian and describe how to simulate other pair-interactions by interspersing the natural time evolution with fast local transformations. Calculating the minimal time overhead of such a simulation leads to a convex optimization problem. Lower and upper bounds on the minimal time overhead are derived in terms of chromatic indices of interaction graphs and spectral majorization criteria. These results classify Hamiltonians with respect to their computational power. For a specific Hamiltonian, namely \sigma_z\otimes\sigma_z-interactions between all spins, the optimization is mathematically equivalent to a separability problem of n-qubit density matrices. We compare the complexity defined by such a quantum computer with the usual gate complexity.
We address the problem of simulating pair-interaction Hamiltonians in n-node quantum networks where the subsystems have arbitrary, possibly different, dimensions. We show that any pair interaction can be used to simulate any other by applying sequences of appropriate local control sequences. Conditions on time optimal simulation are formulated in terms of spectral majorization of matrices characterizing the coupling parameters. Efficient schemes for decoupling and time reversal can be constructed from orthogonal arrays provided that the dimensions of all nodes are equal to the same prime power. Moreover, we consider a specific system of n harmonic oscillators with bilinear interaction. In this case, decoupling can efficiently be achieved using the combinatorial concept of difference schemes. For this type of interaction we present optimal schemes for inversion.
We consider simulating an n-qubit Hamiltonian with nearest-neighbor interactions evolving for time t on a quantum computer. We show that this simulation has gate complexity (nt)^{1+o(1)} using product formulas, a straightforward approach that has been demonstrated by several experimental groups. While it is reasonable to expect this complexity-in particular, this was claimed without rigorous justification by Jordan, Lee, and Preskill-we are not aware of a straightforward proof. Our approach is based on an analysis of the local error structure of product formulas, as introduced by Descombes and Thalhammer and significantly simplified here. We prove error bounds for canonical product formulas, which include well-known constructions such as the Lie-Trotter-Suzuki formulas. We also develop a local error representation for time-dependent Hamiltonian simulation, and we discuss generalizations to periodic boundary conditions, constant-range interactions, and higher dimensions. Combined with a previous lower bound, our result implies that product formulas can simulate lattice Hamiltonians with nearly optimal gate complexity.
We consider unitary dynamical evolutions on n qubits caused by time-dependent pair-interaction Hamiltonians and show that the running time of a parallelized two-qubit gate network simulating the evolution is given by the time integral over the chromatic index of the interaction graph. This defines complexity measures of continuous and discrete quantum algorithms, which are in exact one-to-one correspondence. We prove a lower bound on the complexity of those multiparticle states, which show quantum superpositions on the macroscopic scale.
We study the problem of simulating the time evolution of a lattice Hamiltonian, where the qubits are laid out on a lattice and the Hamiltonian only includes geometrically local interactions (i.e., a qubit may only interact with qubits in its vicinity). This class of Hamiltonians is very general and is believed to capture fundamental interactions of physics. Our algorithm simulates the time evolution of such a Hamiltonian on nnn qubits for time TTT up to error ϵ\epsilonϵ using O(nTpolylog(nT/ϵ)){\mathcal O}( nT {polylog} (nT/\epsilon))O(nTpolylog(nT/ϵ)) gates with depth O(Tpolylog(nT/ϵ)){\mathcal O}(T { polylog} (nT/\epsilon))O(Tpolylog(nT/ϵ)). Our algorithm is the first simulation algorithm that achieves gate cost quasilinear in nTnTnT and polylogarithmic in 1/ϵ1/\epsilon1/ϵ. Our algorithm also readily generalizes to time-dependent Hamiltonians and yields an algorithm with similar gate count for any piecewise slowly varying time-dependent bounded local Hamiltonian. We also prove a matching lower bound on the gate count of such a simulation, showing that any quantum algorithm that can simulate a piecewise constant bounded local Hamiltonian in one dimension to constant error requires Ω~(nT){\widetilde{\Omega}}(nT)Ω(nT) gates in the worst case. The lower bound holds even if we only require the output state to be correct on local measurements. To the best of our knowledge, this is the first nontrivial lower bound on the gate complexity of the simulation problem. Our algorithm is based on a decomposition of the time-evolution unitary into a product of small unitaries using Lieb--Robinson bounds. In the appendix, we prove a Lieb--Robinson bound tailored to Hamiltonians with small commutators between local terms, giving zero Lieb--Robinson velocity in the limit of commuting Hamiltonians. This improves the performance of our algorithm when the Hamiltonian is close to commuting.