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:2605.29279

Permutation Matrix Representation for Quantum Simulation: Comparative Resource Analysis

Hriday Sabharwal, Itay Hen

quant-phSubmitted May 28, 2026• Announced May 29, 2026• 0 citations
arXivHTMLPDF

Abstract

We present a comparative study of the permutation matrix representation (PMR) method for Hamiltonian simulation alongside other leading quantum algorithms. Our analysis focuses on resource costs for simulating both time-independent and time-dependent Hamiltonians. For the time-independent case, we benchmark PMR against quantum signal processing (QSP) and qubitization, using the Rydberg interaction Hamiltonian as a representative example. For the time-dependent case, we compare the time-dependent extension of PMR with the quantum highly oscillatory protocol (qHOP), applied to a Floquet-driven transverse field Ising model in arbitrary spatial dimensions. In both regimes, we find that PMR offers complementary advantages in resource requirements and exhibits favorable scaling with certain system parameters, suggesting that it may provide practical benefits on resource-constrained quantum hardware.

Comments
14 pages, 2 tables. Comments are welcome

Related papers

Permutation matrix representation quantum Monte Carlo

Lalit Gupta, Tameem Albash, Itay Hen

Abstract We present a quantum Monte Carlo algorithm for the simulation of general quantum and classical many-body models within a single unifying framework. The algorithm builds on a power series expansion of the quantum partition function in its off-diagonal terms and is both parameter-free and Trotter error-free. In our approach, the quantum dimension consists of products of elements of a permutation group. As such, it allows for the study of a very wide variety of models on an equal footing. To demonstrate the utility of our technique, we use it to clarify the emergence of the sign problem in the simulations of non-stoquastic physical models. We showcase the flexibility of our algorithm and the advantages it offers over existing state-of-the-art by simulating transverse-field Ising model Hamiltonians and comparing the performance of our technique against that of the stochastic series expansion algorithm. We also study a transverse-field Ising model augmented with randomly chosen two-body transverse-field interactions.

arXiv:1908.03740•Journal of Statistical Mechanics Theory and Experiment•Jul 1, 2020•15 citations

Quantum Algorithm for Time-Dependent Hamiltonian Simulation by Permutation Expansion

Yi‐Hsiang Chen, Amir Kalev, Itay Hen

We present a quantum algorithm for the dynamical simulation of time-dependent Hamiltonians.Our method involves expanding the interaction-picture Hamiltonian as a sum of generalized permutations, which leads to an integral-free Dyson series of the time-evolution operator.Under this representation, we perform a quantum simulation for the time-evolution operator by means of the linear combination of unitaries technique.We optimize the time steps of the evolution based on the Hamiltonian's dynamical characteristics, leading to a gate count that scales with an L 1 -norm-like scaling with respect only to the norm of the interaction Hamiltonian, rather than that of the total Hamiltonian.We demonstrate that the cost of the algorithm is independent of the Hamiltonian's frequencies, implying its advantage for systems with highly oscillating components, and for time-decaying systems the cost does not scale with the total evolution time asymptotically.In addition, our algorithm retains the near optimal log(1/ )/ log log(1/ ) scaling with simulation error .

arXiv:2103.15334•PRX Quantum•Sep 9, 2021•31 citations

Time-Dependent Hamiltonian Simulation Using Discrete-Clock Constructions

Jacob Watkins, Nathan Wiebe, Alessandro Roggero +1 more

Compared with time-independent Hamiltonians, the dynamics of generic quantum Hamiltonians H ( t ) are complicated by the presence of time ordering in the evolution operator. In the context of digital quantum simulation, this difficulty prevents a direct adaptation of many time-independent simulation algorithms for time-dependent simulation. However, there exists a framework within the theory of dynamical systems that eliminates time ordering by adding a “clock” degree of freedom. In this work, we provide a computational framework, based on this reduction, for encoding time-dependent dynamics as time-independent systems. As a result, we make two advances in digital Hamiltonian simulation. First, we create a time-dependent simulation algorithm based on performing qubitization on the augmented clock system and, in doing so, provide the first qubitization-based approach to time-dependent Hamiltonians that goes beyond Trotterization of the ordered exponential. Second, we define a natural generalization of multiproduct formulas for time-ordered exponentials and then propose and analyze an algorithm based on these formulas. Unlike other algorithms of similar accuracy, the multiproduct approach achieves commutator scaling, meaning that this method outperforms existing methods for physically local time-dependent Hamiltonians with sufficient smoothness. Our work reduces the disparity between time-dependent and time-independent simulation and indicates a step toward optimal quantum simulation of time-dependent Hamiltonians. Published by the American Physical Society 2024

