Cover Image

Random regular graph states are complex at almost any depth

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ghosh, Soumik, Hangleiter, Dominik, Helsen, Jonas
Format:	Preprint
Published:	2024
Subjects:	Quantum Physics Computational Complexity Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Peaked quantum advantage using error correction
by: Deshpande, Abhinav, et al.
Published: (2025)

Has quantum advantage been achieved?
by: Hangleiter, Dominik
Published: (2026)

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

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

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

Learning stabilizer structure of quantum states
by: Arunachalam, Srinivasan, et al.
Published: (2025)

Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians
by: Buhrman, Harry, et al.
Published: (2024)

Single-copy stabilizer testing
by: Hinsche, Marcel, et al.
Published: (2024)

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

Unconditional Pseudorandomness against Shallow Quantum Circuits
by: Ghosh, Soumik, et al.
Published: (2025)

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

Quantum search by continuous-time quantum walk on t-designs
by: Lugão, Pedro H. G., et al.
Published: (2023)

The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits
by: Mondada, Luca, et al.
Published: (2023)

A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem
by: Li, Zhengyu, et al.
Published: (2023)

Positive bias makes tensor-network contraction tractable
by: Jiang, Jiaqing, et al.
Published: (2024)

Efficiently verifiable quantum advantage on near-term analog quantum simulators
by: Liu, Zhenning, et al.
Published: (2024)

Polynomial time classical versus quantum algorithms for representation theoretic multiplicities
by: Panova, Greta
Published: (2025)

The Tensor as an Informational Resource
by: Christandl, Matthias
Published: (2023)

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

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

Clifford testing: algorithms and lower bounds
by: Hinsche, Marcel, et al.
Published: (2025)

Performance of Gaussian Boson Sampling on Planted Bipartite Clique Detection
by: Chen, Yu-Zhen Janice, et al.
Published: (2025)

Efficient Algorithms for Weakly-Interacting Quantum Spin Systems
by: Mann, Ryan L., et al.
Published: (2026)

Algorithmic Cluster Expansions for Quantum Problems
by: Mann, Ryan L., et al.
Published: (2023)

Random unitaries in extremely low depth
by: Schuster, Thomas, et al.
Published: (2024)

Between proper and square coloring of planar graphs, hardness and extremal graphs
by: Delépine, Thomas
Published: (2026)

Sensitivity and Hamming graphs
by: Asensio, Sara, et al.
Published: (2025)

On the complexity of global Roman domination problem in graphs
by: Reddy, Sangam Balchandar, et al.
Published: (2026)

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

Fast computational deep thermalization
by: Chakraborty, Shantanav, et al.
Published: (2025)

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

Hunting a rabbit: complexity, approximability and some characterizations
by: Ben-Ameur, Walid, et al.
Published: (2025)

Query complexity of Boolean functions on the middle slice of the cube
by: Gerbner, Dániel, et al.
Published: (2023)

$C_{2k+1}$-coloring of bounded-diameter graphs
by: Piecyk, Marta
Published: (2024)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
by: Kunisky, Dmitriy, et al.
Published: (2024)

A parameterized algorithm for $K_r$-factors in graphs of high minimum degree
by: Gan, Luyining, et al.
Published: (2023)

Random ensembles of symplectic and unitary states are indistinguishable
by: West, Maxwell, et al.
Published: (2024)

Learning quantum states and unitaries of bounded gate complexity
by: Zhao, Haimeng, et al.
Published: (2023)

Isometric path complexity of graphs
by: Chakraborty, Dibyayan, et al.
Published: (2022)

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