Cover Image

Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ilmavirta, Joonas, Lassas, Matti, Lu, Jinpeng, Oksanen, Lauri, Ylinen, Lauri
Format:	Preprint
Published:	2023
Subjects:	Combinatorics Computational Complexity Quantum Physics 52C25 (Primary) 68Q12, 68Q17 (Secondary)
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Flexible realizations existence: NP-completeness on sparse graphs and algorithms
by: Laštovička, Petr, et al.
Published: (2024)

P not equal to NP
by: Delgado, Daniel Cardona
Published: (2023)

The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs
by: Ahn, Jungho, et al.
Published: (2022)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
by: Bergougnoux, Benjamin, et al.
Published: (2025)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
by: Abdullah, Duaa, et al.
Published: (2025)

The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)

The n-vehicle exploration problem is NP-complete
by: Cui, Jinchuan, et al.
Published: (2023)

Complexity of learning matchings and half graphs via edge queries
by: Mande, Nikhil S., et al.
Published: (2025)

Friends-and-strangers is PSPACE-complete
by: Yang, Chao, et al.
Published: (2024)

Undecidability of Translational Tiling with 2 Polycubes
by: Kim, Yoonhu
Published: (2025)

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
by: Marković, Petar, et al.
Published: (2026)

Undefinability of Approximation of 2-to-2 Games
by: Dawar, Anuj, et al.
Published: (2025)

Paintbucket on graphs is PSPACE-complete
by: Saunders, Ethan J., et al.
Published: (2024)

Quantum Lower Bounds by Sample-to-Query Lifting
by: Wang, Qisheng, et al.
Published: (2023)

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

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
by: Edwards, Darren J.
Published: (2025)

Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)

$k$-edge geodetic graphs
by: Guragain, Satyam, et al.
Published: (2024)

On weighted graph separation problems and flow-augmentation
by: Kim, Eun Jung, et al.
Published: (2022)

How Hard is it to be a Star? Convex Geometry and the Real Hierarchy
by: Schaefer, Marcus, et al.
Published: (2025)

Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses
by: Ye, Yuhan
Published: (2026)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
by: Shalunov, Yakov
Published: (2023)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
by: Ye, Lixi
Published: (2026)

Looking for all solutions of the Max Atom Problem (MAP)
by: Truffet, Laurent
Published: (2024)

A polynomial Time Algorithm to Solve The Max-atom Problem
by: Lahlou, Chams, et al.
Published: (2021)

Unifying lower bounds for algebraic machines, semantically
by: Seiller, Thomas, et al.
Published: (2018)

Deterministic Quantum Search via Recursive Oracle Expansion
by: Burke, John, et al.
Published: (2025)

Closed-Form Decomposition for Simplicial Cones and PDBarv Algorithm for Lattice Point Counting
by: Tao, Sihao, et al.
Published: (2025)

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

NP-hard problems are not in BQP
by: Czerwinski, Reiner
Published: (2023)

Teaching and Learning under Deductive Errors
by: Telle, Jan Arne, et al.
Published: (2026)

Tight complexity bounds for diagram commutativity verification
by: Malko, Artem, et al.
Published: (2025)

Reduction of the group isomorphism problem to the group automorphism problem
by: Skresanov, Saveliy V.
Published: (2025)

The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms
by: Kátay, Tamás, et al.
Published: (2023)

Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
by: Meir, Or
Published: (2023)

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
by: Larrauri, Alberto
Published: (2025)

Integer multiplication is at least as hard as matrix transposition
by: Harvey, David, et al.
Published: (2025)

Approximating mixed volumes to arbitrary accuracy
by: Narayanan, Hariharan, et al.
Published: (2025)