Fast Amplification of QMA

Introduction

Which decision problems (yes/no questions) can be efficiently solved on a classical computer? All such problems constitute the complexity class P. The goal of many algorithm designers is to place problems into P by finding efficient algorithms for themSee e.g. the recent example of an algorithm for deciding whether a number is prime .. Another notable complexity class called NP, is the class of problems whose solutions can be efficiently verified. However, finding these solutions might be hard, as NP contains notoriously hard problems like Satisfiability . Whether all the problems in NP could be actually solved in polynomial time (i.e. ${\textsf{P}}\stackrel{{\scriptstyle?}}{{=}}{\textsf{NP}}$) is one of the most interesting open questions of modern computer science .

The problems efficiently solvable with randomized circuits, i.e. with circuits that are allowed to fail with some bounded probability, constitute the class BPP. When we now allow the solution-verifying procedure in the definition of NP to have a small probability of failure, we get the complexity class MA. This acronym stands for “Merlin-Arthur”, as the verifying protocol for the problems in MA goes like this: an all-powerful Merlin provides a ‘proof’ (also called a witness) which a rational Arthur verifies. The problems in MA are those for which Merlin can convince Arthur that the answer to his question is ‘yes’ if it is so, while he has a low probability of fooling Arthur in the ‘no’ cases.

The world is quantum mechanical, so it is natural to ask what can be efficiently computed on a quantum computer? All such problems form the complexity class BQP, and include such problems as factoring and approximating the Jones Polynomial . Kitaev and Watrous defined a quantum analogue of the class MA, calling it QMA (Quantum Merlin-Arthur).

Let us look at the verifying procedure in more detail, starting with an exact definition of QMA.

Consider a language (a set of ‘yes’/‘no’ questions) $L=L_{yes}\cup L_{no}$. Denote its instances $x$. The language $L$ belongs to the class QMA if

there exists a uniform family of quantum verifier circuits $V$ working on $n=poly(|x|)$ qubits and $m=poly(|x|)$ ancillae, and two numbers $a,b$, with separation $a-b$ lower bounded by an inverse polynomial in $n$,

for $x\in L_{yes}$ (the answer to the question $x$ is ‘yes’), there exists a witness $\left|\psi\right\rangle$ such that the circuit $V$ on $\left|\psi\right\rangle\left|0\right\rangle^{\otimes m}$ outputs ‘yes’ (Arthur is convinced) with probability $p_{max}\geq a$,

for $x\in L_{no}$, for any state $\left|\varphi\right\rangle$, the circuit $V$ on $\left|\varphi\right\rangle\left|0\right\rangle^{\otimes m}$ outputs ‘yes’ (is fooled) with probability $p_{max}\leq b$,

When the separation $a-b$ for a verifier circuit $V$ is small, it could take Merlin many verification rounds to convince Arthur that the answer to the question $x$ really is ‘yes’. However, the separation $a-b$ can be amplified by modifying the original verifier circuit, obtaining a new amplified circuit with strong promise bounds

The first such amplification procedure by Kitaev uses a circuit made from

(for some constant $c$) parallel copies of the circuit $V$, with majority voting at the end. Kitaev showedNote that it was necessary to show that entangled witnesses wouldn’t help Merlin to cheat in the ‘no’ cases. that this new circuit has the strong promise bounds (1). The drawback of this procedure is that Merlin now has to provide an $N$ times longer witness.

In , Marriott and Watrous showed that a single quantum witness of length $n$ suffices, finding a verification procedure which reuses this witness many times. Their amplified circuit uses $N$ copies (2) of the original circuit $V$ and its conjugate $V^{\dagger}$, interspersed with some additional operations. The procedure ends with $N$ measurements and classical processing of the results. Arguments employing Chernoff bounds are then used to establish the strong bounds (1) in the ‘yes’ and ‘no’ cases. We give further details about their approach in Section 2.2.

The first result of our paper is a new and faster QMA amplification method.

Consider a verifier circuit $V$ for a problem in QMA, acting on $n$ qubits and $m$ ancillae, with promise bounds $a$ and $b$. There exists an amplified verifier circuit $V^{\prime}$ acting on $n$ qubits and $poly(n)$ ancillae, using

evaluations of the original circuit $V$ and its conjugate $V^{\dagger}$, with promise bounds amplified to (1).

