:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Briët, Jop, Gutiérrez, Francisco Escudero, Gribling, Sander
Format:	Preprint
Published:	2022
Subjects:	Quantum Physics Computational Complexity
Online Access:	https://arxiv.org/abs/2212.08559
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

A near-optimal Quadratic Goldreich-Levin algorithm
by: Briët, Jop, et al.
Published: (2025)

Discreteness of asymptotic tensor ranks
by: Briët, Jop, et al.
Published: (2023)

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

How to compute the volume in low dimension?
by: Cornelissen, Arjan, et al.
Published: (2025)

Noisy decoding by shallow circuits with parities: classical and quantum
by: Briët, Jop, et al.
Published: (2023)

Simple algorithms to test and learn local Hamiltonians
by: Gutiérrez, Francisco Escudero
Published: (2024)

Testing and learning structured quantum Hamiltonians
by: Arunachalam, Srinivasan, et al.
Published: (2024)

Certifying and learning quantum Ising Hamiltonians
by: Bluhm, Andreas, et al.
Published: (2025)

Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances
by: Abbas, Amira, et al.
Published: (2025)

Certifying and learning local quantum Hamiltonians
by: Bluhm, Andreas, et al.
Published: (2026)

Quantum information advantage based on Bell inequalities
by: Jain, Rahul, et al.
Published: (2026)

Learning low-degree quantum objects
by: Arunachalam, Srinivasan, et al.
Published: (2024)

An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
by: Aldi, Marco, et al.
Published: (2024)

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

Mutually unbiased bases: polynomial optimization and symmetry
by: Gribling, Sander, et al.
Published: (2021)

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

Asymptotic tensor rank is characterized by polynomials
by: Christandl, Matthias, et al.
Published: (2024)

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

Learning quantum states prepared by shallow circuits in polynomial time
by: Landau, Zeph, et al.
Published: (2024)

Quantum speedups for linear programming via interior point methods
by: Apers, Simon, et al.
Published: (2023)

A note on polynomial-time tolerant testing stabilizer states
by: Arunachalam, Srinivasan, et al.
Published: (2024)

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

An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory
by: Pirnay, Niklas, et al.
Published: (2022)

Improved Hardness Results for the Guided Local Hamiltonian Problem
by: Cade, Chris, et al.
Published: (2022)

Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States
by: Cade, Chris, et al.
Published: (2022)

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

Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
by: Hiromasa, Ryo, et al.
Published: (2022)

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

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

Certificate Games and Consequences for the Classical Adversary Bound
by: Chakraborty, Sourav, et al.
Published: (2022)

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

Improved Quantum Query Upper Bounds Based on Classical Decision Trees
by: Cornelissen, Arjan, et al.
Published: (2022)

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

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

Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes
by: Cardoso, Ricardo Rivera, et al.
Published: (2025)

More-efficient Quantum Multivariate Mean Value Estimator from Generalized Grover Operator
by: Tang, Letian
Published: (2025)

Commuting Local Hamiltonians Beyond 2D
by: Bostanci, John, et al.
Published: (2024)

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

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