233 citations · 531 across the 32 of their papers we have counts for
24 papers · 1 filter
Beyond Light Cones: State Preparation Complexity in Quantum Spin Glasses
Omar Al-Ghattas, David Gamarnik, Bobak T Kiani
We introduce a method for studying state preparation complexity in dense quantum -spin Hamiltonians on qubits, going beyond bounds based only on circuit lightcones. The key…
Sharp universal death of entanglement threshold for Pauli Hamiltonians
Bobak T. Kiani
We determine the exact universal high-temperature separability threshold for Pauli Hamiltonians of bounded degree . If every coefficient in the Hamiltonian has magnitude at…
SYK thermal expectations are classically easy at any temperature
Alexander Zlokapa, Bobak T. Kiani
Estimating thermal expectations of local observables is a natural target for quantum advantage. We give a simple classical algorithm that approximates thermal expectations for Gibb…
Average-case quantum complexity from glassiness
Alexander Zlokapa, Bobak T. Kiani, Eric R. Anschuetz
Glassiness -- a phenomenon in physics characterized by a rough free-energy landscape -- implies hardness for stable classical algorithms. For example, it can obstruct constant-time…
Optimizing Sparse SYK
Matthew Ding, Robbie King, Bobak T. Kiani +1
Finding the ground state of strongly-interacting fermionic systems is often the prerequisite for fully understanding both quantum chemistry and condensed matter systems. The Sachde…
Slow Mixing of Quantum Gibbs Samplers
David Gamarnik, Bobak T. Kiani, Alexander Zlokapa
Preparing thermal (Gibbs) states is a common task in physics and computer science. Recent algorithms mimic cooling via system-bath coupling, where the cost is determined by mixing…
Strongly interacting fermions are non-trivial yet non-glassy
Eric R. Anschuetz, Chi-Fang Chen, Bobak T. Kiani +1
Random spin systems at low temperatures are glassy and feature computational hardness in finding low-energy states. We study the random all-to-all interacting fermionic Sachdev--Ye…
Bounds on the ground state energy of quantum -spin Hamiltonians
Eric R. Anschuetz, David Gamarnik, Bobak T. Kiani
We consider the problem of estimating the ground state energy of quantum -local spin glass random Hamiltonians, the quantum analogues of widely studied classical spin glass mode…
Product states optimize quantum -spin models for large
Eric R. Anschuetz, David Gamarnik, Bobak T. Kiani
We consider the problem of estimating the maximal energy of quantum -local spin glass random Hamiltonians, the quantum analogues of widely studied classical spin glass models. D…
Neural Networks for Programming Quantum Annealers
Samuel Bosch, Bobak Kiani, Rui Yang +2
Quantum machine learning has the potential to enable advances in artificial intelligence, such as solving problems intractable on classical computers. Some fundamental ideas behind…
Combinatorial NLTS From the Overlap Gap Property
Eric R. Anschuetz, David Gamarnik, Bobak Kiani
In an important recent development, Anshu, Breuckmann, and Nirkhe [ABN22] resolved positively the so-called No Low-Energy Trivial State (NLTS) conjecture by Freedman and Hastings.…
Improving the speed of variational quantum algorithms for quantum error correction
Fabio Zoratti, Giacomo De Palma, Bobak Kiani +4
We consider the problem of devising a suitable Quantum Error Correction (QEC) procedures for a generic quantum noise acting on a quantum circuit. In general, there is no analytic u…
Efficient classical algorithms for simulating symmetric quantum systems
Eric R. Anschuetz, Andreas Bauer, Bobak T. Kiani +1
In light of recently proposed quantum algorithms that incorporate symmetries in the hope of quantum advantage, we show that with symmetries that are restrictive enough, classical a…
Analog quantum variational embedding classifier
Rui Yang, Samuel Bosch, Bobak Kiani +2
Quantum machine learning has the potential to provide powerful algorithms for artificial intelligence. The pursuit of quantum advantage in quantum machine learning is an active are…
Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps
Eric R. Anschuetz, Bobak T. Kiani
One of the most important properties of classical neural networks is how surprisingly trainable they are, though their training algorithms typically rely on optimizing complicated,…
Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
Quynh T. Nguyen, Bobak T. Kiani, Seth Lloyd
Many quantum algorithms for numerical linear algebra assume black-box access to a block-encoding of the matrix of interest, which is a strong assumption when the matrix is not spar…
Quantum algorithms for group convolution, cross-correlation, and equivariant transformations
Grecia Castelazo, Quynh T. Nguyen, Giacomo De Palma +3
Group convolutions and cross-correlations, which are equivariant to the actions of group elements, are commonly used in mathematics to analyze or take advantage of symmetries inher…
Hamiltonian singular value transformation and inverse block encoding
Seth Lloyd, Bobak T. Kiani, David R. M. Arvidsson-Shukur +5
The quantum singular value transformation is a powerful quantum algorithm that allows one to apply a polynomial transformation to the singular values of a matrix that is embedded a…
Learning quantum data with the quantum Earth Mover's distance
Bobak Toussi Kiani, Giacomo De Palma, Milad Marvian +2
Quantifying how far the output of a learning algorithm is from its target is an essential task in machine learning. However, in quantum settings, the loss landscapes of commonly us…
Quantum algorithm for nonlinear differential equations
Seth Lloyd, Giacomo De Palma, Can Gokler +5
Quantum computers are known to provide an exponential advantage over classical computers for the solution of linear differential equations in high-dimensional spaces. Here, we pres…
Quantum advantage for differential equation analysis
Bobak T. Kiani, Giacomo De Palma, Dirk Englund +3
Quantum algorithms for both differential equation solving and for machine learning potentially offer an exponential speedup over all known classical algorithms. However, there also…
Quantum polar decomposition algorithm
Seth Lloyd, Samuel Bosch, Giacomo De Palma +5
The polar decomposition for a matrix is , where is a positive Hermitian matrix and is unitary (or, if is not square, an isometry). This paper shows that the a…
Quantum Medical Imaging Algorithms
Bobak Toussi Kiani, Agnes Villanyi, Seth Lloyd
A central task in medical imaging is the reconstruction of an image or function from data collected by medical devices (e.g., CT, MRI, and PET scanners). We provide quantum algorit…
Learning Unitaries by Gradient Descent
Bobak Toussi Kiani, Seth Lloyd, Reevu Maity
We study the hardness of learning unitary transformations in via gradient descent on time parameters of alternating operator sequences. We provide numerical evidence that, d…