Cover Image

On the quantum time complexity of divide and conquer

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Allcock, Jonathan, Bao, Jinge, Belovs, Aleksandrs, Lee, Troy, Santha, Miklos
Format:	Preprint
Published:	2023
Subjects:	Quantum Physics Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Space-Efficient Quantum Error Reduction without log Factors
by: Belovs, Aleksandrs, et al.
Published: (2025)

Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits
by: Allcock, Jonathan, et al.
Published: (2024)

Quantum divide and conquer
by: Childs, Andrew M., et al.
Published: (2022)

Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
by: Allcock, Jonathan, et al.
Published: (2025)

Quantum algorithms and lower bounds for eccentricity, radius, and diameter in undirected graphs
by: Wesołowski, Adam, et al.
Published: (2025)

A divide and conquer strategy for multinomial particle filter resampling
by: Popov, Andrey A.
Published: (2026)

Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime
by: Aggarwal, Divesh, et al.
Published: (2024)

A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs
by: Apers, Simon, et al.
Published: (2021)

Nonlinear transformation of complex amplitudes via quantum singular value transformation
by: Guo, Naixu, et al.
Published: (2021)

Non-unitary enhanced transfer efficiency in quantum walk search on complex networks
by: Nzongani, Ugo, et al.
Published: (2025)

Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs
by: Jennings, David, et al.
Published: (2023)

Heisenberg-limited Hamiltonian learning without short-time control
by: Shin, Myeongjin, et al.
Published: (2026)

Elfs, trees and quantum walks
by: Apers, Simon, et al.
Published: (2022)

Simulating quantum collision models with Hamiltonian simulations using early fault-tolerant quantum computers
by: Garg, Kushagra, et al.
Published: (2025)

Randomized and quantum approximate matrix multiplication
by: Apers, Simon, et al.
Published: (2025)

Quartic quantum speedups for community detection
by: Schmidhuber, Alexander, et al.
Published: (2025)

Quantum singular value transformation without block encodings: Near-optimal complexity with minimal ancilla
by: Chakraborty, Shantanav, et al.
Published: (2025)

Mixing time of quantum Gibbs sampling for random sparse Hamiltonians
by: Ramkumar, Akshar, et al.
Published: (2024)

Variational ground-state quantum adiabatic theorem
by: Žunkovič, Bojan, et al.
Published: (2024)

Big data applications on small quantum computers
by: Yogendran, Boniface, et al.
Published: (2024)

Analysis of sum-of-squares relaxations for the quantum rotor model
by: Rao, Sujit
Published: (2023)

A quantum algorithm for solving 0-1 Knapsack problems
by: Wilkening, Sören, et al.
Published: (2023)

Assessing fault-tolerant quantum advantage for $k$-SAT with structure
by: Brehm, Martijn, et al.
Published: (2024)

Basic quantum subroutines: finding multiple marked elements and summing numbers
by: van Apeldoorn, Joran, et al.
Published: (2023)

(No) Quantum space-time tradeoff for USTCON
by: Apers, Simon, et al.
Published: (2022)

Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact
by: Wang, Qingwen, et al.
Published: (2024)

Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
by: Benchasattabuse, Naphan, et al.
Published: (2023)

A simple analysis of a quantum-inspired algorithm for solving low-rank linear systems
by: Chen, Tyler, et al.
Published: (2025)

A unified approach to quantum de Finetti theorems and SoS rounding via geometric quantization
by: Rao, Sujit
Published: (2024)

Simulating Gaussian boson sampling on graphs in polynomial time
by: Anand, Konrad, et al.
Published: (2025)

A Dobrushin condition for quantum Markov chains: Rapid mixing and conditional mutual information at high temperature
by: Bakshi, Ainesh, et al.
Published: (2025)

Revisiting Majumdar-Ghosh spin chain model and Max-cut problem using variational quantum algorithms
by: Britant, et al.
Published: (2024)

Learning quantum Hamiltonians at any temperature in polynomial time
by: Bakshi, Ainesh, et al.
Published: (2023)

The PRODSAT phase of random quantum satisfiability
by: Lee, Joon, et al.
Published: (2024)

A 0.8395-approximation algorithm for the EPR problem
by: Apte, Anuj, et al.
Published: (2025)

A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem
by: Xie, Ningyi, et al.
Published: (2023)

Certifying and learning local quantum Hamiltonians
by: Bluhm, Andreas, et al.
Published: (2026)

Provably faster randomized and quantum algorithms for $k$-means clustering via uniform sampling
by: Chen, Tyler, et al.
Published: (2025)

Improved quantum algorithms for linear and nonlinear differential equations
by: Krovi, Hari
Published: (2022)

Accuracy and resource advantages of quantum eigenvalue estimation with non-Hermitian transcorrelated electronic Hamiltonians
by: Uvarov, Alexey, et al.
Published: (2025)