Note that the dependence of $N^{\prime}$ on $\frac{1}{a-b}$ is quadratically better than in (2). This speedup is possible because our circuit $V^{\prime}$ uses intrinsically quantum methods for producing its final answer. There are two ideas behind our construction. First, we utilize the connection between a product of two reflections and a generalized quantum walk. Second, the final coherent processing in the circuit is based on phase estimation (or alternatively, the filter state method of Poulin and Wocjan ) instead of classical majority voting (as in ) or counting (as in ).

When $a$ in the definition of QMA is exactly 1, we get a special case of QMA, called QMA1, or QMA with one-sided error. In this case, there exists a witness which the circuit $V$ accepts without failing. A typical example of a problem in this class is Bravyi’s Quantum $k$-SAT . In the classical world, the class MA with probabilistic verifier circuits can be amplified to MA without errors . However, it is a big open question, whether the corresponding quantum classes are equal, i.e. whether ${\textsf{QMA}}={\textsf{QMA}}_{1}$. In , Aaronson argued that this problem is hard and gave an oracle separating them. The second result of our paper is a step towards answering whether ${\textsf{QMA}}\stackrel{{\scriptstyle?}}{{=}}{\textsf{QMA}}_{1}$. We show that for a class of QMA verifier circuits, we can amplify the probability promise $a$ up to 1 exactly, as opposed to exponentially approaching it as in (1).

Let $V$ be a verifier circuit for an instance of a language in QMA, with promise bounds $a$ and $b$, and let $p_{max}$ be its highest acceptance probability $p_{max}$ in the ‘yes’ case. When $\varphi_{\min}=\frac{1}{\pi}\arccos\sqrt{p_{max}}$ can be expressed exactly by $t=polylog(|x|)$ bits, there exists a circuit $V^{*}$ on $n+t$ qubits and $poly(n)$ ancillae whose acceptance probability in the ‘yes’ case is exactly 1. Said alternatively, ${\textsf{QMA}}_{1}$ is equal to this subclass of QMA.

Note that besides the witness, the new verifier circuit $V^{*}$ needs to receive the description of $a^{*}$. Also note that obtaining a result of this type is possible only because of the coherent phase-estimation processing. Marriott and Watrous’ QMA amplification scheme can not be used to amplify the probabilities to $1$ exactly, because of the inherent probabilistic nature of the measurements.

The paper is organized as follows. First, in Section 2.1 we establish two important geometrical facts about two projectors, required for the analysis of the amplification protocols. In Section 2.2 we revisit the witness-preserving QMA amplification protocol of Marriott and Watrous . Then in Section 2.3 we give a faster QMA amplification method utilizing phase estimation instead of classical final processing. Second, in Section 3 we show that in a special case when the maximum acceptance probability of the verifier circuit has a particular description, we can amplify it to 1 exactly. Finally, in Section 4, inspired by our fast QMA amplification, we simplify the method for preparing QMA witnesses by Poulin and Wocjan , based on filter states.

We conclude with a discussion of our results in Section 5. Finally, Appendix A contains a new proof of the relationship of the eigenvalue gap of a classical random walk and the phase gap of a quantum walk, based on Jordan’s lemma.

Fast QMA Amplification

We arrive at our new QMA amplification scheme, based on phase estimating a certain unitary operator, in several steps. First, with the help of Jordan’s lemma, we look at how two projectors act in a Hilbert space. This helps us to understand the Marriott and Watrous amplification scheme in Section 2.2, based on alternative projective measurements. Second, Jordan’s lemma, together with a connection from quantum walks, leads us to realize that a product of the reflections about the supports of the projectors acts as a rotation within certain subspaces of the Hilbert space. Instead of projective measurements, we thus base our amplification scheme of Section 2.3 on the phase estimation of these rotations. This leads to a speedup in the number of the required evaluations of the verifier circuit.

In this geometrically-focused section, we establish several facts required for understanding both Marriott and Watrous’ witness preserving QMA amplification of Section 2.2, and our new method in Section 2.3.

First, consider two projectors $\Pi_{0}$ and $\Pi_{1}$ on the Hilbert space $\mathcal{H}$. Jordan’s lemma (see also Appendix A) tells us that given two projectors, we can decompose our Hilbert space into

two-dimensional subspaces $S_{i}$ invariant under $\Pi_{0}$ and $\Pi_{1}$, and

one-dimensional subspaces $T_{j}$, on which $\Pi_{0}\Pi_{1}$ is an identity or a zero-rank projector.

Let us focus on the more interesting two-dimensional subspaces. For each of them, we can choose a basis $\{\left|v_{i}\right\rangle,|v_{i}^{\perp}\rangle\}$, obeying