arXiv:2203.11353•PRX Quantum•Oct 31, 2024•24 citations

Efficient quantum algorithm for simulating a time-dependent Hamiltonian that commutes at different times

Nhat A. Nghiem

We describe a quantum algorithm to simulate the time-dependent Hamiltonian, extending the methodology of quantum signal processing. The framework achieves optimal scaling up to some factor with respect to other parameters, and is nearly optimal in inverse of error tolerance, which could be improved to optimal scaling under certain input models. As applications, we discuss the problem of simulating tje generalized lattice system and time-periodic, or Floquet system, showing that our framework provides a neater yet highly efficient solution, achieving nearly optimal scaling in all parameters. In particular, our method also paves a new way for studying phase transition on quantum computer, extending the reach of quantum simulation.

Physical Review A•Sep 16, 2025•1 citation

Algorithms for quantum simulation: design, analysis, implementation, and application

Yuan Su

Simulating the Hamiltonian dynamics of quantum systems is one of the most promising applications of digital quantum computers. In this dissertation, we develop an understanding of quantum simulation algorithms concerning their design, analysis, implementation, and application. We implement three leading simulation algorithms, employing diverse techniques to tighten their error analyses and optimize circuit implementations. We produce concrete resource estimates for simulating a Heisenberg spin system, a problem arising in condensed matter physics that is otherwise difficult to solve on a classical computer. The resulting circuits are orders of magnitude smaller than those for the simplest classically-infeasible instances of factoring and quantum chemistry, suggesting the simulation of spin systems as a promising candidate for an early demonstration of practical quantum computation. We design new simulation algorithms by using classical randomness. We show that by simply randomizing how the terms in the Hamiltonian are ordered, one can prove stronger bounds for product formulas and thereby give more efficient quantum simulations. We also develop a classical sampler for time-dependent Hamiltonians, using which we give a simulation algorithm that substantially improves over previous approaches when the Hamiltonian varies significantly with time. We propose a general theory to analyzing product formulas, an approach to quantum simulation widely used in experimental demonstrations but whose error scaling was poorly understood. Our approach directly exploits the commutativity of Hamiltonian, overcoming the limitations of prior error analyses. We prove new speedups of product formulas for simulating many quantum systems, including simulations of nearest-neighbor lattice systems, second-quantized plane-wave electronic structure, $k$-local Hamiltonians, rapidly decaying power-law interactions, and clustered Hamiltonians, nearly matching or even outperforming the best previous results in quantum simulation. We accompany our analysis with numerical calculation, which suggests that the bounds also have nearly tight constant prefactors. We identify applications of quantum simulation to designing other quantum algorithms and improving quantum Monte Carlo methods. We develop an algorithmic framework ``quantum singular value transformation'' using techniques from quantum simulation and apply it to implement principal component regression. We also apply our new analysis of product formulas and obtain improved quantum Monte Carlo simulations of the transverse field Ising model and quantum ferromagnets.

•Jan 1, 2020•0 citations

Quantum algorithm for differential equations via permutation matrix representation with application to the Burgers equation

Hriday Sabharwal, Amir Kalev, Itay Hen

