187 citations · 264 across the 10 of their papers we have counts for
13 papers
Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture
Jordi Weggemans, Marten Folkertsma, Chris Cade
We study 'Merlinized' versions of the recently defined Guided Local Hamiltonian problem, which we call 'Guidable Local Hamiltonian' problems. Unlike their guided counterparts, thes…
Improved Hardness Results for the Guided Local Hamiltonian Problem
Chris Cade, Marten Folkertsma, Sevag Gharibian +4
Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum alg…
Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States
Chris Cade, Marten Folkertsma, Jordi Weggemans
Recently it was shown that the so-called guided local Hamiltonian problem -- estimating the smallest eigenvalue of a -local Hamiltonian when provided with a description of a qua…
Quantum Algorithms for Community Detection and their Empirical Run-times
Chris Cade, Marten Folkertsma, Ido Niesen +1
We apply our recent work on empirical estimates of quantum speedups to the practical task of community detection in complex networks. We design several quantum variants of a popula…
Quantifying Grover speed-ups beyond asymptotic analysis
Chris Cade, Marten Folkertsma, Ido Niesen +1
Run-times of quantum algorithms are often studied via an asymptotic, worst-case analysis. Whilst useful, such a comparison can often fall short: it is not uncommon for algorithms w…
Quantum Motif Clustering
Chris Cade, Farrokh Labib, Ido Niesen
We present three quantum algorithms for clustering graphs based on higher-order patterns, known as motif clustering. One uses a straightforward application of Grover search, the ot…
Complexity of Supersymmetric Systems and the Cohomology Problem
Chris Cade, P. Marcos Crichigno
We consider the complexity of the local Hamiltonian problem in the context of fermionic Hamiltonians with supersymmetry and show that the problem remains $\mathsf{Q…
Towards quantum advantage via topological data analysis
Casper Gyurik, Chris Cade, Vedran Dunjko
Even after decades of quantum computing development, examples of generally useful quantum algorithms with exponential speedups over classical counterparts are scarce. Recent progre…
Strategies for solving the Fermi-Hubbard model on near-term quantum computers
Chris Cade, Lana Mineh, Ashley Montanaro +1
The Fermi-Hubbard model is of fundamental importance in condensed-matter physics, yet is extremely challenging to solve numerically. Finding the ground state of the Hubbard model u…
The one clean qubit model without entanglement is classically simulable
Mithuna Yoganathan, Chris Cade
Entanglement has been shown to be necessary for pure state quantum computation to have an advantage over classical computation. However, it remains open whether entanglement is nec…
Post-selected Classical Query Complexity
Chris Cade
We study classical query algorithms with post-selection, and find that they are closely connected to rational functions with nonnegative coefficients. We show that the post-selecte…
The Quantum Complexity of Computing Schatten -norms
Chris Cade, Ashley Montanaro
We consider the quantum complexity of computing Schatten -norms and related quantities, and find that the problem of estimating these quantities is closely related to the one cl…
Time and Space Efficient Quantum Algorithms for Detecting Cycles and Testing Bipartiteness
Chris Cade, Ashley Montanaro, Aleksandrs Belovs
We study space and time efficient quantum algorithms for two graph problems -- deciding whether an -vertex graph is a forest, and whether it is bipartite. Via a reduction to the…