Buchumschlag

Limitation of Quantum Walk Approach to the Maximum Matching Problem

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Júnior, Alcides Gomes Andrade, Matsubayashi, Akira
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Quantum Physics Computational Complexity F.2.3
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Quantum Time-Space Tradeoffs for Matrix Problems
von: Beame, Paul, et al.
Veröffentlicht: (2024)

Quantum Sabotage Complexity
von: Cornelissen, Arjan, et al.
Veröffentlicht: (2024)

Tight Bounds on the Spooky Pebble Game: Recycling Qubits with Measurements
von: Kornerup, Niels, et al.
Veröffentlicht: (2021)

Direct Sums for Parity Decision Trees
von: Besselman, Tyler, et al.
Veröffentlicht: (2024)

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
von: Antonelli, Melissa, et al.
Veröffentlicht: (2025)

Liquid Amortization: Proving Amortized Complexity with LiquidHaskell (Functional Pearl)
von: van Brügge, Jan
Veröffentlicht: (2024)

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
von: de Rezende, Susanna F., et al.
Veröffentlicht: (2019)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
von: Bodnar, Levente
Veröffentlicht: (2024)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
von: Conneryd, Jonas, et al.
Veröffentlicht: (2025)

On bounded depth proofs for Tseitin formulas on the grid; revisited
von: Håstad, Johan, et al.
Veröffentlicht: (2022)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
von: de Rezende, Susanna F., et al.
Veröffentlicht: (2026)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
von: de Rezende, Susanna F., et al.
Veröffentlicht: (2024)

Supercritical Tradeoffs for Monotone Circuits
von: Göös, Mika, et al.
Veröffentlicht: (2024)

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
von: Rossman, Benjamin
Veröffentlicht: (2024)

Quantum algorithms through graph composition
von: Cornelissen, Arjan
Veröffentlicht: (2025)

Quantum walks through generalized graph composition
von: Cornelissen, Arjan
Veröffentlicht: (2025)

Separation of PSPACE and EXP
von: Czerwinski, Reiner
Veröffentlicht: (2021)

Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences
von: von Liechtenstein, Maximilian R. P.
Veröffentlicht: (2025)

Logics for the Relational Syllogistic
von: Pratt-Hartmann, Ian, et al.
Veröffentlicht: (2008)

Separating QMA from QCMA with a classical oracle
von: Bostanci, John, et al.
Veröffentlicht: (2025)

Adjusted Kolmogorov Complexity of Binary Words with Empirical Entropy Normalization
von: Vidakovic, Brani
Veröffentlicht: (2025)

QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more
von: Chen, Yanlin, et al.
Veröffentlicht: (2023)

Graph-Based Deterministic Polynomial Framwork for NP Problems
von: Lee, Changryeol
Veröffentlicht: (2025)

An efficient algorithm to compute the minimum free energy of interacting nucleic acid strands
von: Shalaby, Ahmed, et al.
Veröffentlicht: (2024)

Arithmetic Complexity of Solutions of the Dirichlet Problem
von: Boche, Holger, et al.
Veröffentlicht: (2026)

Tight bounds on depth-2 QAC-circuits computing parity
von: Fenner, Stephen, et al.
Veröffentlicht: (2025)

Optimal lower bounds for Quantum Learning via Information Theory
von: Hadiashar, Shima Bab, et al.
Veröffentlicht: (2023)

Pauli measurements are not optimal for single-copy tomography
von: Acharya, Jayadev, et al.
Veröffentlicht: (2025)

On the Complexity of Determinations
von: Hellerstein, Joseph M.
Veröffentlicht: (2026)

Multimarked Spatial Search by Continuous-Time Quantum Walk
von: Lugão, Pedro H. G., et al.
Veröffentlicht: (2022)

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
von: Aaronson, Scott, et al.
Veröffentlicht: (2023)

Pseudorandomness of the Sticky Random Walk
von: Anand, Emile, et al.
Veröffentlicht: (2023)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
von: Conneryd, Jonas, et al.
Veröffentlicht: (2025)

Nonuniform Deterministic Finite Automata over finite algebraic structures
von: Idziak, Paweł M., et al.
Veröffentlicht: (2025)

Quantum Advantage in Computational Chemistry?
von: Gundlach, Hans, et al.
Veröffentlicht: (2025)

Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement
von: Hasegawa, Atsuya, et al.
Veröffentlicht: (2025)

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
von: Gupta, Chetan, et al.
Veröffentlicht: (2025)

Algorithmic hardness of the partition function for nucleic acid strands
von: Ducloz, Gwendal, et al.
Veröffentlicht: (2025)

On the Approaching Geodesic Property via the Quotient Invariant
von: Biswas, Kingshook, et al.
Veröffentlicht: (2025)

Complexity Theory for Quantum Promise Problems
von: Chia, Nai-Hui, et al.
Veröffentlicht: (2024)