Copertina

Quantum Max-Cut is NP hard to approximate

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Piddock, Stephen
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Quantum Physics Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

BQP, meet NP: Search-to-decision reductions and approximate counting
di: Gharibian, Sevag, et al.
Pubblicazione: (2024)

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

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

The classical limit of Quantum Max-Cut
di: Bulchandani, Vir B., et al.
Pubblicazione: (2024)

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut
di: Huang, Jeremy Ahrens, et al.
Pubblicazione: (2024)

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

The 7 faces of quantum NP
di: Gharibian, Sevag
Pubblicazione: (2023)

Exact Quantum Circuit Optimization is co-NQP-hard
di: Kjelstrøm, Adam Husted, et al.
Pubblicazione: (2025)

Quantum Feasibility Labeling for NP-complete Vertex Coloring Problem
di: Zhan, Junpeng
Pubblicazione: (2023)

From Worst-Case Hardness of $\mathsf{NP}$ to Quantum Cryptography via Quantum Indistinguishability Obfuscation
di: Morimae, Tomoyuki, et al.
Pubblicazione: (2025)

Complexity and hardness of random peaked circuits
di: Zhang, Yuxuan
Pubblicazione: (2025)

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

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

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

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

SAT, Gadgets, Max2XOR, and Quantum Annealers
di: Ansótegui, Carlos, et al.
Pubblicazione: (2024)

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

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

Efficient Quantum Hermite Transform
di: Jain, Siddhartha, et al.
Pubblicazione: (2025)

Hardness of approximation for ground state problems
di: Gharibian, Sevag, et al.
Pubblicazione: (2024)

Low-degree approximation of QAC$^0$ circuits
di: Montanaro, Ashley, et al.
Pubblicazione: (2024)

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

On the complexity of unique quantum witnesses and quantum approximate counting
di: Anshu, Anurag, et al.
Pubblicazione: (2024)

Communication Complexity is NP-hard
di: Hirahara, Shuichi, et al.
Pubblicazione: (2025)

Efficient approximate unitary designs from random Pauli rotations
di: Haah, Jeongwan, et al.
Pubblicazione: (2024)

Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions
di: Yamakami, Tomoyuki
Pubblicazione: (2023)

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
di: Gharibian, Sevag, et al.
Pubblicazione: (2021)

New Quantum Algorithms for Computing Quantum Entropies and Distances
di: Wang, Qisheng, et al.
Pubblicazione: (2022)

Computational hardness of estimating quantum entropies via binary entropy bounds
di: Liu, Yupan
Pubblicazione: (2026)

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

Basic Quantum Algorithms
di: Portugal, Renato
Pubblicazione: (2022)

Quantum Threshold is Powerful
di: Grier, Daniel, et al.
Pubblicazione: (2024)

Uncloneable Quantum Advice
di: Broadbent, Anne, et al.
Pubblicazione: (2023)

Quantum Search With Generalized Wildcards
di: Cornelissen, Arjan, et al.
Pubblicazione: (2025)

On the Complexity of Decoded Quantum Interferometry
di: Marwaha, Kunal, et al.
Pubblicazione: (2025)

Efficient Algorithms for Quantum Hashing
di: Zinnatullin, Ilnar, et al.
Pubblicazione: (2025)

Formal Framework for Quantum Advantage
di: Buhrman, Harry, et al.
Pubblicazione: (2025)

Quantum Interactive Oracle Proofs
di: Sun, Baocheng, et al.
Pubblicazione: (2026)

An Efficient Quantum Factoring Algorithm
di: Regev, Oded
Pubblicazione: (2023)

The Power of Lorentz Quantum Computer
di: Zhang, Qi, et al.
Pubblicazione: (2024)