Buchumschlag

Magic and communication complexity

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Girish, Uma, May, Alex, Parham, Natalie, Yuen, Henry
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Quantum Physics Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Random Unitaries in Constant (Quantum) Time
von: Foxman, Ben, et al.
Veröffentlicht: (2025)

On the Pauli Spectrum of QAC0
von: Nadimpalli, Shivam, et al.
Veröffentlicht: (2023)

Fourier Spectrum of Noisy Quantum Algorithms
von: Girish, Uma
Veröffentlicht: (2025)

Quantum circuit lower bounds in the magic hierarchy
von: Parham, Natalie
Veröffentlicht: (2025)

Forrelation is Extremally Hard
von: Girish, Uma, et al.
Veröffentlicht: (2025)

Trade-offs between Entanglement and Communication
von: Arunachalam, Srinivasan, et al.
Veröffentlicht: (2023)

Unconditional Quantum Advantage for Sampling with Shallow Circuits
von: Watts, Adam Bene, et al.
Veröffentlicht: (2023)

QMA vs. QCMA and Pseudorandomness
von: Liu, Jiahui, et al.
Veröffentlicht: (2024)

On the communication complexity of finding a king in a tournament
von: Mande, Nikhil S., et al.
Veröffentlicht: (2024)

Lower bounds for quantum-inspired classical algorithms via communication complexity
von: Mande, Nikhil S., et al.
Veröffentlicht: (2024)

Classical Simulability of Quantum Circuits with Shallow Magic Depth
von: Zhang, Yifan, et al.
Veröffentlicht: (2024)

An efficient quantum parallel repetition theorem and applications
von: Bostanci, John, et al.
Veröffentlicht: (2023)

Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis
von: Bu, Kaifeng, et al.
Veröffentlicht: (2023)

Distributed inner product estimation with limited quantum communication
von: Arunachalam, Srinivasan, et al.
Veröffentlicht: (2024)

Unitary Complexity and the Uhlmann Transformation Problem
von: Bostanci, John, et al.
Veröffentlicht: (2023)

Quantum computational complexity of matrix functions
von: Cifuentes, Santiago, et al.
Veröffentlicht: (2024)

Physical complexity and black hole quantum computers
von: Reilly, Michele, et al.
Veröffentlicht: (2025)

Computational complexity of isometric tensor network states
von: Malz, Daniel, et al.
Veröffentlicht: (2024)

On query complexity measures and their relations for symmetric functions
von: Mittal, Rajat, et al.
Veröffentlicht: (2021)

Direct sum theorems beyond query complexity
von: Suruga, Daiki
Veröffentlicht: (2024)

Quantum and classical query complexities of functions of matrices
von: Montanaro, Ashley, et al.
Veröffentlicht: (2023)

Separations in query complexity for total search problems
von: Ben-David, Shalev, et al.
Veröffentlicht: (2024)

Two bases suffice for QMA1-completeness
von: Ma, Henry, et al.
Veröffentlicht: (2025)

On the complexity of estimating ground state entanglement and free energy
von: Gharibian, Sevag, et al.
Veröffentlicht: (2025)

On the complexity of unique quantum witnesses and quantum approximate counting
von: Anshu, Anurag, et al.
Veröffentlicht: (2024)

On classical advice, sampling advice and complexity assumptions for learning separations
von: Pérez-Guijarro, Jordi
Veröffentlicht: (2024)

Fermionic Independent Set and Laplacian of an independence complex are QMA-hard
von: Rayudu, Chaithanya
Veröffentlicht: (2024)

Hardness results for decoding the surface code with Pauli noise
von: Fischer, Alex, et al.
Veröffentlicht: (2023)

The Complexity of Stoquastic Sparse Hamiltonians
von: Grilo, Alex B., et al.
Veröffentlicht: (2026)

On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality
von: Sakamoto, Kazuki, et al.
Veröffentlicht: (2025)

Another generalization of Hadamard test: Optimal sample complexities for learning functions on the unitary group
von: Suruga, Daiki
Veröffentlicht: (2025)

Quantum complexity of the Kronecker coefficients
von: Bravyi, Sergey, et al.
Veröffentlicht: (2023)

On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$
von: Yao, Penghui, et al.
Veröffentlicht: (2023)

Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes
von: Cardoso, Ricardo Rivera, et al.
Veröffentlicht: (2025)

StoqMA vs. MA: the power of error reduction
von: Aharonov, Dorit, et al.
Veröffentlicht: (2020)

Fast simulation of planar Clifford circuits
von: Gosset, David, et al.
Veröffentlicht: (2020)

The Power of Shallow-depth Toffoli and Qudit Quantum Circuits
von: Grilo, Alex Bredariol, et al.
Veröffentlicht: (2024)

Random regular graph states are complex at almost any depth
von: Ghosh, Soumik, et al.
Veröffentlicht: (2024)

Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
von: Lemus, Mariano, et al.
Veröffentlicht: (2023)

A complexity phase transition at the EPR Hamiltonian
von: Marwaha, Kunal, et al.
Veröffentlicht: (2026)