We can also choose another basis $\{\left|w_{i}\right\rangle,|w_{i}^{\perp}\rangle\}$ for $S_{i}$ from the eigenvectors of $\Pi_{1}$, obeying

We can also make a choice of phases so that $\langle v_{i}|w_{i}\rangle$ is a real positive number, and define the principal angle

Let $p_{i}$ be the expectation value of $\Pi_{1}$ in the state $\left|v_{i}\right\rangle$. In Sections 2.2 and 2.3, $p_{i}$ will be the probability that the verifier circuit $V$ accepts the state $\left|v_{i}\right\rangle$. The projector $\Pi_{1}$ restricted to the subspace $S_{i}$ is $\left|w_{i}\right\rangle\left\langle w_{i}\right|$, so we have

This symmetrical relationship is an essential element in Marriott and Watrous’ witness-preserving QMA amplification scheme in Section 2.2.

Second, let us look at the reflections about the supports of $\Pi_{0}$ and $\Pi_{1}$:

Using the decomposition of the Hilbert space from Jordan’s lemma, we can prove the following theorem about the eigenvalues of the product of two reflections:

in the two-dimensional invariant subspaces $S_{i}$, and eigenvalues $\pm 1$ in the one-dimensional invariant subspaces $T_{j}$.

Thus, within each two-dimensional subspace $S_{i}$, the product of two reflections $F_{1}F_{0}$ is a rotation by $2\pi\varphi_{i}$, with $\varphi_{i}$ given in (6). We rely on this fact in our fast QMA amplification scheme in Section 2.3.

This theorem, proved by Szegedy is a base component in many results about quantum walks. We also point the interested reader to a new proof of Theorem 3 using Jordan’s lemma in Appendix A.

2 Witness-preserving QMA Amplification

We can now look at the QMA amplification scheme of Marriott and Watrous which we want to speed up. Consider now the two projectors:

with $\Pi_{0}$ projecting onto zeros on the ancilla qubits, and $\Pi_{1}$ projecting on the states that are accepted by the original verifier circuit. Note that the support of $\Pi_{1}$ can contain states with nonzero ancillae. The promise bounds of the original circuit $V$ are $a$ and $b$. The amplification procedure with the strong promise bounds (1) is the following:

Combine a single input witness of length $n$ with fresh ancilla qubits.

Inspect the sequence of results, and count the number of times when two consecutive results differTo allow this number to reach $N$, attach a zero at the start of the sequence of measurement results.. When this number is smaller than $N\frac{a+b}{2}$, output ‘yes’, otherwise output ‘no’.

Let us sketch why this scheme works. Recall the decomposition of the Hilbert space into 2-dimensional and 1-dimensional subspaces in Section 2.1 and focus on the 2D subspaces $S_{i}$. We can choose two bases for each subspace $S_{i}$ as in (4) and (5). Our $\Pi_{0}$ is such that the states $\left|v_{i}\right\rangle$ (4) have the ancillae in the state zero, i.e. $\left|v_{i}\right\rangle=\left|\psi_{i}\right\rangle\left|0\right\rangle$. With our choice of $\Pi_{1}$,

defined in (7) is the probability that the original circuit $V$ accepts the witness $\left|\psi_{i}\right\rangle$.

We now choose some $\left|v_{i}\right\rangle$ as the initial state and perform the sequence of alternating measurements of $\Pi_{0}$ and $\Pi_{1}$, obtaining a bit string. Throughout this procedure, the state of the system stays within the original 2-dimensional subspace $S_{i}$. Moreover, the identities in (8) imply that the probability of obtaining two consecutive 0’s or 1’s (projecting onto $\left|w_{i}\right\rangle$ from $\left|v_{i}\right\rangle$, etc.) is $p_{i}$, while the probability of obtaining $10$ or $01$ is $(1-p_{i})$. The probability of a given sequence of measurement results is then

where $z$ is the number of times consecutive measurement results differ. When getting $z<\frac{N(a+b)}{2}$, we output ‘yes’, and for $z>\frac{N(a+b)}{2}$ we output ‘no’. Marriott and Watrous use arguments based on Chernoff bounds to show that these answers have exponentially good confidence bounds (1). What remains is to show that in the ‘no’ case, a superposition of the states $\left|v_{i}\right\rangle$ for different $i$’s will not help Merlin to fool Arthur.

To summarize, the scheme consists of $N$ measurements (2), and one half of them involves evaluating the circuit $V$ and its conjugate. Note that the processing of the sequence of results is based on classical statistical methods. In the next Section we show that using a natively quantum algorithm (phase estimation or filter states) results in faster amplification.

