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/0106077 · Quantum Information and Computation

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

Paweł Wocjan, Dominik Janzing, T. Beth

Published Feb 1, 2002• 38 citations
arXivHTMLPDF

Abstract

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.

DOI
10.26421/qic2.2-2

Related papers

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

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

Optimal simulation of two-qubit Hamiltonians using general local operations

C. H. Bennett, J. I. Cirac, Matthew Leifer +4 more

We consider the simulation of the dynamics of one nonlocal Hamiltonian by another, allowing arbitrary local resources but no entanglement or classical communication. We characterize notions of simulation, and proceed to focus on deterministic simulation involving one copy of the system. More specifically, two otherwise isolated systems A and B interact by a nonlocal Hamiltonian $H\ensuremath{\ne}{H}_{A}{+H}_{B}.$ We consider the achievable space of Hamiltonians ${H}^{\ensuremath{'}}$ such that the evolution ${e}^{\ensuremath{-}{\mathrm{iH}}^{\ensuremath{'}}t}$ can be simulated by the interaction H interspersed with local operations. For any dimensions of A and B, and any nonlocal Hamiltonians H and ${H}^{\ensuremath{'}},$ there exists a scale factor s such that for all times t the evolution ${e}^{\ensuremath{-}{\mathrm{iH}}^{\ensuremath{'}}\mathrm{st}}$ can be simulated by H acting for time t interspersed with local operations. For two-qubit Hamiltonians H and ${H}^{\ensuremath{'}},$ we calculate the optimal s and give protocols achieving it. The optimal protocols do not require local ancillas, and can be understood geometrically in terms of a polyhedron defined by a partial order on the set of two-qubit Hamiltonians.

arXiv:quant-ph/0107035•Physical Review A•Jul 19, 2002•110 citations

Optimal Lower Bounds for Hamiltonian Simulation

Alexander Zlokapa, Richard R. Allen, Aram W. Harrow

For Hamiltonian $H = \sum_j h_j$, we prove asymptotically tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer. Our bounds hold for arbitrary term norms $\|h_j\|$, time $t$, and trace-distance error $ε$. The matching upper bound (known as composite qDRIFT) consists of high-order Trotterization of the large terms and a randomized first-order Trotterization of the small terms. Unlike prior work that chooses worst-case $\|h_j\|$ to encode the computation of parity or other Boolean functions in time evolution, our proof is elementary and based on a local, bounded-degree classical Hamiltonian. Our work suggests that for many physical systems (e.g., power-law interactions), gate count must scale polynomially in $1/ε$, contrary to the complexity suggested by counting coherent oracle queries such as those in the block-encoding model.

quant-pharXiv:2607.19852•Jul 23, 2026•0 citations

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

Dominik Janzing, Wocjan, Pawel, Beth, Thomas

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.

arXiv:quant-ph/0203061•Mar 14, 2002•0 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
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.
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 the simulation of the dynamics of one nonlocal Hamiltonian by another, allowing arbitrary local resources but no entanglement or classical communication. We characterize notions of simulation, and proceed to focus on deterministic simulation involving one copy of the system. More specifically, two otherwise isolated systems A and B interact by a nonlocal Hamiltonian $H\ensuremath{\ne}{H}_{A}{+H}_{B}.$ We consider the achievable space of Hamiltonians ${H}^{\ensuremath{'}}$ such that the evolution ${e}^{\ensuremath{-}{\mathrm{iH}}^{\ensuremath{'}}t}$ can be simulated by the interaction H interspersed with local operations. For any dimensions of A and B, and any nonlocal Hamiltonians H and ${H}^{\ensuremath{'}},$ there exists a scale factor s such that for all times t the evolution ${e}^{\ensuremath{-}{\mathrm{iH}}^{\ensuremath{'}}\mathrm{st}}$ can be simulated by H acting for time t interspersed with local operations. For two-qubit Hamiltonians H and ${H}^{\ensuremath{'}},$ we calculate the optimal s and give protocols achieving it. The optimal protocols do not require local ancillas, and can be understood geometrically in terms of a polyhedron defined by a partial order on the set of two-qubit Hamiltonians.
For Hamiltonian H=∑jhjH = \sum_j h_jH=∑j​hj​, we prove asymptotically tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer. Our bounds hold for arbitrary term norms ∥hj∥\|h_j\|∥hj​∥, time ttt, and trace-distance error εεε. The matching upper bound (known as composite qDRIFT) consists of high-order Trotterization of the large terms and a randomized first-order Trotterization of the small terms. Unlike prior work that chooses worst-case ∥hj∥\|h_j\|∥hj​∥ to encode the computation of parity or other Boolean functions in time evolution, our proof is elementary and based on a local, bounded-degree classical Hamiltonian. Our work suggests that for many physical systems (e.g., power-law interactions), gate count must scale polynomially in 1/ε1/ε1/ε, contrary to the complexity suggested by counting coherent oracle queries such as those in the block-encoding model.
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.
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.