Cover Image

Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Benchasattabuse, Naphan, Bärtschi, Andreas, García-Pintos, Luis Pedro, Golden, John, Lemons, Nathan, Eidenbenz, Stephan
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

Trainability Barriers in Low-Depth QAOA Landscapes
by: Rajakumar, Joel, et al.
Published: (2024)

Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
by: Pelofske, Elijah, et al.
Published: (2023)

Scalable Experimental Bounds for Entangled Quantum State Fidelities
by: Aktar, Shamminuj, et al.
Published: (2022)

Probing Quantum Telecloning on Superconducting Quantum Processors
by: Pelofske, Elijah, et al.
Published: (2023)

Better approximation guarantee for Asymmetric TSP
by: Vygen, Jens
Published: (2026)

Improved approximation algorithms for the EPR Hamiltonian
by: Ju, Nathan, et al.
Published: (2025)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
by: Singer, Noah G.
Published: (2025)

A $(2+\varepsilon)$-approximation algorithm for the general scheduling problem in quasipolynomial time
by: Armbruster, Alexander, et al.
Published: (2025)

Increasing the Measured Effective Quantum Volume with Zero Noise Extrapolation
by: Pelofske, Elijah, et al.
Published: (2023)

Improved approximation ratio for covering pliable set families
by: Nutov, Zeev
Published: (2024)

Simple approximation algorithms for Polyamorous Scheduling
by: Biktairov, Yuriy, et al.
Published: (2024)

Testable algorithms for approximately counting edges and triangles in sublinear time and space
by: Eden, Talya, et al.
Published: (2025)

An O(nlogn) approximate knapsack algorithm
by: Dawes, Nick
Published: (2025)

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
by: Kolmogorov, Vladimir
Published: (2023)

An approximation algorithm for Maximum DiCut vs. Cut
by: Nakajima, Tamio-Vesa, et al.
Published: (2024)

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

Parameterized and approximation algorithms for coverings points with segments in the plane
by: Kowalska, Katarzyna, et al.
Published: (2024)

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

Efficient parameterized approximation
by: Kratsch, Stefan, et al.
Published: (2025)

An $2\sqrt{k}$-approximation algorithm for minimum power $k$ edge disjoint $st$ -paths
by: Nutov, Zeev
Published: (2022)

Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes
by: Velusamy, Santhoshini
Published: (2025)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
by: Chakraborty, Dibyayan, et al.
Published: (2024)

A tight example for approximation ratio 5 for covering small cuts by the primal-dual method
by: Nutov, Zeev
Published: (2025)

Tight Lieb-Robinson Bound for approximation ratio in Quantum Annealing
by: Braida, Arthur, et al.
Published: (2023)

Expected Maximin Fairness in Max-Cut and other Combinatorial Optimization Problems
by: Salem, Jad, et al.
Published: (2024)

New approximate distance oracles and their applications
by: Kadria, Avi, et al.
Published: (2025)

Bicriteria approximation for $k$-edge-connectivity
by: Nutov, Zeev, et al.
Published: (2025)

Theoretical Approximation Ratios for Warm-Started QAOA on 3-Regular Max-Cut Instances at Depth $p=1$
by: Tate, Reuben, et al.
Published: (2024)

Sketching approximations and LP approximations for finite CSPs are related
by: Singer, Noah G., et al.
Published: (2025)

Fast approximation algorithms for the 1-median problem on real-world large graphs
by: Ueta, Keisuke, et al.
Published: (2025)

Quantum algorithm for approximating the expected value of a random-exist quantified oracle
by: Rotello, Caleb
Published: (2024)

Near-optimal hierarchical matrix approximation from matrix-vector products
by: Chen, Tyler, et al.
Published: (2024)

Improved bicriteria approximation for $k$-edge-connectivity
by: Nutov, Zeev
Published: (2025)

Improved girth approximation in weighted undirected graphs
by: Kadria, Avi, et al.
Published: (2025)

FPT approximations for Capacitated Sum of Radii and Diameters
by: Filtser, Arnold, et al.
Published: (2024)

On the cut-query complexity of approximating max-cut
by: Plevrakis, Orestis, et al.
Published: (2022)

Beyond 2-approximation for k-Center in Graphs
by: Jin, Ce, et al.
Published: (2025)

A rounding and clustering-based exact algorithm for the p-center problem
by: Ales, Zacharie, et al.
Published: (2024)

A simple $(2+ε)$-approximation for knapsack interdiction
by: Weninger, Noah
Published: (2026)

Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate $k$-clique counts faster
by: Censor-Hillel, Keren, et al.
Published: (2025)