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:2401.08550 · Quantum

Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding

Jiaqi Leng, Joseph Li, Yuxiang Peng, Xiaodi Wu

Published Sep 11, 2025• 2 citations
arXivHTMLPDF

Abstract

Many promising quantum applications depend on the efficient quantum simulation of an exponentially large sparse Hamiltonian, a task known as sparse Hamiltonian simulation, which is fundamentally important in quantum computation. Although several theoretically appealing quantum algorithms have been proposed for this task, they typically require a black-box query model of the sparse Hamiltonian, rendering them impractical for near-term implementation on quantum devices.In this paper, we propose a technique named Hamiltonian embedding . This technique simulates a desired sparse Hamiltonian by embedding it into the evolution of a larger and more structured quantum system, allowing for more efficient simulation through hardware-efficient operations. We conduct a systematic study of this new technique and demonstrate significant savings in computational resources for implementing prominent quantum applications. As a result, we can now experimentally realize quantum walks on complicated graphs (e.g., binary trees, glued-tree graphs), quantum spatial search, and the simulation of real-space Schrödinger equations on current trapped-ion and neutral-atom platforms. Given the fundamental role of Hamiltonian evolution in the design of quantum algorithms, our technique markedly expands the horizon of implementable quantum advantages in the NISQ era.

DOI
10.22331/q-2025-09-11-1857

Related papers

Resource-efficient quantum simulation of transport phenomena via Hamiltonian embedding

Joseph Li, Gengzhi Yang, Jiaqi Leng +1 more

Transport phenomena play a key role in a variety of application domains, and efficient simulation of these dynamics remains an outstanding challenge. While quantum computers offer potential for significant speedups, existing algorithms either lack rigorous theoretical guarantees or demand substantial quantum resources, preventing scalable and efficient validation on realistic quantum hardware. To address this gap, we develop a comprehensive framework for simulating classes of transport equations, offering both rigorous theoretical guarantees -- including exponential speedups in specific cases -- and a systematic, hardware-efficient implementation. Central to our approach is the Hamiltonian embedding technique, a white-box approach for end-to-end simulation of sparse Hamiltonians that avoids abstract query models and retains near-optimal asymptotic complexity. Empirical resource estimates indicate that our approach can yield an order-of-magnitude (e.g., $42\times$) reduction in circuit depth given favorable problem structures. We then apply our framework to solve linear and nonlinear transport PDEs, including the first experimental demonstration of a 2D advection equation on a trapped-ion quantum computer.

quant-pharXiv:2602.03099•Quantum Science and Technology•Feb 4, 2026•0 citations

Black-box Hamiltonian simulation and unitary implementation

Andrew M. Childs, Dominic William Berry

We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness $\sparseness$ (the maximum number of nonzero elements in a column) and the evolution time $t$, whereas previous methods had complexity scaling as $\sparseness^4$ and were superlinear in $t$. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified $\UN\times\UN$ unitary operation use $\tilde O(\UN^2)$ elementary gates, we show that a black-box unitary can be performed with bounded error using $O(\UN^{2/3} (\log\log \UN)^{4/3})$ queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only $\tilde O(\sqrt{\UN})$ queries, which is optimal.

Quantum Information and Computation•Jan 1, 2012•101 citations

Black-box hamiltonian simulation and unitary implementation

Dominic William Berry, Andrew M. Childs

We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness D (the maximum number of nonzero elements in a column) and the evolution time t, whereas previous methods had complexity scaling as D4 and were superlinear in t. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified N × N unitary operation use O(N2) elementary gates, we show that a black-box unitary can be performed with bounded error using O(N2/3(log logN)4/3) queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only O(√N) queries, which is optimal.

Quantum Information and Computation•Jan 1, 2012•100 citations

Quantum simulations for non-unitary operators: Techniques, applications

Krishnageetha Karuppasamy

