I want to understand how the precision of promise gap on input size changes the problem's difficulty. I read the guided local Hamiltonian problem (GLHP).

Description of GLHP: We have been given a Hamiltonian and a 'good guessed' ground state. Determine if the ground state eigenvalue $\lambda_0\leq \alpha$ or $\lambda_0\geq \beta$. Where $\alpha, \beta \in \mathbb{R}$ (page 3, definition 2). In the case of the Guided Local Hamiltonian Problem (link), the hardness depends on the promise gap as follows:

  • BPP if, $\alpha - \beta = \Omega(1)$
  • BQP-complete if, $\alpha - \beta = \Omega(1/poly(n))$
  • QMA-complete if, $\alpha - \beta = \Omega(1/exp(n))$

While inspecting APPROX-QCIRCUIT-PROB (AQP), I don't find such a gap.

I want to know if the promise gap is implicit in the description of APQ.

Description of APPROX-QCIRCUIT-PROB (from wiki):

Given a description of a quantum circuit $C$ acting on $n$ qubits with $m$ gates, where $m$ is a polynomial in $n$, and each gate acts on one or two qubits, and two numbers $\alpha, \beta \in [0,1], \alpha > \beta$, distinguish between the following two cases:

  • measuring the first qubit of the state $C|0\rangle^{\otimes n}$ yields $|1\rangle$ with probability $\geq \alpha$.
  • measuring the first qubit of the state $C|0\rangle^{\otimes n}$ yields $|1\rangle$ with probability $\leq \beta$.

My attempt: I think APQ has a one-bit output, while GLHE has an n-bit output. Thus, the promise gap for AQP is not applicable.

  • $\begingroup$ Wouldn't it be $|\alpha-\beta|$? Imagine if $\alpha=\beta$ or if $|\alpha-\beta|$ were very (exponentially) small - then even a good BQP algorithm couldn't distinguish. $\endgroup$ Commented Apr 29 at 22:15
  • $\begingroup$ Actually no need for absolute values. Just $\alpha-\beta$ because $\alpha>\beta$. $\endgroup$ Commented Apr 30 at 2:00
  • $\begingroup$ @MarkSpinelli, the key reason for my confusion is as follows: There are two sources of precision. 1. the precision on output value (say, eigenvalue estimation). 2. Precision on probabilistic guarantee, like (1/3, 2/3) or 1/2 +1/poly(n). the 2nd one is a generic feature of 'randomized' (like) computation like BPP and BQP. $\endgroup$ Commented May 1 at 6:24
  • $\begingroup$ @MarkSpinelli, I tried to pin down features 1 and 2 in AQP and GLHP problems. I can figure out feature 1 for GLHP (eigenvalue precision), while no mention of feature 2 (I think they have assumed it implicitly). While in AQP, I see feature 2 explicit (probabilistic guarantee). Since AQP is a one-bit output problem. I can't think of what does even output precision would mean. $\endgroup$ Commented May 1 at 6:30
  • $\begingroup$ @MarkSpinelli, precisely I need the following help: How to figure out features 1 and 2 in both problems. Or is there a more straightforward way to look at the problem? :) Thanks! $\endgroup$ Commented May 1 at 6:34

1 Answer 1


For clear estimation problems such as GLHE or diagonal entries of matrix powers, the goal is to estimate a value up to some additive (or multiplicative) error. But often to prove complexity results and containment in classes such as BQP or QMA it's convenient to convert the problem to a (yes/no) decision problem. We do this by converting the additive error into a promise on the true value to be estimated.

For example, the GLHE problem as an estimation could be defined as "given a circuit to prepare good guess of the ground state of a Hamiltonian, estimate the ground state energy up to an additive error of $\alpha-\beta$." But this isn't a yes/no decision problem, so we convert it to "given a good guess as to the ground state of a Hamiltonian as a circuit to prepare this ansatz, and a promise that the true energy is greater than or equal to $\alpha$ and less than or equal to $\beta$, decide which is which."

Turning to the APPROX-QCIRCUIT-PROB, this problem is already framed as a decision problem. Thus, the gap in the above problem is already $\alpha-\beta$. If this gap gets smaller and smaller then the problem is harder and harder to solve, but as long as the gap is $\Omega(1)$ it can be amplified with repetition by applying the Chernoff bound. If the gap is too small then the Chernoff bound won't help.

But, another way to think of the APPROX-QCIRCUIT-PROB is also as an estimation problem - here, we can ask what is the true expectation of the first qubit in the circuit, up to an (additive) error of $\alpha-\beta$? Either way, the gap is $\alpha-\beta$ and as a decision problem it is not well-defined for any true expectation less than $\alpha$ and greater than $\beta$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.