We develop a quantum algorithm for solving the dynamics of the nonlinear viscous Burgers equation. We apply the Carleman linearization procedure on the spatially discretized equation, followed by a padding scheme that allows implementation on qubit registers. Existing Carleman-based quantum algorithms commonly formulate the lifted linear differential equation in an oracle model. Here we decompose the padded generator into diagonal masks and reversible arithmetic permutations using the Permutation Matrix Representation (PMR), which we show to be naturally compatible with the Linear Combination of Hamiltonian Simulations (LCHS) algorithm. Under the assumptions required by LCHS - most importantly positive semidefiniteness of the Hermitian part of the linear generator, possibly after a stabilizing shift - the algorithm prepares a normalized quantum state proportional to the solution of the truncated lifted system; the stabilizing shift introduces an exponential postselection overhead, which we quantify and mitigate through a rescaling scheme. We show that our algorithm scales with the off-diagonal norm of the Carleman generator instead of the matrix norm, which can be advantageous for other generators that are diagonally dominant. We also extend the PMR scheme to general fluid equations that may contain higher-order derivatives or nonlinear terms, or may involve multiple fluid variables or spatial dimensions. The construction illustrates how PMR can serve as a convenient Hamiltonian-simulation primitive for a broader class of LCU-based algorithms.

quant-pharXiv:2608.19508•Aug 21, 2026•0 citations
We present a comparative study of the permutation matrix representation (PMR) method for Hamiltonian simulation alongside other leading quantum algorithms. Our analysis focuses on resource costs for simulating both time-independent and time-dependent Hamiltonians. For the time-independent case, we benchmark PMR against quantum signal processing (QSP) and qubitization, using the Rydberg interaction Hamiltonian as a representative example. For the time-dependent case, we compare the time-dependent extension of PMR with the quantum highly oscillatory protocol (qHOP), applied to a Floquet-driven transverse field Ising model in arbitrary spatial dimensions. In both regimes, we find that PMR offers complementary advantages in resource requirements and exhibits favorable scaling with certain system parameters, suggesting that it may provide practical benefits on resource-constrained quantum hardware.
Abstract We present a quantum Monte Carlo algorithm for the simulation of general quantum and classical many-body models within a single unifying framework. The algorithm builds on a power series expansion of the quantum partition function in its off-diagonal terms and is both parameter-free and Trotter error-free. In our approach, the quantum dimension consists of products of elements of a permutation group. As such, it allows for the study of a very wide variety of models on an equal footing. To demonstrate the utility of our technique, we use it to clarify the emergence of the sign problem in the simulations of non-stoquastic physical models. We showcase the flexibility of our algorithm and the advantages it offers over existing state-of-the-art by simulating transverse-field Ising model Hamiltonians and comparing the performance of our technique against that of the stochastic series expansion algorithm. We also study a transverse-field Ising model augmented with randomly chosen two-body transverse-field interactions.
We present a quantum algorithm for the dynamical simulation of time-dependent Hamiltonians.Our method involves expanding the interaction-picture Hamiltonian as a sum of generalized permutations, which leads to an integral-free Dyson series of the time-evolution operator.Under this representation, we perform a quantum simulation for the time-evolution operator by means of the linear combination of unitaries technique.We optimize the time steps of the evolution based on the Hamiltonian's dynamical characteristics, leading to a gate count that scales with an L 1 -norm-like scaling with respect only to the norm of the interaction Hamiltonian, rather than that of the total Hamiltonian.We demonstrate that the cost of the algorithm is independent of the Hamiltonian's frequencies, implying its advantage for systems with highly oscillating components, and for time-decaying systems the cost does not scale with the total evolution time asymptotically.In addition, our algorithm retains the near optimal log(1/ )/ log log(1/ ) scaling with simulation error .
Compared with time-independent Hamiltonians, the dynamics of generic quantum Hamiltonians H ( t ) are complicated by the presence of time ordering in the evolution operator. In the context of digital quantum simulation, this difficulty prevents a direct adaptation of many time-independent simulation algorithms for time-dependent simulation. However, there exists a framework within the theory of dynamical systems that eliminates time ordering by adding a “clock” degree of freedom. In this work, we provide a computational framework, based on this reduction, for encoding time-dependent dynamics as time-independent systems. As a result, we make two advances in digital Hamiltonian simulation. First, we create a time-dependent simulation algorithm based on performing qubitization on the augmented clock system and, in doing so, provide the first qubitization-based approach to time-dependent Hamiltonians that goes beyond Trotterization of the ordered exponential. Second, we define a natural generalization of multiproduct formulas for time-ordered exponentials and then propose and analyze an algorithm based on these formulas. Unlike other algorithms of similar accuracy, the multiproduct approach achieves commutator scaling, meaning that this method outperforms existing methods for physically local time-dependent Hamiltonians with sufficient smoothness. Our work reduces the disparity between time-dependent and time-independent simulation and indicates a step toward optimal quantum simulation of time-dependent Hamiltonians. Published by the American Physical Society 2024
We describe a quantum algorithm to simulate the time-dependent Hamiltonian, extending the methodology of quantum signal processing. The framework achieves optimal scaling up to some factor with respect to other parameters, and is nearly optimal in inverse of error tolerance, which could be improved to optimal scaling under certain input models. As applications, we discuss the problem of simulating tje generalized lattice system and time-periodic, or Floquet system, showing that our framework provides a neater yet highly efficient solution, achieving nearly optimal scaling in all parameters. In particular, our method also paves a new way for studying phase transition on quantum computer, extending the reach of quantum simulation.
Simulating the Hamiltonian dynamics of quantum systems is one of the most promising applications of digital quantum computers. In this dissertation, we develop an understanding of quantum simulation algorithms concerning their design, analysis, implementation, and application. We implement three leading simulation algorithms, employing diverse techniques to tighten their error analyses and optimize circuit implementations. We produce concrete resource estimates for simulating a Heisenberg spin system, a problem arising in condensed matter physics that is otherwise difficult to solve on a classical computer. The resulting circuits are orders of magnitude smaller than those for the simplest classically-infeasible instances of factoring and quantum chemistry, suggesting the simulation of spin systems as a promising candidate for an early demonstration of practical quantum computation. We design new simulation algorithms by using classical randomness. We show that by simply randomizing how the terms in the Hamiltonian are ordered, one can prove stronger bounds for product formulas and thereby give more efficient quantum simulations. We also develop a classical sampler for time-dependent Hamiltonians, using which we give a simulation algorithm that substantially improves over previous approaches when the Hamiltonian varies significantly with time. We propose a general theory to analyzing product formulas, an approach to quantum simulation widely used in experimental demonstrations but whose error scaling was poorly understood. Our approach directly exploits the commutativity of Hamiltonian, overcoming the limitations of prior error analyses. We prove new speedups of product formulas for simulating many quantum systems, including simulations of nearest-neighbor lattice systems, second-quantized plane-wave electronic structure, kkk-local Hamiltonians, rapidly decaying power-law interactions, and clustered Hamiltonians, nearly matching or even outperforming the best previous results in quantum simulation. We accompany our analysis with numerical calculation, which suggests that the bounds also have nearly tight constant prefactors. We identify applications of quantum simulation to designing other quantum algorithms and improving quantum Monte Carlo methods. We develop an algorithmic framework ``quantum singular value transformation'' using techniques from quantum simulation and apply it to implement principal component regression. We also apply our new analysis of product formulas and obtain improved quantum Monte Carlo simulations of the transverse field Ising model and quantum ferromagnets.
We develop a quantum algorithm for solving the dynamics of the nonlinear viscous Burgers equation. We apply the Carleman linearization procedure on the spatially discretized equation, followed by a padding scheme that allows implementation on qubit registers. Existing Carleman-based quantum algorithms commonly formulate the lifted linear differential equation in an oracle model. Here we decompose the padded generator into diagonal masks and reversible arithmetic permutations using the Permutation Matrix Representation (PMR), which we show to be naturally compatible with the Linear Combination of Hamiltonian Simulations (LCHS) algorithm. Under the assumptions required by LCHS - most importantly positive semidefiniteness of the Hermitian part of the linear generator, possibly after a stabilizing shift - the algorithm prepares a normalized quantum state proportional to the solution of the truncated lifted system; the stabilizing shift introduces an exponential postselection overhead, which we quantify and mitigate through a rescaling scheme. We show that our algorithm scales with the off-diagonal norm of the Carleman generator instead of the matrix norm, which can be advantageous for other generators that are diagonally dominant. We also extend the PMR scheme to general fluid equations that may contain higher-order derivatives or nonlinear terms, or may involve multiple fluid variables or spatial dimensions. The construction illustrates how PMR can serve as a convenient Hamiltonian-simulation primitive for a broader class of LCU-based algorithms.