The rapid advancement of quantum computing has created new opportunities for solving computationally intensive problems across diverse fields such as optimization, physical system simulation, and machine learning. However, practical implementation on Noisy Intermediate-Scale Quantum (NISQ) devices remains challenging due to hardware limitations including noise, decoherence, and restricted qubit connectivity. A fundamental constraint further complicating this effort is that all quantum operations must be unitary, while many real-world problems are naturally expressed in non-unitary forms. This discrepancy necessitates novel techniques for transforming non-unitary mathematical structures into unitary or Hamiltonian representations compatible with quantum hardware.This thesis proposes a unified framework for converting structured, sparse, or otherwise non-unitary classical matrices into unitary forms that can be executed efficiently on NISQ devices. The methodology introduces general transformation strategies such as linear combinations of unitaries, structured embeddings, and resource-aware circuit construction, enabling the deployment of quantum algorithms without incurring prohibitive overhead. Each technique is developed with an emphasis on preserving problem structure, minimizing circuit depth, and ensuring compatibility with IBM’s NISQ hardware. The proposed frameworks are validated through theoretical analysis and quantum simulations, with performance benchmarks based on gate count, circuit fidelity, convergence behavior, and scalability. This work demonstrates how non-unitary formulations arising in various computational contexts can be systematically adapted for quantum execution, advancing the practical utility of NISQ-era devices.

•May 1, 2026•0 citations

Efficient Simulation of Szegedy Quantum Walk Formulations and Algorithms

Sergio A. Ortega, Daniel K. Park

Quantum walks provide a versatile framework for quantum algorithms across a wide range of applications. We develop efficient classical simulation methods for Szegedy quantum walks that avoid explicit construction of the full unitary evolution operator. Unlike previous approaches restricted to a particular walk formulation, our framework is built from fundamental update and reflection operators, enabling the simulation of a broader class of Szegedy walk formulations. We further extend these methods to phase-estimation-based algorithms coupled to the walk, including implementations suitable for large sparse graphs. The resulting methods achieve optimal $O(N^2)$ complexity for dense graphs with $N$ nodes. For sparse graphs, the computational cost scales linearly with the number of edges, which is $O(N)$ in many cases. We implement the framework in the Python package SQWLib and illustrate its capabilities through simulations of representative algorithms, including quantum simulated annealing and quantum search on graphs. These results provide a practical tool for studying Szegedy-walk-based algorithms numerically beyond purely analytical treatments.

quant-pharXiv:2606.14226•Jun 15, 2026•0 citations

On the quantum simulation of complex networks

Duarte Magano, João P. Moutinho, Bruno Coelho Coutinho

Quantum walks provide a natural framework to approach graph problems with quantum computers, exhibiting speedups over their classical counterparts for tasks such as the search for marked nodes or the prediction of missing links. Continuous-time quantum walk algorithms assume that we can simulate the dynamics of quantum systems where the Hamiltonian is given by the adjacency matrix of the graph. It is known that such can be simulated efficiently if the underlying graph is row-sparse and efficiently row-computable. While this is sufficient for many applications, it limits the applicability for this class of algorithms to study real world complex networks, which, among other properties, are characterized by the existence of a few densely connected nodes, called hubs. In other words, complex networks are typically not row-sparse, even though the average connectivity over all nodes can be very small. In this work, we extend the state-of-the-art results on quantum simulation to graphs that contain a small number of hubs, but that are otherwise sparse. Hopefully, our results may lead to new applications of quantum computing to network science.