3 Fast QMA Amplification Based on Phase Estimation

In our new amplification procedure, we utilize the same pair of projectors $\Pi_{0}$ and $\Pi_{1}$ (11) as Marriott and Watrous. However, instead of measuring them directly, we build our circuit using the reflections $F_{0}$ and $F_{1}$ (9) about their supports. Theorem 3 tells us that within the two-dimensional invariant subspaces introduced in Section 2.1, the product $F_{1}F_{0}$ is a rotation by an angle related to an acceptance probability for the original circuit $V$. This turns the problem of accepting or rejecting witnesses for the circuit $V$ into the problem of determining the properties of the rotation coming from the operator $F_{1}F_{0}$. We will show that a small rotation corresponds to a high acceptance probability for the circuit $V$ and vice versa. We thus do phase estimation on the operator $F_{1}F_{0}$, accepting or rejecting the witness depending on the phase we obtain. Finally, to boost the probability of success, we concatenate several such phase estimation procedures, obtaining the desired strong promise bounds (1).

First, let us look at a ‘yes’ case, and show that Merlin can convince us about it. Just as in Section 2.2, he chooses a witness $\left|\psi_{i}\right\rangle$, which we combine with fresh ancillae to get

an eigenvector of $\Pi_{0}$, belonging to one of the two-dimensional invariant subspaces $S_{i}$ we introduced in Section 2.1. From Theorem 3, we know that within this subspace, $F_{1}F_{0}$ has the form $e^{i2\pi\varphi_{i}\hat{\sigma}_{y}}$ and its eigenvalues are $e^{\pm i2\pi\varphi_{i}}$, with $\varphi_{i}$ given by (6). Recalling (10), we can express $\left|v_{i}\right\rangle$ in terms of the eigenvectors $|\varphi_{i}^{\pm}\rangle$ of $F_{1}F_{0}$ as

Merlin chooses his witness $\left|\psi_{i}\right\rangle$ so that the corresponding phase $\varphi_{i}$ is the smallest. According to (12) and (7), such $\varphi_{i}$ corresponds to picking the witness $\left|\psi_{i}\right\rangle$ with the largest possible acceptance probability $p_{i}$. Because we are talking about the ‘yes’ case, this $\varphi_{i}^{(yes)}$ is upper bounded by

where $a$ is the guaranteed acceptance probability for some witness in the definition of QMA. Similarly, for a ‘no’ case, the smallest possible $\varphi_{i}^{(no)}$ is lower bounded by

Our approach will be to measure the rotation phase for the state $\left|v_{i}\right\rangle$ (15), and to resolve whether it is less than $\varphi_{a}$, or larger than $\varphi_{b}$. Note that the phase estimation for the operator $F_{1}F_{0}$ on the state (15) has two possible results $\pm\varphi_{i}$. However, because of the form of (7), we are only interested in the absolute value $|\varphi_{i}|$. We can recognize we got an estimate of the negative phase $-\varphi_{i}$ when we measure $\varphi^{\prime}\in\left[\frac{1}{2},1\right]$, and we then use the value $1-\varphi^{\prime}\in\left[0,\frac{1}{2}\right]$ instead of it.

We get the state (15) on the input, and our phase estimation outputs some value $\varphi^{\prime}$. To be convinced that $|\varphi^{\prime}|$ is smaller than $\varphi_{a}$ or greater than $\varphi_{b}$, we need a precision guarantee

Using the Taylor expansion of $\arccos{x}$ around $x=0$, we bound

as all the coefficients in the sum are positive and we have $a>b$, so we can lower bound the expression by the $n=0$ term. Therefore, we need

bits of precision for our phase estimation. According to , a phase estimation algorithm precise to $n$ bits, with failure probability $\epsilon_{pe}$ requires

ancilla qubits. The number of times we need to perform a controlled-$(F_{1}F_{0})$ operation is then

using (20) and choosing $\epsilon_{pe}\leq\frac{1}{16}$ as an upper bound on the failure probability.

We want our procedure to work with exponentially small failure probability. To achieve this, we concatenate $r$ phase estimation circuits as in Figure 2 and take the median of the $r$ results (recall that we use $|\varphi|\in\left[0,\frac{1}{2}\right]$ here). Because of the following lemmaOur median lemma is a variant of the powering lemma ., the median phase is a good estimate of the actual phase $\varphi_{i}$, with high probability.

