REVIEW 5 cited by
Quantum Speed-ups for Semidefinite Programming
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
We give a quantum algorithm for solving semidefinite programs (SDPs). It has worst-case running time $n^{\frac{1}{2}} m^{\frac{1}{2}} s^2 \text{poly}(\log(n), \log(m), R, r, 1/\delta)$, with $n$ and $s$ the dimension and row-sparsity of the input matrices, respectively, $m$ the number of constraints, $\delta$ the accuracy of the solution, and $R, r$ a upper bounds on the size of the optimal primal and dual solutions. This gives a square-root unconditional speed-up over any classical method for solving SDPs both in $n$ and $m$. We prove the algorithm cannot be substantially improved (in terms of $n$ and $m$) giving a $\Omega(n^{\frac{1}{2}}+m^{\frac{1}{2}})$ quantum lower bound for solving semidefinite programs with constant $s, R, r$ and $\delta$. The quantum algorithm is constructed by a combination of quantum Gibbs sampling and the multiplicative weight method. In particular it is based on a classical algorithm of Arora and Kale for approximately solving SDPs. We present a modification of their algorithm to eliminate the need for solving an inner linear program which may be of independent interest.
Forward citations
Cited by 5 Pith papers
-
A distillation-teleportation protocol for fault-tolerant QRAM
An adaptive distillation-teleportation protocol implements a fault-tolerant QRAM query with poly(n) quantum resources and 1/poly(n) device fidelity, at the cost of an exponential classical dataset update each round.
-
Maximum channel entropy principle and microcanonical channels
A maximum-entropy principle for quantum channels yields thermal channels with exponential form, analogous to thermal states.
-
Thermalization with partial information
A maximum channel entropy principle, backed by a microcanonical-style derivation, identifies the canonical noisy channel that models thermalization under partial information.
-
Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities
Quantum algorithms for bandits with knapsacks achieve improved regret and time complexity by replacing classical sampling with quantum Monte Carlo and approximate quantum LP solving.
-
Canonical Partition Function on a Quantum Computer through Trotter Interpolation
Estimates the canonical partition function of a Hamiltonian by interpolating Trotter error, replacing the quantum walk with generalized quantum signal processing on a Trotterized evolution operator.
Discussion (0). Sign in to comment.