arXiv:2212.06126•SciPost Physics Core•Aug 24, 2023•6 citations
Many promising quantum applications depend on the efficient quantum simulation of an exponentially large sparse Hamiltonian, a task known as sparse Hamiltonian simulation, which is fundamentally important in quantum computation. Although several theoretically appealing quantum algorithms have been proposed for this task, they typically require a black-box query model of the sparse Hamiltonian, rendering them impractical for near-term implementation on quantum devices.In this paper, we propose a technique named Hamiltonian embedding . This technique simulates a desired sparse Hamiltonian by embedding it into the evolution of a larger and more structured quantum system, allowing for more efficient simulation through hardware-efficient operations. We conduct a systematic study of this new technique and demonstrate significant savings in computational resources for implementing prominent quantum applications. As a result, we can now experimentally realize quantum walks on complicated graphs (e.g., binary trees, glued-tree graphs), quantum spatial search, and the simulation of real-space Schrödinger equations on current trapped-ion and neutral-atom platforms. Given the fundamental role of Hamiltonian evolution in the design of quantum algorithms, our technique markedly expands the horizon of implementable quantum advantages in the NISQ era.
Transport phenomena play a key role in a variety of application domains, and efficient simulation of these dynamics remains an outstanding challenge. While quantum computers offer potential for significant speedups, existing algorithms either lack rigorous theoretical guarantees or demand substantial quantum resources, preventing scalable and efficient validation on realistic quantum hardware. To address this gap, we develop a comprehensive framework for simulating classes of transport equations, offering both rigorous theoretical guarantees -- including exponential speedups in specific cases -- and a systematic, hardware-efficient implementation. Central to our approach is the Hamiltonian embedding technique, a white-box approach for end-to-end simulation of sparse Hamiltonians that avoids abstract query models and retains near-optimal asymptotic complexity. Empirical resource estimates indicate that our approach can yield an order-of-magnitude (e.g., 42×42\times42×) reduction in circuit depth given favorable problem structures. We then apply our framework to solve linear and nonlinear transport PDEs, including the first experimental demonstration of a 2D advection equation on a trapped-ion quantum computer.
We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness $\sparseness$ (the maximum number of nonzero elements in a column) and the evolution time ttt, whereas previous methods had complexity scaling as $\sparseness^4$ and were superlinear in ttt. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified $\UN\times\UN$ unitary operation use $\tilde O(\UN^2)$ elementary gates, we show that a black-box unitary can be performed with bounded error using $O(\UN^{2/3} (\log\log \UN)^{4/3})$ queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only $\tilde O(\sqrt{\UN})$ queries, which is optimal.
We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness D (the maximum number of nonzero elements in a column) and the evolution time t, whereas previous methods had complexity scaling as D4 and were superlinear in t. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified N × N unitary operation use O(N2) elementary gates, we show that a black-box unitary can be performed with bounded error using O(N2/3(log logN)4/3) queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only O(√N) queries, which is optimal.
The rapid advancement of quantum computing has created new opportunities for solving computationally intensive problems across diverse fields such as optimization, physical system simulation, and machine learning. However, practical implementation on Noisy Intermediate-Scale Quantum (NISQ) devices remains challenging due to hardware limitations including noise, decoherence, and restricted qubit connectivity. A fundamental constraint further complicating this effort is that all quantum operations must be unitary, while many real-world problems are naturally expressed in non-unitary forms. This discrepancy necessitates novel techniques for transforming non-unitary mathematical structures into unitary or Hamiltonian representations compatible with quantum hardware.This thesis proposes a unified framework for converting structured, sparse, or otherwise non-unitary classical matrices into unitary forms that can be executed efficiently on NISQ devices. The methodology introduces general transformation strategies such as linear combinations of unitaries, structured embeddings, and resource-aware circuit construction, enabling the deployment of quantum algorithms without incurring prohibitive overhead. Each technique is developed with an emphasis on preserving problem structure, minimizing circuit depth, and ensuring compatibility with IBM’s NISQ hardware. The proposed frameworks are validated through theoretical analysis and quantum simulations, with performance benchmarks based on gate count, circuit fidelity, convergence behavior, and scalability. This work demonstrates how non-unitary formulations arising in various computational contexts can be systematically adapted for quantum execution, advancing the practical utility of NISQ-era devices.
Quantum walks provide a versatile framework for quantum algorithms across a wide range of applications. We develop efficient classical simulation methods for Szegedy quantum walks that avoid explicit construction of the full unitary evolution operator. Unlike previous approaches restricted to a particular walk formulation, our framework is built from fundamental update and reflection operators, enabling the simulation of a broader class of Szegedy walk formulations. We further extend these methods to phase-estimation-based algorithms coupled to the walk, including implementations suitable for large sparse graphs. The resulting methods achieve optimal O(N2)O(N^2)O(N2) complexity for dense graphs with NNN nodes. For sparse graphs, the computational cost scales linearly with the number of edges, which is O(N)O(N)O(N) in many cases. We implement the framework in the Python package SQWLib and illustrate its capabilities through simulations of representative algorithms, including quantum simulated annealing and quantum search on graphs. These results provide a practical tool for studying Szegedy-walk-based algorithms numerically beyond purely analytical treatments.
Quantum walks provide a natural framework to approach graph problems with quantum computers, exhibiting speedups over their classical counterparts for tasks such as the search for marked nodes or the prediction of missing links. Continuous-time quantum walk algorithms assume that we can simulate the dynamics of quantum systems where the Hamiltonian is given by the adjacency matrix of the graph. It is known that such can be simulated efficiently if the underlying graph is row-sparse and efficiently row-computable. While this is sufficient for many applications, it limits the applicability for this class of algorithms to study real world complex networks, which, among other properties, are characterized by the existence of a few densely connected nodes, called hubs. In other words, complex networks are typically not row-sparse, even though the average connectivity over all nodes can be very small. In this work, we extend the state-of-the-art results on quantum simulation to graphs that contain a small number of hubs, but that are otherwise sparse. Hopefully, our results may lead to new applications of quantum computing to network science.