Consider a sequence $\{\varphi^{\prime}_{k}\}$ for $k=1,\dots,r$. Let the probability that $\varphi^{\prime}_{k}$ does not belong to an interval $LR=(\varphi_{L},\varphi_{R})$ be $\epsilon$, with $\epsilon<\frac{1}{2}$. Then the probability that the median of $\{\varphi^{\prime}_{k}\}$ falls out of $LR$ is bounded by $p_{fail}\leq\frac{1}{2}\left(2\sqrt{\epsilon(1-\epsilon)}\right)^{r}$.

The only way the median could fall out of the interval $LR$ is by having more than half of the datapoints $\varphi^{\prime}_{k}$ falling out of it. This probability is bounded by

where we used the fact that $\epsilon<\frac{1}{2}$, so that $\frac{\epsilon}{1-\epsilon}<1$ and $2\sqrt{\epsilon(1-\epsilon)}<1$. ∎

Recall that the precision (18) we demanded for $\varphi^{\prime}$ is such that when we get a phase smaller than $\frac{\varphi_{a}+\varphi_{b}}{2}$, we conclude that we have a ‘yes’ case. Lemma 1 tells us that for $\epsilon_{pe}=\frac{1}{16}$, the probability of our median scheme failing (producing a bad estimate of the phase) is bounded from above by

This gives us the first of the strong promise bounds (1), with

uses of the verifier circuit and its inverse. In the worst case (when the phases are hardest to tell apart), we have $a\approx b\approx\frac{1}{2}$, giving us $N^{\prime}=\frac{5\pi r}{2(a-b)}$. We can compare this to (2), where the actual value of the constant is $c=2$, and see that our method is better already for $a-b\leq\frac{1}{4}$. Of course, our motivation to start thinking about a new QMA amplification method was the case when $a-b$ is tiny.

For the ‘no’ case, the analysis is the same as above, if $\left|\psi\right\rangle\left|0\right\rangle$ (the witness combined with fresh ancillae) belongs to one of the two-dimensional invariant subspaces. The smallest median phase we can get corresponds to the largest possible acceptance probability, which is lower than $b$. The probability of obtaining a median of the $r$ the phase estimations below $\frac{\varphi_{a}+\varphi_{b}}{2}$ (i.e. Arthur being fooled) is again upper bounded by (24). On the other hand, what if we get a superposition $\sum_{i}v_{i}\left|v_{i}\right\rangle$ with $\left|v_{i}\right\rangle$’s from different two-dimensional invariant subspaces on the input? The final phase measurement on a superposition like $\sum_{i}v_{i}\left|v_{i}\right\rangle\left|\varphi_{i}\right\rangle$ gives us a classical mixture of results $\varphi_{i}$, weighted by $v_{i}^{2}$. Therefore, it’s always better for Merlin to choose a single $i$ with the smallest possible $\varphi_{i}^{(no)}$ if he wants to have a chance of fooling us. Nevertheless the probability to measure a phase smaller than $\frac{\varphi_{a}+\varphi_{b}}{2}$ in a ‘no’ case is upper bounded by $\epsilon_{pe}$ for any $\left|\alpha_{i}\right\rangle$. Recalling what we did above, several concatenated phase estimations allow us to detect that $\varphi^{\prime}>\frac{\varphi_{a}+\varphi_{b}}{2}$ with high probability. We then conclude that Merlin is just trying to fool us.

Is QMA with one-sided error equal to QMA?

Merlin knows all about our verifier circuit. This means he also knows the division of the Hilbert space corresponding to the two projectors $\Pi_{0}$ and $\Pi_{1}$ described in Section 2.1, and the bases $\{\left|v_{i}\right\rangle,|v_{i}^{\perp}\rangle\}$ of the two-dimensional invariant subspaces. Each of the vectors $\left|v_{i}\right\rangle=\left|\psi_{i}\right\rangle\left|0\right\rangle$ is a combination of the eigenvectors (15) of the product of two reflections $F_{1}F_{0}$ (9), with eigenvalues $e^{\pm i2\pi\varphi_{i}}$. Through (7) and (12), the phase $\varphi_{i}$ is related to the probability that the circuit $V$ accepts the witness $\left|\psi_{i}\right\rangle$. If Merlin sent us $\left|v_{i}\right\rangle$ and told us what the phase $\varphi_{i}$ is, we could verify his claim. However, the phase estimation circuit is not always perfect. Still, it works exactly, if the phase we are estimating has an $n$-bit binary expansion. Thus, we could do the following:

