Excellent question. You've hit upon a very subtle but important point in the analysis of in-place QMA amplification.

Your analysis is completely correct. The Marriott-Watrous (MW05) amplification scheme does not guarantee that an arbitrary "good" witness for the original verifier will remain a "good" witness for the amplified verifier.

Let's break down why this is the case and then answer your core question.

Why the MW05 Scheme Doesn't Preserve All Good Witnesses

As you've correctly identified, the MW05 procedure is essentially a form of phase estimation. Let's formalize this slightly to see the issue clearly.

1. The Verifier and the Operator R: For a given verifier circuit that acts on a witness state and ancillas , the acceptance probability is . MW05 define an operator that acts only on the witness space, such that for any witness , the expected value is the acceptance probability: .

2. The Reflection Unitary G: They then define a unitary operator related to whose phase reflects this probability. Specifically, the eigenvalues of are , and the corresponding eigenvalues of are . A high acceptance probability (large ) corresponds to a large phase angle .

3. The Amplified Verifier M': The new verifier performs phase estimation on the operator using the provided witness as the target state. If the estimated phase is large (i.e., corresponds to an acceptance probability ), accepts. If the phase is small (corresponding to probability ), rejects.

The Problem with Superpositions:

• If the witness provided to is an eigenvector of (and thus of ), phase estimation works beautifully. It will estimate the single phase with very high accuracy, and the verifier will accept or reject almost deterministically.

• However, a general "good" witness is a superposition of eigenvectors: . The initial acceptance probability is .

• When the amplified verifier runs phase estimation on , the final state before measurement is a superposition: , where is the clock register's estimate of the phase .

• Measuring the clock register will yield a "good" phase estimate with probability (where is the set of "good" eigenvectors with ) and a "bad" phase estimate with probability .

Your formula is a great summary of the final acceptance probability of on witness : Assuming the phase estimation is nearly perfect (which it is for large enough repetition count ), this becomes .

As you noted, it's entirely possible to have a state where the average probability is high, but the total weight on "good" eigenvectors is low. Such a state would be a valid witness for the original machine but would likely be rejected by the amplified machine .

Q: Is there a way to perform this amplification while guaranteeing all valid witnesses stay valid?

The short answer is: No, this is not believed to be possible with known techniques, and it seems to face fundamental obstacles.

Here’s the reasoning:

1. The "Black Box" Nature of the Witness

Any "in-place" amplification scheme constructs a new verifier from the old verifier . This new verifier must act on the witness state it receives. The verifier does not "know" the decomposition . It can only interact with via the original circuit (or related operators like ).

Consider two different witnesses:

• , an eigenvector with acceptance probability .
• , where has probability 1 and has probability 0.

The acceptance probability for the original verifier is identical for both witnesses:

• .
• .

A hypothetical amplification procedure that keeps all good witnesses valid must amplify the success probability for both and to near 1. However, any procedure based on phase estimation (like MW05) will treat them differently:

• On , it will measure a phase corresponding to and accept.
• On , it will measure a phase corresponding to with probability , and a phase for with probability . The total acceptance probability will be stuck at .

For a method to distinguish from and amplify both, it would need more information than just the ability to run the verifier circuit . This seems impossible due to the linearity of quantum mechanics.

2. Why This Isn't a Problem for the Definition of QMA

The crucial point is that the definition of the complexity class QMA does not require this strong property.

• Completeness: For a YES instance, there exists (∃) a witness such that the verifier accepts with probability .
• Soundness: For a NO instance, for all (∀) states , the verifier accepts with probability .

The MW05 proof works perfectly within this definition:

1. If is a YES instance for , there exists a witness with .
2. This implies that the operator has at least one eigenvalue . Let the corresponding eigenvector be .
3. Merlin, being all-powerful, can simply provide this "best" witness to the amplified verifier .
4. Since is an eigenvector, will accept it with probability .
5. Therefore, for the YES instance , there exists a witness for that is accepted with high probability. This satisfies the completeness condition for the new machine .

The original "good" witness serves only as a proof that a "best" eigenvector witness exists. Merlin is free to change the witness he sends from to when talking to the amplified verifier. The witness size remains the same, so the amplification is still "in-place".

In conclusion, your observation is sharp and correct, but it highlights a feature, not a bug, of the amplification process. The goal of QMA amplification is to create a new machine with a better probability gap, not to preserve the accepting status of every single pre-existing witness state.