Image de couverture de livre

Approximation algorithms for noncommutative CSPs

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Culf, Eric, Mousavi, Hamoon, Spirig, Taro
Format:	Preprint
Publié:	2023
Sujets:	Quantum Physics Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

A Quantum Unique Games Conjecture
par: Mousavi, Hamoon, et autres
Publié: (2024)

Existence and nonexistence of commutativity gadgets for entangled CSPs
par: Culf, Eric, et autres
Publié: (2025)

New Approaches to Complexity via Quantum Graphs
par: Culf, Eric, et autres
Publié: (2023)

Gap-preserving reductions and RE-completeness of independent set games
par: Mančinska, Laura, et autres
Publié: (2025)

Quantum polymorphism characterisation of commutativity gadgets in all quantum models
par: Culf, Eric, et autres
Publié: (2026)

Satisfiability of commutative vs. non-commutative CSPs
par: Bulatov, Andrei A., et autres
Publié: (2024)

The quantum smooth label cover problem is undecidable
par: Culf, Eric, et autres
Publié: (2025)

On Approximability of Satisfiable k-CSPs: V
par: Bhangale, Amey, et autres
Publié: (2024)

On Approximability of Satisfiable k-CSPs: IV
par: Bhangale, Amey, et autres
Publié: (2023)

On Approximability of Satisfiable $k$-CSPs: VI
par: Bhangale, Amey, et autres
Publié: (2024)

On Approximability of Satisfiable $k$-CSPs: VII
par: Bhangale, Amey, et autres
Publié: (2024)

The Communication Complexity of Approximating Matrix Rank
par: Sherstov, Alexander A., et autres
Publié: (2024)

Quantum algorithms for path and cycle containment problems
par: Cornelissen, Arjan, et autres
Publié: (2026)

Quantum Algorithms for Approximate Graph Isomorphism Testing
par: Kulkarni, Prateek P.
Publié: (2026)

On the Approximate Non-Deterministic Degree of Total Boolean Functions
par: Pednekar, Samruddhi, et autres
Publié: (2026)

Quantum algorithms to simulate quadratic classical Hamiltonians and optimal control
par: Krovi, Hari
Publié: (2024)

Approximate Degrees of Multisymmetric Properties with Application to Quantum Claw Detection
par: Tani, Seiichiro
Publié: (2024)

Lower bounds for quantum-inspired classical algorithms via communication complexity
par: Mande, Nikhil S., et autres
Publié: (2024)

Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach
par: Mehraban, Saeed, et autres
Publié: (2023)

Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
par: Lykov, Danylo, et autres
Publié: (2022)

An alternative explicit circuit diagram for the quantum search algorithm by implementing a non-unitary gate
par: Daskin, Ammar
Publié: (2024)

Logarithmic Depth Decomposition of Approximate Multi-Controlled Single-Qubit Gates Without Ancilla Qubits
par: Silva, Jefferson D. S., et autres
Publié: (2025)

A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization
par: Schreiber, Franz J., et autres
Publié: (2025)

Approximating the quantum value of an LCS game is RE-hard
par: Taller, Aviv, et autres
Publié: (2025)

Linear Space Streaming Lower Bounds for Approximating CSPs
par: Chou, Chi-Ning, et autres
Publié: (2021)

Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
par: Arunachalam, Srinivasan, et autres
Publié: (2021)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
par: Singer, Noah G.
Publié: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
par: Singer, Noah G., et autres
Publié: (2026)

Sketching approximability of all finite CSPs
par: Chou, Chi-Ning, et autres
Publié: (2021)

Fast quantum algorithm for differential equations
par: Bagherimehrab, Mohsen, et autres
Publié: (2023)

Clifford testing: algorithms and lower bounds
par: Hinsche, Marcel, et autres
Publié: (2025)

An order out of nowhere: a new algorithm for infinite-domain CSPs
par: Mottet, Antoine, et autres
Publié: (2023)

Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity
par: Zhang, Yifan F., et autres
Publié: (2025)

Towards a complexity-theoretic dichotomy for TQFT invariants
par: Bridges, Nicolas, et autres
Publié: (2025)

Polynomial time classical versus quantum algorithms for representation theoretic multiplicities
par: Panova, Greta
Publié: (2025)

Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians
par: Gall, François Le
Publié: (2024)

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut
par: Huang, Jeremy Ahrens, et autres
Publié: (2024)

A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs
par: Apers, Simon, et autres
Publié: (2021)

Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances
par: Abbas, Amira, et autres
Publié: (2025)

CSPs with Few Alien Constraints
par: Jonsson, Peter, et autres
Publié: (2024)