Merlin sends us the state $\left|\psi_{i}\right\rangle_{witness}\otimes\left|\varphi_{i}\right\rangle_{n}$, with $\left|\varphi_{i}\right\rangle_{n}$ an exact $n$-bit binary encoding of $\varphi_{i}$.

Measure $\left|\varphi_{i}\right\rangle_{n}$ in the $z$ basis, obtaining the number $\varphi_{i}$. Continue if $p_{i}=\cos^{2}(\pi\varphi_{i})\geq a$.

Run the fast QMA amplification scheme. When the witness is $\left|\psi_{i}\right\rangle$, the resulting phases we measure must all be equal to $\varphi_{i}$ or $-\varphi_{i}$, because the $n$-bit phase estimation should work perfectly for $\varphi_{i}$ with an exact $n$-bit binary expansion.

Only when the result agrees with the $\varphi_{i}$ which Merlin has sent, we are convinced that the answer to the yes/no question is ‘yes’.

For the ‘yes’ cases, the acceptance probability is exactly 1 when Merlin does everything right. On the other hand, if the answer is ‘no’, the acceptance probability of the QMA amplification scheme is already exponentially small, as shown in Section 2.3. This finishes the proof of our Theorem 2: for a special class of verifier circuits, ${\textsf{QMA}}_{\varphi}$ is equal to ${\textsf{QMA}}_{1}$.

Today, we do not know which circuits $V$ have the nice property described above. Nevertheless, there is a possibility that circuits without it can be (easily) slightly modified to have it. Merlin could send us a classical hint about the modification, and we would do it, keeping the properties of the circuit required in the definition of QMA. If this were possible, ${\textsf{QMA}}_{1}={\textsf{QMA}}$.

Preparing Witnesses for QMA

Given a verifier circuit $V$ for a problem in QMA, what could we do to actually prepare a witness which the circuit accepts? Poulin and Wocjan investigated this together with the problem of preparing ground states of local Hamiltonians. This question is not simple. The first idea would be to do a basic Grover search for the states in the support of the projector $\Pi_{1}$ (the states on which the circuit $V$ outputs $1$). However, this works only when $\Pi_{1}$ commutes with $\Pi_{0}$ (the projector on zeros on the ancillae). When $[\Pi_{1},\Pi_{0}]\neq 0$, the ancilla part of the states we get from Grover searching will very likely be nonzero, and the method does not produce a proper witness of the form $\left|\psi_{i}\right\rangle\left|0\right\rangle$. Poulin and Wocjan found a way for preparing the witness in general. First, they run the witness-preserving QMA amplification scheme of Marriott and Watrous (see Section 2.2) backwards, and then do Grover search for the part of the state with zero ancillae. We simplify their method, showing how to search for QMA witnesses using a reverse of our fast QMA amplification, in a much smaller system with easier initialization. This also unifies their approaches to ground state and QMA witness preparation.

Let us sketch the new filter state method. After the phase estimation (before the final Fourier transform) in our fast QMA amplification, we expect to have the state

in superposition with a corresponding $\left|\varphi_{i}^{-}\right\rangle_{1}$ part. The state $\left|f_{\varphi_{i}}\right\rangle$ is the filter state for phase $\varphi_{i}$. Imagine now that we ran the phase estimation backwards, starting in (26). We would obtain $\left|\varphi_{i}^{+}\right\rangle_{1}\left|0\right\rangle_{2}$. What would happen if we ran phase estimation backwards on

where $\left|\alpha\right\rangle$ is a random state and $\left|f_{\varphi_{i}}\right\rangle$ is the filter state? We would get

where the second register of $\left|\beta\right\rangle_{12}$ is nonzero. If we created the filter state $\left|f_{\varphi_{i}}\right\rangle$ with a large $n$, the coefficient $c_{\varphi_{i}}^{\perp}$ must be small (with high probability). The last step is then to amplify the coefficient $c_{\varphi_{i}}$ by amplitude amplification for the states with zeros on the second register – the phase estimation qubits. After we do this, we will obtain the state

with high probability, and from (15) we know that

With probability $\frac{1}{2}$, projecting on the zeros of the ancillae then gives us the witness $\left|\psi_{i}\right\rangle$. In practice, we would have to repeat this probabilistic method many times, scanning a range of $\varphi$’s and verifying (with our fast QMA amplification method) whether we actually got a witness.

