  In computer science, many search problems are reducible to decision problems,
which implies that finding a solution is as hard as deciding whether a solution
exists. A quantum analogue of search-to-decision reductions would be to ask
whether a quantum algorithm with access to a $\mathsf{QMA}$ oracle can
construct $\mathsf{QMA}$ witnesses as quantum states. By a result from Irani,
Natarajan, Nirkhe, Rao, and Yuen (CCC '22), it is known that this does not hold
relative to a quantum oracle, unlike the cases of $\mathsf{NP}$, $\mathsf{MA}$,
and $\mathsf{QCMA}$ where search-to-decision relativizes. We prove that if one
is not interested in the quantum witness as a quantum state but only in terms
of its partial assignments, i.e. the reduced density matrices, then there
exists a classical polynomial-time algorithm with access to a $\mathsf{QMA}$
oracle that outputs approximations of the density matrices of a near-optimal
quantum witness, for any desired constant locality and inverse polynomial
error. Our construction is based on a circuit-to-Hamiltonian mapping that
approximately preserves near-optimal $\mathsf{QMA}$ witnesses and a new
$\mathsf{QMA}$-complete problem, Low-energy Density Matrix Verification, which
is called by the $\mathsf{QMA}$ oracle to adaptively construct approximately
consistent density matrices of a low-energy state.
