Cover Image

Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Mehraban, Saeed, Tahmasbi, Mehrdad
Format:	Preprint
Published:	2023
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Improved bounds for testing low stabilizer complexity states
by: Mehraban, Saeed, et al.
Published: (2024)

The Space Just Above One Clean Qubit
by: Jacobs, Dale, et al.
Published: (2024)

Quantum state isomorphism problems for groups
by: Gheorghiu, Alexandru, et al.
Published: (2026)

Bosonic Quantum Computational Complexity
by: Chabaud, Ulysse, et al.
Published: (2024)

The Communication Complexity of Approximating Matrix Rank
by: Sherstov, Alexander A., et al.
Published: (2024)

New Lower-bounds for Quantum Computation with Non-Collapsing Measurements
by: Miloschewsky, David, et al.
Published: (2024)

Lower bounds for quantum-inspired classical algorithms via communication complexity
by: Mande, Nikhil S., et al.
Published: (2024)

Improved Lower Bounds for QAC0
by: Joshi, Malvika Raj, et al.
Published: (2025)

Improved Circuit Lower Bounds and Quantum-Classical Separations
by: Grewal, Sabee, et al.
Published: (2024)

Lower Bounds for Unitary Property Testing with Proofs and Advice
by: Weggemans, Jordi
Published: (2024)

Approximation algorithms for noncommutative CSPs
by: Culf, Eric, et al.
Published: (2023)

Complexity of Quadratic Bosonic Hamiltonian Simulation: $\mathsf{BQP}$-Completeness and $\mathsf{PostBQP}$-Hardness
by: Zschetzsche, Lilith, et al.
Published: (2026)

Quantum Query-Space Lower Bounds Using Branching Programs
by: Bera, Debajyoti, et al.
Published: (2024)

Lower Bounds on Relative Error Quantum Compression and Classical Shadows
by: Sankar, Kaushik
Published: (2025)

Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
by: Wang, Qisheng, et al.
Published: (2024)

Space-bounded quantum interactive proof systems
by: Gall, François Le, et al.
Published: (2024)

Quantum circuit lower bounds in the magic hierarchy
by: Parham, Natalie
Published: (2025)

Oracle separation of QMA and QCMA with bounded adaptivity
by: Ben-David, Shalev, et al.
Published: (2024)

Quantum Algorithms for Approximate Graph Isomorphism Testing
by: Kulkarni, Prateek P.
Published: (2026)

A note on quantum lower bounds for local search via congestion and expansion
by: Brânzei, Simina, et al.
Published: (2024)

On the Approximate Non-Deterministic Degree of Total Boolean Functions
by: Pednekar, Samruddhi, et al.
Published: (2026)

Lower Bounds for Approximate Sign Rank
by: Bindua, Riju, et al.
Published: (2026)

Approximate Degrees of Multisymmetric Properties with Application to Quantum Claw Detection
by: Tani, Seiichiro
Published: (2024)

Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
by: Agarwal, Avantika, et al.
Published: (2024)

Beating the natural Grover bound for low-energy estimation and state preparation
by: Buhrman, Harry, et al.
Published: (2024)

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

Space-bounded quantum state testing via space-efficient quantum singular value transformation
by: Gall, François Le, et al.
Published: (2023)

Logarithmic Depth Decomposition of Approximate Multi-Controlled Single-Qubit Gates Without Ancilla Qubits
by: Silva, Jefferson D. S., et al.
Published: (2025)

Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth
by: Hsieh, Min-Hsiu, et al.
Published: (2024)

Approximating the quantum value of an LCS game is RE-hard
by: Taller, Aviv, et al.
Published: (2025)

Quantum Advantage in Decision Trees: A Weighted Graph and $L_1$ Norm Approach
by: Grillo, Sebastian Alberto, et al.
Published: (2026)

Algorithmic Randomness and Probabilistic Laws
by: Barrett, Jeffrey A., et al.
Published: (2023)

Information-Theoretic Lower Bounds for Approximating Monomials via Optimal Quantum Tsallis Entropy Estimation
by: Wang, Qisheng
Published: (2025)

A slightly improved upper bound for quantum statistical zero-knowledge
by: Gall, François Le, et al.
Published: (2025)

Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis
by: Bu, Kaifeng, et al.
Published: (2023)

Learning quantum states and unitaries of bounded gate complexity
by: Zhao, Haimeng, et al.
Published: (2023)

Computational hardness of estimating quantum entropies via binary entropy bounds
by: Liu, Yupan
Published: (2026)

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
by: Grewal, Sabee, et al.
Published: (2022)

Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity
by: Zhang, Yifan F., et al.
Published: (2025)

Clifford testing: algorithms and lower bounds
by: Hinsche, Marcel, et al.
Published: (2025)