The filter state $\left|f_{\varphi_{i}}\right\rangle$ in our scheme sketched above is the Fourier transform of $\left|\varphi_{i}\right\rangle$. In their first method for preparing ground states of many-body systems, Poulin and Wocjan use the same filter state, with the role of $\varphi_{i}$ played by the ground state energy. Scanning a range of energies plays the same role as scanning through a range of phases in the witness-preparation method. The analysis of the required number of phase estimation qubits $n$ to ensure that $c_{\varphi_{i}}^{\perp}$ is small, and the bounds on $c_{\varphi_{i}}$ thus works here as well. We point the interested reader to Appendix C of for the necessary details.

The original method for preparing witnesses in differs from the method for preparing ground states of many-body systems. It uses filter states representing measurements outputs of the Marriott-Watrous scheme corresponding to a certain acceptance probability. For the filter states to work (see Appendix D in ), they need to introduce an extra register containing a large number of ancillae, scaling as $N$ in (2). The final Grover search in this method is over the space of these ancillae.

By using the reverse of our QMA amplification scheme, we achieve two things. First, we unify the approaches to preparing ground states of many-body systems and QMA witnesses in , by using the same type of filter states. Second, comparing (25) and (2) shows that we now need only $N^{\prime}\propto~{}(a-b)N$ ancilla qubits. This greatly reduces the size of the final search space and speeds up the method. Nevertheless, its running time obviously still stays exponential in $n$, the size of the problem.

Discussion

First, we study the cost of amplifying the gap between the acceptance probabilities in the ‘yes’ and ‘no’ cases for the complexity class QMA. Let $L$ be an arbitrary language in QMA. Given a family $\{U_{n}\}$ of ${\textsf{QMA}}(a,b)$-circuits accepting $L$, we show how to construct a family $\{V_{n}\}$ of ${\textsf{QMA}}(1-2^{-r},2^{-r})$-circuits accepting $L$. Each of the circuits $V_{n}$ applies the original circuit $U_{n}$ or its inverse $U_{n}^{\dagger}$ at most $O\left(\frac{r}{a-b}\right)$ times. Thus, the complexity of our amplification method grows linearly in $\frac{1}{a-b}$. This improves upon the performance of the amplification method in whose complexity grows quadratically in $\frac{1}{a-b}$. This quadratic speed-up is reminiscent of the speed-up in Grover’s search algorithm and search algorithms employing quantum walks. This is not a coincidence. In fact, the intuition behind our amplification procedure is based on Szegedy’s quantization of classical Markov chains – quantum walks .

To explain this intuition, let us first look at quantum walks from a point of view than slightly different from the one usually taken in the literature. Roughly speaking, a quantum walk is derived from two projectors $P$ and $Q$ such that

the unique state $|\pi\rangle$ with $\|P|\pi\rangle\|^{2}=1$ and $\|Q|\pi\rangle\|^{2}=1$ is the desired quantum sample of the stationary distribution of the corresponding classical walk,

all the other states $|\varphi\rangle$ with the property $\left\|P\left|\varphi\right\rangle\right\|^{2}=1$ and orthogonal to $\left|\pi\right\rangle$ are necessarily contracted by $Q$, meaning that $\left\|Q\left|\varphi\right\rangle\right\|^{2}\leq 1-\delta$.

We can reduce this complexity with the help of the quantum walk $W=(2P-I)(2Q-I)$. The fact that $\left\|Q\left|\pi\right\rangle\right\|^{2}=1$ translates into the fact that $\left|\pi\right\rangle$ is the unique eigenvector of $W$ with eigenvalue $1$ (and corresponding phase ). Moreover, the fact that $\left\|Q\left|\varphi\right\rangle\right\|^{2}\leq 1-\delta$ translates into the fact that $\left|\varphi\right\rangle$ is necessarily a superposition of eigenvectors of $W$ whose phases have absolute value greater than some $\Delta$. This phase gap $\Delta$ is related to the eigenvalue gap $\delta$ by a quadratic relation: $\Delta\geq\sqrt{\delta}$. This leads to the quantum speed-up, because we can now distinguish between the two cases by running phase estimation. The required accuracy is $O(\Delta)$, and we can achieve this by invoking $W$ at most $O(\Delta^{-1})=O(\delta^{-1/2})$ times.

Our fast QMA amplification extends the quadratic relation between the probability and phase gaps to the more general situation, where the acceptance probability is at least $a$ in the ‘yes’ case and at most $b$ in the ‘no’ case. Recall that the situation relevant to quantum walks corresponds to $a=1$ and $b=1-\delta$. In the general case ($a\leq 1$), we prove that the phases $\varphi_{a}$ and $\varphi_{b}$ corresponding to the probability bounds $a$ and $b$ satisfy the separation bound $\varphi_{b}-\varphi_{a}=\Omega(a-b)$. By employing phase estimation, we can resolve these two cases by invoking $W$ at most $O\left(\frac{1}{a-b}\right)$ times.

