Is distinguishing a certain outcome from an uncertain outcome BQP-hard?

Question

Let $C$ be a description of a quantum circuit on $n$ qubits with poly($n$) 2-local gates. The defining BQP-complete problem, APPROX-QCIRCUIT-PROB distinguishes two cases:

1. $\langle 0 ... 0| C^\dagger P_{\lvert 1 \rangle} C|0...0 \rangle \geq \alpha$
2. $\langle 0 ... 0| C^\dagger P_{\lvert 1 \rangle} C|0...0 \rangle \leq \beta$

for two numbers $\alpha, \beta \in (0,1), \alpha > \beta$ and $P_{\lvert 1 \rangle}$ projecting the first qubit onto $|1\rangle$.

I am wondering whether it is possible to easily shift the focus from a single qubit to a single bitstring and reduce the problem distinguishing

1. $|\langle 0 ... 0| C|0...0 \rangle|^2 \geq \alpha$
2. $|\langle 0 ... 0| C|0...0 \rangle|^2 \leq \beta$

to APPROX-QCIRCUIT-PROB. In other words, if we call the outcome in case 1 ($\alpha$-)certain and in case 2 ($\beta$)-uncertain is distinguishing a certain outcome from an uncertain outcome BQP-hard?

I would be fine with focusing on $1 - \alpha = \mathcal{O}(2^{-n})$ as well as $\beta = \mathcal{O}(2^{-n})$.

Answer 1

Assume $\alpha = \Omega(1/poly(n))$ and $\beta = \mathcal{O}(2^{-n})$. $C$ maps an initial state $\vert 0...0\rangle$ to the state $$C \vert 0... 0 \rangle = a \vert 0\rangle \otimes \vert \phi_0\rangle + b \vert 1 \rangle \otimes \vert \phi_1 \rangle $$ with $a,b \in \mathbb{C}, \ |a|^2 + |b|^2 = 1$. In order to solve APPROX-QCIRCUIT-PROB, one has to decide whether $|b|^2 \geq \alpha$ or $|b|^2 \leq \beta$ promised that one of those holds. This can be done by reducing it to the second problem that decides whether there is a peak in the output probability of $| 0...0 \rangle$. For this, add an ancillary qubit $A$ initialized in $|0 \rangle_A$ and consider the circuit $X_A \ C^\dagger \ CNOT_{1,A} \ C$ that executes $C$, copies the classical output of qubit 1 into $A$, then inverts the circuit $C$ again and finally flips the ancilla. The probability of measuring the all-zero bitstring $|0...0\rangle \otimes \vert 0\rangle_A$ reads $$\langle 0...0 0_A| X_A C^\dagger CNOT_{1,A} C | 0...0 0_A\rangle = \left( \bar a \langle 01_A | \otimes \langle \phi_0 | + \bar b \langle 11_A | \otimes \langle \phi_1 | \right) \left( a | 0 0_A \rangle \otimes |\phi_0 \rangle + b | 11_A \rangle \otimes | \phi_1 \rangle \right) = |b|^2. $$ Using $\mathcal{O}(poly(n))$ samples, we can map outputs 1. and 2. to the outputs of APPROX-QCIRCUIT-PROB and decide with bounded failure probability.