2
$\begingroup$

This is in a similar spirit to another question I asked here.

Let's say I am given a $k$-local Hamiltonian $H$. We know that $||H|| \leq 1$. Let the ground state be $|\psi_{0}\rangle$, with energy $E_{0}$. Let $U$ be an $n$-qubit unitary such that \begin{equation} U |\psi_{0}\rangle |00\cdots0\rangle = |\psi_{0}\rangle |E_{0}\rangle. \end{equation}

Let $V$ be an $n$-qubit unitary such that \begin{equation} V |00\cdots0\rangle = |\psi_{0}\rangle, \end{equation}

Can we implement both $U$ and $V$ in polynomial space (ie, with polynomially many qubits), with exponentially many gates from a universal gate set, upto an inverse exponential (in the number of qubits) precision? In other words, let $U'$ and $V'$ be what we can actually implement with exponentially many gates, and let $|\psi_{0}'\rangle$ and $E_{0}'$ be the ground state and the ground energy we get by applying $V'$ and $U'$ respectively. What is the relation between $|\psi_{0}\rangle$ and $|\psi_{0}'\rangle$, and $E_{0}$ and $E_{0}'$? Are they also within an inverse exponential additive error to each other?

If so, is this an alternative proof that the $k$-local Hamiltonian problem, which is complete for QMA, can be solved in BQPSPACE (the quantum analogue of PSPACE)?

Is this also why we do not know if QMA is contained in BQP? In other words, we do not know if there is a description of $U$ and $V$ which requires only polynomially many gates.

$\endgroup$
7
  • $\begingroup$ QMA is likely much larger than BQP. What do you mean by whether we know if QMA is contained in BQP? Both contain P and both are contained in PSPACE; separation is likely very difficult. $\endgroup$ Oct 15, 2020 at 2:59
  • $\begingroup$ We do not know if QMA is contained in BQP. My question is, can that fact be reduced to the fact that we do not know a polynomial description of the unitaries $U$ and $V$? If we had such a description, we would be able to put QMA in BQP. $\endgroup$
    – BlackHat18
    Oct 15, 2020 at 3:20
  • $\begingroup$ If QMA is contained in BQP, then QMA=BQP, because BQP is contained in QMA. $\endgroup$ Oct 15, 2020 at 3:34
  • $\begingroup$ Yes. I wanted to ask whether the fact that we do not know if these two classes are equal can be reduced to the fact that we do not know a polynomial description of the two unitaries. $\endgroup$
    – BlackHat18
    Oct 15, 2020 at 5:49
  • $\begingroup$ In your description, is not $U'$ just a circuit for a quantum phase estimation (QPE) algorithm, which can be implemented with a polynomial number of gates? $\endgroup$ Oct 15, 2020 at 14:18

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.