Quantum Time-Space Tradeoffs for Exponential Dynamic Programming

• URL: http://arxiv.org/abs/2604.02233v1
• Date: Thu, 02 Apr 2026 16:28:18 GMT
• Title: Quantum Time-Space Tradeoffs for Exponential Dynamic Programming
• Abstract summary: We study how we can improve the space complexity by trading it for time, while still retaining a speedup over the classical algorithms.<n>We show novel quantum time-space tradeoffs, which we obtain by adjusting the parameters of these algorithms and combining them with "quantized" classical strategies.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate the quantum algorithms for dynamic programming by Ambainis et al. (SODA'19). While giving provable complexity speedups and applicable to a variety of NP-hard problems, these algorithms have a notable drawback: they require a large amount of Quantum Random Access Memory (QRAM), which potentially could be very challenging to implement in a physical quantum computer. In this work, we study how we can improve the space complexity by trading it for time, while still retaining a speedup over the classical algorithms. We show novel quantum time-space tradeoffs, which we obtain by adjusting the parameters of these algorithms and combining them with "quantized" classical strategies.

Related papers

• Quantum DPLL and Generalized Constraints in Iterative Quantum Algorithms [0.0]
  We explore a class of hybrid quantum algorithms that are closely related to classical greedy or local search algorithms.<n>We develop a hybrid quantum version of the well-known classical Davis-Putnam-Logemann-Loveland (DPLL) algorithm for satisfiability problems.
  arXiv  Detail & Related papers  (2025-09-02T18:00:05Z)
• On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality [3.3083504598202733]
  A quantum algorithm offers an exponential speedup over any classical algorithm in simulating classical dynamics with long-range interactions.<n>Many real-world classical systems, such as those arising from partial differential equations, exhibit only local interactions.<n>This work offers new insights into the complexity of classical dynamics governed by partial differential equations.
  arXiv  Detail & Related papers  (2025-05-15T16:06:22Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture [1.072460284847973]
  We show that Variational Quantum Algorithms can be a viable alternative to classical algorithms in the near future. In particular, we compare the performances, in terms of success probability, of two algorithms, i.e., Quantum Approximate Optimization Algorithm (QAOA) and Variational Quantum Eigensolver (VQE) The simulation experiments, performed for a set of simple problems, %CM230124 that involve a Cloud and two Edge nodes, show that the VQE algorithm ensures better performances when it is equipped with appropriate circuit textitansatzes that are able to restrict the search space
  arXiv  Detail & Related papers  (2024-01-25T17:37:40Z)
• 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)
• Parallel-in-time quantum simulation via Page and Wootters quantum time [0.0]
  We present quantum algorithms for parallel-in-time simulations inspired by the Page and Wootters formalism.<n>We show that our algorithms can compute temporal properties over $N$ different times of many-body systems.<n>We rigorously prove that the entanglement created between the system qubits and the clock qubits has operational meaning.
  arXiv  Detail & Related papers  (2023-08-24T17:32:41Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Fast-forwarding quantum simulation with real-time quantum Krylov subspace algorithms [0.0]
  We propose several quantum Krylov fast-forwarding (QKFF) algorithms capable of predicting long-time dynamics well beyond the coherence time of current quantum hardware. Our algorithms use real-time evolved Krylov basis states prepared on the quantum computer and a multi-reference subspace method to ensure convergence towards high-fidelity, long-time dynamics.
  arXiv  Detail & Related papers  (2022-08-01T16:00:20Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• 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)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

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.