# What is the promise gap in APPROX-CIRCUIT-VALUE (BQP-complete) problem?

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.

• 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. Commented Apr 29 at 22:15
• Actually no need for absolute values. Just $\alpha-\beta$ because $\alpha>\beta$. Commented Apr 30 at 2:00
• @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. Commented May 1 at 6:24
• @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. Commented May 1 at 6:30
• @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! Commented May 1 at 6:34

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$$.