Buchumschlag

On the Need for (Quantum) Memory with Short Outputs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Hao, Zihan, Huang, Zikuan, Liu, Qipeng
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Improved Quantum Lifting by Coherent Measure-and-Reprogram
von: Cojocaru, Alexandru, et al.
Veröffentlicht: (2025)

Classical vs Quantum Advice and Proofs under Classically-Accessible Oracle
von: Li, Xingjian, et al.
Veröffentlicht: (2023)

Quantum Lifting for Invertible Permutations and Ideal Ciphers
von: Cojocaru, Alexandru, et al.
Veröffentlicht: (2025)

On the Need for Large Quantum Depth
von: Chia, Nai-Hui, et al.
Veröffentlicht: (2019)

NISQ Security and Complexity via Simple Classical Reasoning
von: Cojocaru, Alexandru, et al.
Veröffentlicht: (2025)

Short and useful quantum proofs for sublogarithmic-space verifiers
von: Say, A. C. Cem
Veröffentlicht: (2025)

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

The NISQ Complexity of Collision Finding
von: Hamoudi, Yassine, et al.
Veröffentlicht: (2022)

Dequantizing Short-Path Quantum Algorithms
von: Gall, François Le, et al.
Veröffentlicht: (2026)

Size Minimization For Multi-Output AND-Functions
von: Armbruster, Susanne
Veröffentlicht: (2024)

Query Lower Bounds for Correlation Clustering under Memory Constraints
von: Garg, Sumegha, et al.
Veröffentlicht: (2026)

On the Number of Quantifiers Needed to Define Boolean Functions
von: Carmosino, Marco, et al.
Veröffentlicht: (2024)

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

Low-Sensitivity Matching via Sampling from Gibbs Distributions
von: Yoshida, Yuichi, et al.
Veröffentlicht: (2025)

The Quantumly Fast and the Classically Forrious
von: Canonne, Clément L., et al.
Veröffentlicht: (2026)

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

Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds
von: Li, Jiawei, et al.
Veröffentlicht: (2024)

Separating Quantum and Classical Advice with Good Codes
von: Bostanci, John, et al.
Veröffentlicht: (2026)

New Quantum Algorithms for Computing Quantum Entropies and Distances
von: Wang, Qisheng, et al.
Veröffentlicht: (2022)

Quantum state testing with restricted measurements
von: Liu, Yuhan, et al.
Veröffentlicht: (2024)

Quantum and Classical Communication Complexity of Permutation-Invariant Functions
von: Guan, Ziyi, et al.
Veröffentlicht: (2023)

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

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

Does Subset Sum Admit Short Proofs?
von: Włodarczyk, Michał
Veröffentlicht: (2024)

Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups
von: Cai, Jin-Yi, et al.
Veröffentlicht: (2026)

A Note on Output Length of One-Way State Generators and EFIs
von: Hhan, Minki, et al.
Veröffentlicht: (2023)

Worst-Case and Average-Case Hardness of Hypercycle and Database Problems
von: Fu, Cheng-Hao, et al.
Veröffentlicht: (2025)

Dual‐Sliding‐Mode‐Observer‐Based IPMSM Sensorless Control Technique
von: Sang Xu, et al.
Veröffentlicht: (2024)

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

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

Quantum Merlin-Arthur proof systems for synthesizing quantum states
von: Delavenne, Hugo, et al.
Veröffentlicht: (2023)

The Greedy Coin Change Problem
von: Gupta, Shreya, et al.
Veröffentlicht: (2024)

Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions
von: Yamakami, Tomoyuki
Veröffentlicht: (2023)

Approximately counting maximal independent set is equivalent to #SAT
von: Zhang, Hao, et al.
Veröffentlicht: (2024)

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
von: Gharibian, Sevag, et al.
Veröffentlicht: (2021)

Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
von: Lykov, Danylo, et al.
Veröffentlicht: (2022)

Nearly-Linear Time Seeded Extractors with Short Seeds
von: Doron, Dean, et al.
Veröffentlicht: (2024)

The Computational Complexity of Factored Graphs
von: Gupta, Shreya, et al.
Veröffentlicht: (2024)

Basic Quantum Algorithms
von: Portugal, Renato
Veröffentlicht: (2022)

Quantum Threshold is Powerful
von: Grier, Daniel, et al.
Veröffentlicht: (2024)