Cover Image

Random Unitaries in Constant (Quantum) Time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Foxman, Ben, Parham, Natalie, Vasconcelos, Francisca, Yuen, Henry
Format:	Preprint
Published:	2025
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Pauli Spectrum of QAC0
by: Nadimpalli, Shivam, et al.
Published: (2023)

Constant-Depth Unitary Preparation of Dicke States
by: Joshi, Malvika Raj, et al.
Published: (2026)

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

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

Unconditional Quantum Advantage for Sampling with Shallow Circuits
by: Watts, Adam Bene, et al.
Published: (2023)

Unitary Complexity and the Uhlmann Transformation Problem
by: Bostanci, John, et al.
Published: (2023)

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

How to Construct Random Unitaries
by: Ma, Fermi, et al.
Published: (2024)

QMA vs. QCMA and Pseudorandomness
by: Liu, Jiahui, et al.
Published: (2024)

Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
by: Rosenthal, Gregory
Published: (2021)

Unitary synthesis with fewer T gates
by: Tan, Xinyu
Published: (2025)

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

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
by: Rajakumar, Joel, et al.
Published: (2024)

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

Strict Hierarchy for Quantum Channel Certification to Unitary
by: Chen, Kean, et al.
Published: (2026)

Quantum Event Learning and Gentle Random Measurements
by: Watts, Adam Bene, et al.
Published: (2022)

Oracle Separations for the Quantum-Classical Polynomial Hierarchy
by: Agarwal, Avantika, et al.
Published: (2024)

An efficient quantum parallel repetition theorem and applications
by: Bostanci, John, et al.
Published: (2023)

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

The Space-Time Cost of Purifying Quantum Computations
by: Zhandry, Mark
Published: (2024)

Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses
by: Wu, Mingyou
Published: (2024)

Multimarked Spatial Search by Continuous-Time Quantum Walk
by: Lugão, Pedro H. G., et al.
Published: (2022)

Unitary designs in nearly optimal depth
by: Cui, Laura, et al.
Published: (2025)

Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
by: Chia, Nai-Hui, et al.
Published: (2024)

Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates
by: Nelson, Jon, et al.
Published: (2024)

Two bases suffice for QMA1-completeness
by: Ma, Henry, et al.
Published: (2025)

A Schematic Definition of Quantum Polynomial Time Computability
by: Yamakami, Tomoyuki
Published: (2018)

Quantum Advantages in (n,d)->1 Random Access Codes
by: Ambainis, Andris, et al.
Published: (2015)

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

Oracle separation of QMA and QCMA with bounded adaptivity
by: Ben-David, Shalev, 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)

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

Monte Carlo to Las Vegas for Recursively Composed Functions
by: Al-Dhalaan, Bandar, et al.
Published: (2026)

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

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

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

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

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

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)