Cover Image

Exact Quantum Circuit Optimization is co-NQP-hard

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kjelstrøm, Adam Husted, Pavlogiannis, Andreas, van de Pol, Jaco
Format:	Preprint
Published:	2025
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Efficient Simulation of High-Level Quantum Gates
by: Kjelstrøm, Adam Husted, et al.
Published: (2025)

Program Analysis via Multiple Context Free Language Reachability
by: Conrado, Giovanna Kobus, et al.
Published: (2024)

On Exact Sizes of Minimal CNOT Circuits
by: Christensen, Jens Emil, et al.
Published: (2025)

Unconditional Quantum Advantage for Sampling with Shallow Circuits
by: Watts, Adam Bene, et al.
Published: (2023)

Optimising quantum circuits is generally hard
by: van de Wetering, John, et al.
Published: (2023)

Quantum Max-Cut is NP hard to approximate
by: Piddock, Stephen
Published: (2025)

Exponential improvements to the average-case hardness of BosonSampling
by: Bouland, Adam, et al.
Published: (2024)

Quantum Circuit Optimization by Graph Coloring
by: Lee, Hochang, et al.
Published: (2025)

The Power of Shallow-depth Toffoli and Qudit Quantum Circuits
by: Grilo, Alex Bredariol, et al.
Published: (2024)

Thermodynamic Signature of Logical Depth in Quantum Circuits
by: Ibnouhsein, Issam
Published: (2025)

Unconditional Pseudorandomness against Shallow Quantum Circuits
by: Ghosh, Soumik, et al.
Published: (2025)

Improved Circuit Lower Bounds and Quantum-Classical Separations
by: Grewal, Sabee, et al.
Published: (2024)

Classical Simulability of Quantum Circuits with Shallow Magic Depth
by: Zhang, Yifan, et al.
Published: (2024)

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals
by: Grier, Daniel, et al.
Published: (2025)

Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits
by: Fefferman, Bill, et al.
Published: (2024)

Complexity and hardness of random peaked circuits
by: Zhang, Yuxuan
Published: (2025)

On the hardness of cloning and connections to representation theory
by: Havlíček, Vojtěch, et al.
Published: (2024)

Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates
by: Nelson, Jon, et al.
Published: (2024)

The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
by: Kahanamoku-Meyer, Gregory D., et al.
Published: (2024)

How hard is it to verify a classical shadow?
by: Karaiskos, Georgios, et al.
Published: (2025)

DQC1-hardness of estimating correlation functions
by: Moulik, Subhayan Roy, et al.
Published: (2024)

The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits
by: Mondada, Luca, et al.
Published: (2023)

Quantum Event Learning and Gentle Random Measurements
by: Watts, Adam Bene, et al.
Published: (2022)

Fermionic Independent Set and Laplacian of an independence complex are QMA-hard
by: Rayudu, Chaithanya
Published: (2024)

Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
by: Lykov, Danylo, et al.
Published: (2022)

Optimized Amplitude Amplification for Quantum State Preparation
by: Chernikov, Artem, et al.
Published: (2025)

On the hardness of learning ground state entanglement of geometrically local Hamiltonians
by: Bouland, Adam, et al.
Published: (2024)

Quantum Subgradient Estimation for Conditional Value-at-Risk Optimization
by: Skarlatos, Vasilis, et al.
Published: (2025)

The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding
by: Gu, Shouzhen, et al.
Published: (2026)

Circuit-to-Hamiltonian from tensor networks and fault tolerance
by: Anshu, Anurag, et al.
Published: (2023)

Approximating the quantum value of an LCS game is RE-hard
by: Taller, Aviv, et al.
Published: (2025)

Quantum precomputation: parallelizing cascade circuits and the Moore-Nilsson conjecture is false
by: Watts, Adam Bene, et al.
Published: (2025)

Quantum-Classical Separations in Shallow-Circuit-Based Learning with and without Noises
by: Zhang, Zhihan, et al.
Published: (2024)

Reachability Constraints in Variational Quantum Circuits: Optimization within Polynomial Group Module
by: Oh, Yun-Tak, et al.
Published: (2026)

Topics in Non-local Games: Synchronous Algebras, Algebraic Graph Identities, and Quantum NP-hardness Reductions
by: He, Entong
Published: (2024)

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
by: Rajakumar, Joel, et al.
Published: (2024)

Wasserstein Complexity of Quantum Circuits
by: Li, Lu, et al.
Published: (2022)

Constructing $\mathrm{NP}^{\mathord{\#}\mathrm P}$-complete problems and ${\mathord{\#}\mathrm P}$-hardness of circuit extraction in phase-free ZH
by: Mitosek, Piotr
Published: (2024)

Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity
by: Zhang, Yifan F., et al.
Published: (2025)

The Exact Replica Threshold for Nonlinear Moments of Quantum States
by: Zeng, Shuai
Published: (2026)