Second, we study the complexity-theoretic question whether QMA is equal to ${\textsf{QMA}}_{1}$. Based on our new amplification procedure, we show that in some special cases (when the largest possible acceptance probabilities $a^{*}$ in the ‘yes’ cases satisfy a trigonometric identity), the acceptance probability in the ‘yes’ case can be amplified to $1$. The idea is that in these special cases the probabilities $a^{*}$ translate into ‘nice’ phases $\varphi_{a^{*}}$, which we can deterministically identify using phase estimation.

In the future, we plan to examine whether we could exploit the quadratic relation between the probability and phase gaps in more general situations to obtain new faster quantum algorithms. We will also seek to determine ways of proving that the acceptance probability can be boosted to $1$ in new, less restrictive cases.

Acknowledgments

D. N. gratefully acknowledges support by European Project QAP 2004-IST-FETPI-15848 and by the Slovak Research and Development Agency under the contract No. APVV-0673-07. P. W. gratefully acknowledges the support by NSF grants CCF-0726771 and CCF-0746600. Y. Z. was partially supported by the NSF-China Grant-10605035. Part of this work was done while D. N. was visiting University of Central Florida.

Appendix A A proof of Theorem 3 using Jordan’s lemma

Theorem 3 is an important result relevant to quantum walks, and it was proved by Szegedy in . We now prove it in a different way – using Jordan’s lemma. Jordan’s lemma has been recently used to analyze QMA amplification , and here we show that it is useful for quantum walks as well. For a short proof of Jordan’s lemma, see e.g. .

For any two Hermitian projectors $\Pi_{1}$ and $\Pi_{0}$, there exists an orthogonal decomposition of the Hilbert space into one dimensional and two dimensional subspaces that are invariant under both $\Pi_{1}$ and $\Pi_{0}$. Moreover, inside each two-dimensional subspace, $\Pi_{1}$ and $\Pi_{0}$ are rank-one projectors.

Consider now an $N$-dimensional Hilbert space $\mathcal{H}$, a rank $r$ projector $\Pi_{1}$ and a rank $s$ projector $\Pi_{0}$, with $1\leq r,s\leq N$. Jordan’s lemma implies the existence of an orthonormal basis for the Hilbert space $\mathcal{H}$ which can be divided into five groups.

Two-dimensional subspaces $S_{i}$ for $i=1,\dots,t$, invariant under both $\Pi_{1}$ and $\Pi_{0}$. Each subspace $S_{i}$ is spanned by the orthonormal eigenvectors $\left|v_{i}\right\rangle$ and $|v_{i}^{\perp}\rangle$ of the projector $\Pi_{1}$, i.e. obeying $\Pi_{1}\left|v_{i}\right\rangle=\left|v_{i}\right\rangle$ and $\Pi_{1}|v_{i}^{\perp}\rangle=0$.

Four types of one dimensional subspaces $T^{(bc)}_{i}$, where $b,c\in\{0,1\}$. These $N-2t$ subspaces are spanned by $|v^{(bc)}_{i}\rangle$, for $b,c\in\{0,1\}$, obeying

The 2D subspaces $S_{i}$ can be also spanned by the orthonormal eigenvectors $|w_{i}\rangle,|w_{i}^{\perp}\rangle$ of the projector $\Pi_{0}$, satisfying $\Pi_{0}|w_{i}\rangle=|w_{i}\rangle$ and $\Pi_{0}|w_{i}^{\perp}\rangle=0.$ Hence, we can recast the projectors $\Pi_{1}$ and $\Pi_{0}$ in the form

in terms of our chosen orthonormal basis of the Hilbert space $\mathcal{H}$.

We now rewrite Theorem 3 using the notation $\theta_{i}=\pi\varphi_{i}$, and provide a new proof based on Jordan’s lemma.

With a suitable choice of the orthonormal eigenvectors $\{|w_{i}\rangle,|w_{i}^{\perp}\rangle\}$ of the projector $\Pi_{0}$ and definingNote that in (6), we chose to use the rescaled $\varphi_{i}=\frac{\theta_{i}}{\pi}$ instead, to unify the notation with phase estimation. the principal angle $\theta_{i}$

References