Cover Image

Complexity and hardness of random peaked circuits

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Zhang, Yuxuan
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

Optimising quantum circuits is generally hard
by: van de Wetering, John, et al.
Published: (2023)

Incompressibility and spectral gaps of random circuits
by: Chen, Chi-Fang, et al.
Published: (2024)

Fault-tolerant compiling of classically hard IQP circuits on hypercubes
by: Hangleiter, Dominik, et al.
Published: (2024)

Constructing $\mathrm{NP}^{\mathord{\#}\mathrm P}$-complete problems and ${\mathord{\#}\mathrm P}$-hardness of circuit extraction in phase-free ZH
by: Mitosek, Piotr
Published: (2024)

Complexity of quantum circuits via sensitivity, magic, and coherence
by: Bu, Kaifeng, et al.
Published: (2022)

Exact spectral gaps of random one-dimensional quantum circuits
by: Deneris, Andrew E., et al.
Published: (2024)

Classical Simulability of Quantum Circuits with Shallow Magic Depth
by: Zhang, Yifan, et al.
Published: (2024)

On the hardness of cloning and connections to representation theory
by: Havlíček, Vojtěch, et al.
Published: (2024)

The power of quantum circuits in sampling
by: Blanc, Guy, et al.
Published: (2025)

IQP circuits for 2-Forrelation
by: Buzet, Quentin, et al.
Published: (2026)

Quantum advantage from measurement-induced entanglement in random shallow circuits
by: Watts, Adam Bene, et al.
Published: (2024)

Quantum Max-Cut is NP hard to approximate
by: Piddock, Stephen
Published: (2025)

How hard is it to verify a classical shadow?
by: Karaiskos, Georgios, et al.
Published: (2025)

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

Fast simulation of planar Clifford circuits
by: Gosset, David, et al.
Published: (2020)

On estimating the entropy of shallow circuit outputs
by: Gheorghiu, Alexandru, et al.
Published: (2020)

Exact Quantum Circuit Optimization is co-NQP-hard
by: Kjelstrøm, Adam Husted, et al.
Published: (2025)

Exponential improvements to the average-case hardness of BosonSampling
by: Bouland, Adam, et al.
Published: (2024)

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

Low-degree approximation of QAC$^0$ circuits
by: Montanaro, Ashley, et al.
Published: (2024)

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

Bell sampling from quantum circuits
by: Hangleiter, Dominik, et al.
Published: (2023)

Quantum precomputation: parallelizing cascade circuits and the Moore-Nilsson conjecture is false
by: Watts, Adam Bene, et al.
Published: (2025)

Classical simulability of quantum circuits followed by sparse classical post-processing
by: Takahashi, Yasuhiro, et al.
Published: (2026)

Learning junta distributions, quantum junta states, and QAC$^0$ circuits
by: Bao, Jinge, et al.
Published: (2024)

The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding
by: Gu, Shouzhen, et al.
Published: (2026)

Gate-based quantum simulation of Gaussian bosonic circuits on exponentially many modes
by: Barthe, Alice, et al.
Published: (2024)

When quantum resources backfire: Non-gaussianity and symplectic coherence in noisy bosonic circuits
by: Upreti, Varun, et al.
Published: (2025)

Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expanders
by: Iyer, Vishnu, et al.
Published: (2026)

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

Classically estimating observables of noiseless quantum circuits
by: Angrisani, Armando, et al.
Published: (2024)

An alternative explicit circuit diagram for the quantum search algorithm by implementing a non-unitary gate
by: Daskin, Ammar
Published: (2024)

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

Quantum Complexity vs Classical Complexity: A Survey
by: Vaezi, Arash, et al.
Published: (2023)

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

The Complexity of Stoquastic Sparse Hamiltonians
by: Grilo, Alex B., et al.
Published: (2026)

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

Efficient approximate unitary designs from random Pauli rotations
by: Haah, Jeongwan, et al.
Published: (2024)

Verifiable measurement-based quantum random sampling with trapped ions
by: Ringbauer, Martin, et al.
Published: (2023)

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