:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Hao, Zihan, Huang, Zikuan, Liu, Qipeng
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2602.23763
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Improved Quantum Lifting by Coherent Measure-and-Reprogram
by: Cojocaru, Alexandru, et al.
Published: (2025)

Classical vs Quantum Advice and Proofs under Classically-Accessible Oracle
by: Li, Xingjian, et al.
Published: (2023)

Quantum Lifting for Invertible Permutations and Ideal Ciphers
by: Cojocaru, Alexandru, et al.
Published: (2025)

On the Need for Large Quantum Depth
by: Chia, Nai-Hui, et al.
Published: (2019)

NISQ Security and Complexity via Simple Classical Reasoning
by: Cojocaru, Alexandru, et al.
Published: (2025)

The NISQ Complexity of Collision Finding
by: Hamoudi, Yassine, et al.
Published: (2022)

Dequantizing Short-Path Quantum Algorithms
by: Gall, François Le, et al.
Published: (2026)

Short and useful quantum proofs for sublogarithmic-space verifiers
by: Say, A. C. Cem
Published: (2025)

Size Minimization For Multi-Output AND-Functions
by: Armbruster, Susanne
Published: (2024)

MP-Aggregation MP(R,2-WO) is Polynomial-Time Solvable When the Output Should Be Dichotomous Weak Preference Order
by: Chen, Jiehua
Published: (2025)

Low-Sensitivity Matching via Sampling from Gibbs Distributions
by: Yoshida, Yuichi, et al.
Published: (2025)

Query Lower Bounds for Correlation Clustering under Memory Constraints
by: Garg, Sumegha, et al.
Published: (2026)

On the Number of Quantifiers Needed to Define Boolean Functions
by: Carmosino, Marco, et al.
Published: (2024)

Raising the Bar: An Asymptotic Comparison of Classical and Quantum Shortest Path Algorithms
by: Do, Phuc Hao, et al.
Published: (2025)

Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds
by: Li, Jiawei, et al.
Published: (2024)

Separating Quantum and Classical Advice with Good Codes
by: Bostanci, John, et al.
Published: (2026)

A nearly-$4\log n$ depth lower bound for formulas with restriction on top
by: Wu, Hao
Published: (2024)

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

Does Subset Sum Admit Short Proofs?
by: Włodarczyk, Michał
Published: (2024)

The Quantumly Fast and the Classically Forrious
by: Canonne, Clément L., et al.
Published: (2026)

A Note on Output Length of One-Way State Generators and EFIs
by: Hhan, Minki, et al.
Published: (2023)

Quantum and Classical Communication Complexity of Permutation-Invariant Functions
by: Guan, Ziyi, et al.
Published: (2023)

Quantum state testing with restricted measurements
by: Liu, Yuhan, et al.
Published: (2024)

Complexity Theory for Quantum Promise Problems
by: Chia, Nai-Hui, et al.
Published: (2024)

Dual‐Sliding‐Mode‐Observer‐Based IPMSM Sensorless Control Technique
by: Sang Xu, et al.
Published: (2024)

Making Quickhull More Like Quicksort: A Simple Randomized Output-Sensitive Convex Hull Algorithm
by: Goodrich, Michael T., et al.
Published: (2024)

Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD
by: Deligkas, Argyrios, et al.
Published: (2026)

A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity
by: Dvořák, Pavel, et al.
Published: (2024)

Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups
by: Cai, Jin-Yi, et al.
Published: (2026)

Worst-Case and Average-Case Hardness of Hypercycle and Database Problems
by: Fu, Cheng-Hao, et al.
Published: (2025)

Nearly-Linear Time Seeded Extractors with Short Seeds
by: Doron, Dean, et al.
Published: (2024)

Quantum Merlin-Arthur proof systems for synthesizing quantum states
by: Delavenne, Hugo, et al.
Published: (2023)

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

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

Approximately counting maximal independent set is equivalent to #SAT
by: Zhang, Hao, et al.
Published: (2024)

Complexity of Round-Robin Allocation with Potentially Noisy Queries
by: Li, Zihan, et al.
Published: (2024)

The Greedy Coin Change Problem
by: Gupta, Shreya, et al.
Published: (2024)

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

Frontier Space-Time Algorithms Using Only Full Memory
by: Chmel, Petr, et al.
Published: (2026)

Basic Quantum Algorithms
by: Portugal, Renato
Published: (2022)