23 citations · 72 across the 15 of their papers we have counts for
13 papers · 1 filter
Polynomial-time classical algorithms for mean-field models up to the glass transition
Alexander Schmidhuber, Alexander Zlokapa
The Sachdev-Ye-Kitaev model is a strongly interacting fermionic system that has been well-studied in condensed matter and high energy physics. It is highly quantum: Gaussian states…
On The Complexity of Redundancy-Free Quantum Hamiltonians
Matthew B. Hastings, Alexander Schmidhuber
We consider a class of redudancy-free Hamiltonians, which are those where the trace vanishes for any product of Hamiltonian terms in which at least one term appears an odd number o…
Adiabatic Quantum Phase Estimation
Alexander Schmidhuber, Seth Lloyd
Quantum phase estimation (QPE) is a central algorithmic primitive that estimates eigenvalues of a Hamiltonian up to precision in Heisenberg-limited time . Standard ga…
Quartic quantum speedups for community detection
Alexander Schmidhuber, Alexander Zlokapa
Community detection is a foundational problem in data science. Its natural extension to hypergraphs captures higher-order correlations beyond pairwise interactions. In this work, w…
Hamiltonian Decoded Quantum Interferometry
Alexander Schmidhuber, Jonathan Z. Lu, Noah Shutty +3
We introduce Hamiltonian Decoded Quantum Interferometry (HDQI), a quantum algorithm that utilizes coherent Bell measurements and the symplectic representation of the Pauli group to…
Constructive interference at the edge of quantum ergodic dynamics
Dmitry A. Abanin, Rajeev Acharya, Laleh Aghababaie-Beni +262
Quantum observables in the form of few-point correlators are the key to characterizing the dynamics of quantum many-body systems. In dynamics with fast entanglement generation, qua…
Phase estimation with partially randomized time evolution
Jakob Günther, Freek Witteveen, Alexander Schmidhuber +3
Quantum phase estimation combined with Hamiltonian simulation is the most promising algorithmic framework to computing ground state energies on quantum computers. Its main computat…
Provable quantum speedups for computing persistence in topological data analysis
Casper Gyurik, Alexander Schmidhuber, Robbie King +2
Topological data analysis (TDA) aims to extract noise-robust features from a data set by examining the number and persistence of holes in its topology. We provide an efficient quan…
Classically estimating observables of noiseless quantum circuits
Armando Angrisani, Alexander Schmidhuber, Manuel S. Rudolph +3
We present a classical algorithm based on Pauli propagation for estimating expectation values of arbitrary observables on random unstructured quantum circuits across all circuit ar…
Optimization by Decoded Quantum Interferometry
Stephen P. Jordan, Noah Shutty, Mary Wootters +6
Achieving superpolynomial speedups for optimization has long been a central goal for quantum algorithms. Here we introduce Decoded Quantum Interferometry (DQI), a quantum algorithm…
Quartic quantum speedups for planted inference
Alexander Schmidhuber, Ryan O'Donnell, Robin Kothari +1
We describe a quantum algorithm for the Planted Noisy XOR problem (also known as sparse Learning Parity with Noise) that achieves a nearly quartic (th power) speedup over the…
Measurement events relative to temporal quantum reference frames
Ladina Hausmann, Alexander Schmidhuber, Esteban Castro-Ruiz
The Page-Wootters formalism is a proposal for reconciling the background-dependent, quantum-mechanical notion of time with the background independence of general relativity. Howeve…
Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis
Alexander Schmidhuber, Seth Lloyd
Quantum algorithms for topological data analysis (TDA) seem to provide an exponential advantage over the best classical approach while remaining immune to dequantization procedures…