Demonstration of Exponential Quantum Speedup with Constant-Depth Compiled Circuits for Simon's Problem

• URL: http://arxiv.org/abs/2604.27457v1
• Date: Thu, 30 Apr 2026 05:52:49 GMT
• Title: Demonstration of Exponential Quantum Speedup with Constant-Depth Compiled Circuits for Simon's Problem
• Abstract summary: We demonstrate exponential quantum speedup for a restricted-Hamming-weight version of Simon's problem on present-day superconducting quantum processors.<n>A hardware-aware compilation strategy compiles the quantum part of each Simon query circuit to constant depth.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We demonstrate exponential quantum speedup for a restricted-Hamming-weight version of Simon's problem on present-day superconducting quantum processors by introducing a hardware-aware compilation strategy that compiles the quantum part of each Simon query circuit to constant depth. The resulting compiled circuits have $O(1)$ depth and linear connectivity, map directly onto common device layouts, and avoid additional routing and SWAP overhead. Implemented on IBM's $156$-qubit Boston and $120$-qubit Miami processors, the resulting circuits achieve sufficiently high fidelity to exhibit algorithmic quantum speedup without error suppression. Using the number-of-queries-to-solution metric, we observe exponential speedup over the classical lower bound across the full Hamming-weight range studied on Boston and across low-to-intermediate Hamming weights on Miami; at higher Hamming weights on Miami, we still observe polynomial speedup. The same construction also reaches a regime where the original Simon problem is recovered for the problem sizes studied. These results show that careful hardware-aware compilation can make exponential quantum speedup experimentally accessible for a canonical hidden-subgroup problem in the NISQ regime.

Related papers

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  We give a problem that is solvable by shallow quantum circuits, hard for computation in time under lattice-based assumptions.<n>We prove that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
  arXiv  Detail & Related papers  (2026-09-01T15:54:34Z)
• TrackHHL: The 1-Bit Quantum Filter for particle trajectory reconstruction [0.2089615335919449]
  We introduce the 1-Bit Quantum Filter, a domain-specific adaptation of Harrow-Hassidim-Lloyd (HHL)<n>This work establishes a resource-efficient track reconstruction method capable of solving realistic event topologies on noise-free simulators and smaller tracking scenarios within the current constraints of the Noisy Intermediate Scale (NISQ) era.
  arXiv  Detail & Related papers  (2026-01-12T17:49:04Z)
• Quantum Simulation of Molecular Dynamics Processes - A Benchmark Study Using Classical Simulator and Present-Day Quantum Hardware [0.40498500266986387]
  We explore how the fundamental problems in quantum molecular dynamics can be modelled using classical simulators (emulators) of quantum computers and the actual quantum hardware available to us today.<n>The results of our modelling on classical emulators of quantum hardware agree perfectly with the results obtained using the traditional (classical) methods.<n>However, the results obtained on the actual quantum hardware available today, such as IBM's superconducting qubits and IonQ's trapped ions, indicate large discrepancies due to hardware limitations.
  arXiv  Detail & Related papers  (2025-07-28T17:50:24Z)
• Quantum Compiling with Reinforcement Learning on a Superconducting Processor [55.135709564322624]
  We develop a reinforcement learning-based quantum compiler for a superconducting processor. We demonstrate its capability of discovering novel and hardware-amenable circuits with short lengths. Our study exemplifies the codesign of the software with hardware for efficient quantum compilation.
  arXiv  Detail & Related papers  (2024-06-18T01:49:48Z)
• Quantum Zeno Monte Carlo for computing observables [0.0]
  We introduce Quantum Zeno Monte Carlo (QZMC), a classical-quantum hybrid algorithm that demonstrates resilience to device noise and Trotter errors while showing computational cost for a gapped system.<n>QZMC computes static and dynamic properties without requiring initial state overlap or variational parameters, offering reduced quantum circuit depth.
  arXiv  Detail & Related papers  (2024-03-05T08:32:17Z)
• Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem [0.0]
  Simon's problem is to find a hidden period encoded into an unknown 2-to-1 function.<n>We demonstrate an algorithmic quantum speedup for a variant of Simon's problem where the hidden period has a restricted Hamming weight $w$.
  arXiv  Detail & Related papers  (2024-01-15T19:52:31Z)
• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• Robust Extraction of Thermal Observables from State Sampling and Real-Time Dynamics on Quantum Computers [49.1574468325115]
  We introduce a technique that imposes constraints on the density of states, most notably its non-negativity, and show that this way, we can reliably extract Boltzmann weights from noisy time series. Our work enables the implementation of the time-series algorithm on present-day quantum computers to study finite temperature properties of many-body quantum systems.
  arXiv  Detail & Related papers  (2023-05-30T18:00:05Z)
• Towards the real-time evolution of gauge-invariant $\mathbb{Z}_2$ and $U(1)$ quantum link models on NISQ Hardware with error-mitigation [0.0]
  We benchmark the real-time dynamics of $mathbbZ$ and $U(1)$ gauge in plaquette models using noisy intermediate scale quantum (NISQ) hardware. We design quantum circuits for models of increasing complexity and measure physical observables such as the return probability to the initial state, and locally conserved charges.
  arXiv  Detail & Related papers  (2021-09-30T12:22:21Z)
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation [55.41644538483948]
  Current generation noisy intermediate-scale quantum (NISQ) computers are severely limited in chip size and error rates. We derive localized circuit transformations to efficiently compress quantum circuits for simulation of certain spin Hamiltonians known as free fermions. The proposed numerical circuit compression algorithm behaves backward stable and scales cubically in the number of spins enabling circuit synthesis beyond $mathcalO(103)$ spins.
  arXiv  Detail & Related papers  (2021-08-06T19:38:03Z)
• Long-Time Error-Mitigating Simulation of Open Quantum Systems on Near Term Quantum Computers [38.860468003121404]
  We study an open quantum system simulation on quantum hardware, which demonstrates robustness to hardware errors even with deep circuits containing up to two thousand entangling gates. We simulate two systems of electrons coupled to an infinite thermal bath: 1) a system of dissipative free electrons in a driving electric field; and 2) the thermalization of two interacting electrons in a single orbital in a magnetic field -- the Hubbard atom. Our results demonstrate that algorithms for simulating open quantum systems are able to far outperform similarly complex non-dissipative algorithms on noisy hardware.
  arXiv  Detail & Related papers  (2021-08-02T21:36:37Z)
• Pulse-level noisy quantum circuits with QuTiP [53.356579534933765]
  We introduce new tools in qutip-qip, QuTiP's quantum information processing package. These tools simulate quantum circuits at the pulse level, leveraging QuTiP's quantum dynamics solvers and control optimization features. We show how quantum circuits can be compiled on simulated processors, with control pulses acting on a target Hamiltonian.
  arXiv  Detail & Related papers  (2021-05-20T17:06:52Z)

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.