Cover Image

Quantum computational complexity of matrix functions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cifuentes, Santiago, Wang, Samson, Silva, Thais L., Berta, Mario, Aolita, Leandro
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 and classical query complexities of functions of matrices
by: Montanaro, Ashley, et al.
Published: (2023)

Physical complexity and black hole quantum computers
by: Reilly, Michele, et al.
Published: (2025)

Quantum computation with indefinite causal structures
by: Araújo, Mateus, et al.
Published: (2017)

On query complexity measures and their relations for symmetric functions
by: Mittal, Rajat, et al.
Published: (2021)

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

Symmetric quantum computation
by: Castro-Silva, Davi, et al.
Published: (2025)

Improved separation between quantum and classical computers for sampling and functional tasks
by: Marshall, Simon C., et al.
Published: (2024)

Quantum complexity of the Kronecker coefficients
by: Bravyi, Sergey, et al.
Published: (2023)

Another generalization of Hadamard test: Optimal sample complexities for learning functions on the unitary group
by: Suruga, Daiki
Published: (2025)

Quantum computing and persistence in topological data analysis
by: Gyurik, Casper, et al.
Published: (2024)

Magic and communication complexity
by: Girish, Uma, et al.
Published: (2025)

Bounding the computational power of bosonic systems
by: Upreti, Varun, et al.
Published: (2025)

Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
by: Lemus, Mariano, et al.
Published: (2023)

A simple lower bound for the complexity of estimating partition functions on a quantum computer
by: Chen, Zherui, et al.
Published: (2024)

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

A full dichotomy for Holant$^c$, inspired by quantum computation
by: Backens, Miriam
Published: (2022)

Computational complexity of isometric tensor network states
by: Malz, Daniel, et al.
Published: (2024)

Direct sum theorems beyond query complexity
by: Suruga, Daiki
Published: (2024)

Separations in query complexity for total search problems
by: Ben-David, Shalev, et al.
Published: (2024)

Whether a quantum computation employs nonlocal resources is operationally undecidable
by: Fields, Chris, et al.
Published: (2025)

On the complexity of unique quantum witnesses and quantum approximate counting
by: Anshu, Anurag, et al.
Published: (2024)

On the communication complexity of finding a king in a tournament
by: Mande, Nikhil S., et al.
Published: (2024)

On the complexity of estimating ground state entanglement and free energy
by: Gharibian, Sevag, et al.
Published: (2025)

On classical advice, sampling advice and complexity assumptions for learning separations
by: Pérez-Guijarro, Jordi
Published: (2024)

Fermionic Independent Set and Laplacian of an independence complex are QMA-hard
by: Rayudu, Chaithanya
Published: (2024)

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

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

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

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

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

Randomized semi-quantum matrix processing
by: Tosta, Allan, et al.
Published: (2023)

DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians
by: Ji, Zhengfeng, et al.
Published: (2026)

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

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

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)

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

DQC1-hardness of estimating correlation functions
by: Moulik, Subhayan Roy, et al.
Published: (2024)

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