Cover Image

Approximate Degrees of Multisymmetric Properties with Application to Quantum Claw Detection

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Tani, Seiichiro
Format:	Preprint
Published:	2024
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams
by: Tani, Seiichiro
Published: (2019)

Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
by: Hiromasa, Ryo, et al.
Published: (2022)

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

On the Rational Degree of Boolean Functions and Applications
by: Iyer, Vishnu, et al.
Published: (2023)

Quantum Property Testing for Bounded-Degree Directed Graphs
by: Peng, Pan, et al.
Published: (2026)

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

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

Coherence in Property Testing: Quantum-Classical Collapses and Separations
by: Jeronimo, Fernando Granha, et al.
Published: (2024)

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

Local Test for Unitarily Invariant Properties of Bipartite Quantum States
by: Chen, Kean, et al.
Published: (2024)

Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits
by: Fefferman, Bill, et al.
Published: (2024)

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

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

Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach
by: Mehraban, Saeed, 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)

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

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

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

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

Quantum Threshold is Powerful
by: Grier, Daniel, et al.
Published: (2024)

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

Uncloneable Quantum Advice
by: Broadbent, Anne, et al.
Published: (2023)

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

The Power of Lorentz Quantum Computer
by: Zhang, Qi, et al.
Published: (2024)

Quantum Communication Advantage in TFNP
by: Göös, Mika, et al.
Published: (2024)

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

Quantum Search With Generalized Wildcards
by: Cornelissen, Arjan, et al.
Published: (2025)

Quantum Interactive Oracle Proofs
by: Sun, Baocheng, et al.
Published: (2026)

An Efficient Quantum Factoring Algorithm
by: Regev, Oded
Published: (2023)

Efficient Quantum Hermite Transform
by: Jain, Siddhartha, et al.
Published: (2025)

On the Complexity of Decoded Quantum Interferometry
by: Marwaha, Kunal, et al.
Published: (2025)

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

Pseudo-deterministic Quantum Algorithms
by: Aaronson, Hugo, et al.
Published: (2026)

Efficient Algorithms for Quantum Hashing
by: Zinnatullin, Ilnar, et al.
Published: (2025)

Formal Framework for Quantum Advantage
by: Buhrman, Harry, et al.
Published: (2025)

Dimension Independent Disentanglers from Unentanglement and Applications
by: Jeronimo, Fernando G., et al.
Published: (2024)

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut
by: Huang, Jeremy Ahrens, et al.
Published: (2024)

A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting
by: Chen, Kean, et al.
Published: (2025)

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

A Quantum Unique Games Conjecture
by: Mousavi, Hamoon, et al.
Published: (2024)