Cover Image

Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Lemus, Mariano, Faleiro, Ricardo, Mateus, Paulo, Paunković, Nikola, Souto, André
Format:	Preprint
Published:	2023
Subjects:	Quantum Physics Computational Complexity Mathematical Physics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

Efficient simulation of parametrized quantum circuits under non-unital noise through Pauli backpropagation
by: Martinez, Victor, et al.
Published: (2025)

Pseudo-deterministic Quantum Algorithms
by: Aaronson, Hugo, et al.
Published: (2026)

Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis
by: Bu, Kaifeng, et al.
Published: (2023)

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

Rapidly mixing loop representation quantum Monte Carlo for Heisenberg models on star-like bipartite graphs
by: Takahashi, Jun, et al.
Published: (2024)

A polynomial-time classical algorithm for noisy quantum circuits
by: Schuster, Thomas, et al.
Published: (2024)

Semi-Quantum Conference Key Agreement with GHZ-type states
by: Barreiro, Rúben, et al.
Published: (2025)

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

A learning theory for quantum photonic processors and beyond
by: Rosati, Matteo
Published: (2022)

The membership problem for constant-sized quantum correlations is undecidable
by: Fu, Honghao, et al.
Published: (2021)

On the Computational Complexity of Schrödinger Operators
by: Zheng, Yufan, et al.
Published: (2024)

Proof of Hiding Conjecture in Gaussian Boson Sampling
by: Shou, Laura, et al.
Published: (2025)

Fermionic Gaussian Testing and Non-Gaussian Measures via Convolution
by: Lyu, Xingjian, et al.
Published: (2024)

Convergence efficiency of quantum gates and circuits
by: Kong, Linghang, et al.
Published: (2024)

Poincaré Duality and Multiplicative Structures on Quantum Codes
by: Li, Yiming, et al.
Published: (2025)

Optimal, Qubit-Efficient Quantum Vehicle Routing via Colored-Permutations
by: Onah, Chinonso, et al.
Published: (2026)

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

Wasserstein Complexity of Quantum Circuits
by: Li, Lu, et al.
Published: (2022)

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

Quantum Merlin-Arthur proof systems for synthesizing quantum states
by: Delavenne, Hugo, et al.
Published: (2023)

Performance of Practical Quantum Oblivious Key Distribution
by: Lemus, Mariano, et al.
Published: (2025)

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

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

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

Quasi-quantum states and the quasi-quantum PCP theorem
by: Arad, Itai, et al.
Published: (2024)

Classical versus quantum queries in quantum PCPs with classical proofs
by: Buhrman, Harry, et al.
Published: (2024)

Rational degree is polynomially related to degree
by: Kothari, Robin, et al.
Published: (2026)

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

Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
by: Anand, Kartik, et al.
Published: (2025)

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

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

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

Quantum computational complexity of matrix functions
by: Cifuentes, Santiago, et al.
Published: (2024)

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

The 7 faces of quantum NP
by: Gharibian, Sevag
Published: (2023)

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

Classifying Entanglement by Algebraic Geometry
by: Gharahi, Masoud
Published: (2024)