Cover Image

NP-hard problems are not in BQP

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Czerwinski, Reiner
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity 03D15, 03D60, 68Q12, 68Q15, 81P68 F.1.3; F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Separation of PSPACE and EXP
by: Czerwinski, Reiner
Published: (2021)

The Polynomial Hierarchy does not collapse
by: Czerwinski, Reiner
Published: (2024)

Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
by: Tzameret, Iddo, et al.
Published: (2023)

Evolomino is NP-complete
by: Nikolaev, Andrei V.
Published: (2025)

The Optimizer Quotient and the Certification Trilemma
by: Simas, Tristan
Published: (2026)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)

Algorithmic Barriers to Detecting and Repairing Structural Overspecification in Adaptive Data-Structure Selection
by: Alpay, Faruk, et al.
Published: (2026)

#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
by: Bannach, Max, et al.
Published: (2025)

Complexities of Well-Quasi-Ordered Substructural Logics
by: Galatos, Nikolaos, et al.
Published: (2025)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
by: Hakoniemi, Tuomas, et al.
Published: (2024)

A correspondence between the time and space complexity
by: Latkin, Ivan V.
Published: (2023)

Shifted Partial Derivative Polynomial Rank and Codimension
by: Edwards, Darren J.
Published: (2025)

Why the classes P and NP are not well-defined finitarily
by: Anand, Bhupinder Singh
Published: (2024)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
by: Huseynzade, Rafig
Published: (2025)

Understanding and Improving Automated Proof Synthesis for Interactive Theorem Provers
by: Zhang, Manqing, et al.
Published: (2026)

A Logspace Constructive Proof of L=SL
by: Buss, Sam, et al.
Published: (2025)

An SoS Entropy Dichotomy via Windowed Hypercontractivity
by: Lela, Marko
Published: (2025)

Truth-Aware Decoding: A Program-Logic Approach to Factual Language Generation
by: Alpay, Faruk, et al.
Published: (2025)

Distributed Exact Quantum Amplitude Amplification Algorithm for Arbitrary Quantum States
by: Zhou, Xu, et al.
Published: (2026)

Exploring P versus NP
by: Tang, Jian-Gang
Published: (2022)

Quantum Advantage in Computational Chemistry?
by: Gundlach, Hans, et al.
Published: (2025)

QSeqSim: A Symbolic Simulator for Qiskit While Loops Using Sequential Quantum Circuits
by: Li, Zihao, et al.
Published: (2026)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
by: Lela, Marko
Published: (2025)

Separation and Collapse of Equilibria Inequalities on AND-OR Trees without Shape Constraints
by: Ito, Fuki, et al.
Published: (2024)

Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2024)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
by: Saffidine, Abdallah, et al.
Published: (2025)

Character Complexity: A Novel Measure for Quantum Circuit Analysis
by: Shami, Daksh
Published: (2024)

NP-hardness of p-adic linear regression
by: Baker, Gregory D.
Published: (2026)

Insignificant Choice Polynomial Time: A Logic Capturing PTIME
by: Schewe, Klaus-Dieter
Published: (2020)

The Solver's Paradox in Formal Problem Spaces
by: Rosko, Milan
Published: (2025)

From Gödel incompleteness to the consistency of circuit lower bounds
by: Atserias, Albert, et al.
Published: (2026)

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

On the Descriptive Complexity of Groups without Abelian Normal Subgroups
by: Grochow, Joshua A., et al.
Published: (2022)

Adversarial Barrier in Uniform Class Separation
by: Rosko, Milan
Published: (2025)

Quantum algorithms through graph composition
by: Cornelissen, Arjan
Published: (2025)

Quantum walks through generalized graph composition
by: Cornelissen, Arjan
Published: (2025)

Locality, Consistency, and the Tractability Frontier
by: Simas, Tristan
Published: (2026)

A Homological Separation of $\mathbf{P}$ from $\mathbf{NP}$ via Computational Topology and Category Theory
by: Tang, Jian-Gang
Published: (2025)

Meta Theorem for Hardness on FCP-Problem
by: Nagao, Atsuki, et al.
Published: (2025)

Upper and Lower Bounds for the Linear Ordering Principle
by: Hirsch, Edward A., et al.
Published: (2025)