`LinearCombination` block encoding may be leaving `resource` register dirty, affecting `ChebyshevPolynomial`

[charlesyuan314]

Evidence for this was encountered when debugging ChebyshevPolynomial. We are currently unable to correctly construct polynomials of complex linear combinations, which seems to be because reflecting on the ancilla register is not enough.

For example, while we can correctly block-encode $T_n(\frac{X+H}{2})$, trying to compute $T_2(\frac{X+3H}{4})$ yields an incorrect result. This error seems to be caused by LinearCombination rather than ChebyshevPolynomial, as writing a (1,1,0)-block-encoding for $\frac{X+3H}{4}$ as a matrix by hand yields the correct answer. The linear combination here uses 1 ancilla qubit but also 4 resource qubits, which are not left zero.

One theory I have so far is that the problem lies in the Select oracle, which may be somehow modifying its selection register in such a way that the Prepare oracle is not correctly uncomputing its junk.

Related: #1233

[charlesyuan314]

@anurudhp points out that this may be an inherent limitation of alias sampling. From the paper:

Select itself necessarily introduces entanglement between its target register |ψ> and the index register |l> (plus associated junk register). So Prepare† will not exactly restore |l> or the junk register. Although we only specify the action of Prepare on the |0> state, Prepare will be applied to other states due to this imperfect uncomputation effect.

So we are faced with a tradeoff of either 1) using alias sampling and treating dirty resource qubits as ancilla, or 2) switching to e.g. state preparation by rotation. Either way, ancilla count goes up.