5 papers
On the Complexity of Decoded Quantum Interferometry
Kunal Marwaha, Bill Fefferman, Alexandru Gheorghiu +1
We study the complexity of Decoded Quantum Interferometry (DQI), a quantum algorithm for approximate optimization. First, we show that the algorithm resists classical simulation st…
Wavefunction Flows: Efficient Quantum Simulation of Continuous Flow Models
David Layden, Ryan Sweke, VojtÄch HavlÃÄek +2
Flow models are a cornerstone of modern machine learning. They are generative models that progressively transform probability distributions according to learned dynamics. Specifica…
Quantum Algorithms for Representation-Theoretic Multiplicities
Martin Larocca, Vojtech Havlicek
Kostka, Littlewood-Richardson, Plethysm and Kronecker coefficients are the multiplicities of irreducible representations in the decomposition of representations of the symmetric gr…
Classical and quantum algorithms for characters of the symmetric group
Sergey Bravyi, David Gosset, Vojtech Havlicek +1
Characters of irreducible representations are ubiquitous in group theory. However, computing characters of some groups such as the symmetric group is a challenging problem kn…
On the hardness of cloning and connections to representation theory
VojtÄch HavlÃÄek, Chinmay Nirkhe
The states accepted by a quantum circuit are known as the witnesses for the quantum circuit's satisfiability. The assumption BQP does not equal QMA implies that no efficient algori…