  Semidefinite programs (SDPs) are a particular class of convex optimization
problems with applications in combinatorial optimization, operational research,
and quantum information science. Seminal work by Brand\~{a}o and Svore shows
that a ``quantization'' of the matrix multiplicative-weight algorithm can
provide approximate solutions to SDPs quadratically faster than the best
classical algorithms by using a quantum computer as a Gibbs-state sampler. We
propose a modification of this quantum algorithm and show that a similar
speedup can be obtained by replacing the Gibbs-state sampler with the
preparation of thermal pure quantum (TPQ) states. While our methodology incurs
an additional problem-dependent error, which decreases as the problem size
grows, it avoids the preparation of purified Gibbs states, potentially saving a
number of ancilla qubits. In addition, we identify a spectral condition which,
when met, reduces the resources further, and shifts the computational
bottleneck from Gibbs state preparation to ground-state energy estimation. With
classical state-vector simulations, we verify the efficiency of the algorithm
for particular cases of Hamiltonian learning problems. We are able to obtain
approximate solutions for two-dimensional spinless Hubbard and one-dimensional
Heisenberg XXZ models for sizes of up to $N=2^{10}$ variables. For the Hubbard
model, we provide an estimate of the resource requirements of our algorithm,
including the number of Toffoli gates and the number of qubits.
