format: text

text:
# Quantum NP - A Survey

## 1 Introduction

The field of complexity theory has witnessed several fundamental results in the recent decade or two; It is now a rich field involving deep questions and leading to the discovery of beautiful and unexpected structures, with important contributions to the understanding of the notion of classical probabilistic and deterministic computation. With the stormy entrance of quantum computation into the life of theoretical computer scientists, it seems only natural to ask whether such a rich theory of complexity can also be developed for the quantum model; it is probably true that such interesting structures and results await for us down the road of quantum complexity theory, with perhaps insights to be drawn from them regarding the quantum computational power. Several important results have already been discovered, and there are surely more to come. It is not unreasonable to also hope that quantum complexity can significantly contribute to the understanding of classical complexity in unexpected ways; A puzzling example in which quantum arguments are used in order to prove an entirely classical result in the area of locally decodable codes was recently found. We thus view the development of the field of quantum complexity as an important direction that holds the promise of a rich area of study with possible implications to the understanding of quantum algorithmic theory, as well as to classical complexity theory and to the foundations of quantum physics.

Perhaps the most basic and fundamental result in classical complexity theory, is the Cook-Levin theorem, which states that $`SAT`$, the problem of whether a Boolean formula is satisfiable or not, is $`NP`$ complete. This result opened the door to the study of the extremely expressive complexity class $`NP`$, and the rich theory of $`NP`$-completeness, and was an important building block in many later results in theoretical computer science and complexity theory, such as the PCP theorems, hardness of approximation results and the proof that $`IP=PSpace`$. In the heart of this result stands the very basic understanding that computation is local.

We devote this manuscript to the survey of a result by Kitaev, which is the quantum analog of the Cook-Levin Theorem. Kitaev first defines the quantum analog of $`NP`$, and then defines a complete problem which can be viewed as a generalization of $`SAT`$ to the quantum world. The proof follows the lines of the Cook-Levin proof, but defers from it in some fundamental points; We highlight those as we go along. The classical proof is quite simple; The quantum counterpart is rather complicated and long. However, there are several reasons to study this theorem, apart from the elegance of the proof, and from the naturalness of the question. First, there is a lot to be learned from the comparison of the classical proof and its (much more involved) quantum counterpart; Understanding the exact places where those differ is insightful. Secondly, the result raises a rich array of natural and interesting open problems related to this subject; We list those at the end of the survey, after the proof. Our proof follows closely the proof given by Kitaev, with minor deviations; Our main contribution here is adding explanations and clarifications, hopefully providing some intuition behind the proof, and highlighting some open problems. We hope that this survey will provide an easy access to Kitaev’s fundamental result and to the rich array of open questions it raises.

## 2 Definition of QMA

We would like to define a complexity class which will be the quantum analog of NP:

###### Definition 1

NP: $`LNP`$ if there exists a deterministic polynomial time verifier $`V`$ such that:

* $`xLy|y|=poly(|x|),V(x,y)=1.`$
* $`xLy|y|=poly(|x|),V(x,y)=0.`$

By $`|x|`$ we mean the number of bits in the binary string $`x`$. However, when trying to define the quantum analog, we immediately encounter an obstacle. We cannot require the verifier to answer $`0`$ or $`1`$ deterministically, because we will not be able to distinguish between this case and the case in which the verifier outputs these values with extremely high probability. Since the fact that states are continuous is inherent to quantum computation, we resort to defining QMA, the quantum analog of MA, which is the probabilistic version of NP.

Informally, MA can be thought of as a probabilistic analog of NP, allowing for two-sided errors.

###### Definition 2

MA: $`L𝒜`$ if there exists a probabilistic polynomial time verifier $`V`$ such that:

* $`xLy|y|=poly(|x|),Pr(V(x,y)=1)\frac{2}{3}`$
* $`xLy|y|=poly(|x|),Pr(V(x,y)=1)\frac{1}{3}`$

MA is naturally viewed as a game or interaction between 2 parties - Merlin, which has infinite computational power, and Arthur, which is limited to a polynomial time machine (the above $`V`$). Merlin should answer queries such as “is $`xL`$?”, and accompany the answer with a polynomial witness $`y`$ which Arthur can verify in polynomial time. Note that when showing that a problem is in MA, we should also show that Merlin cannot fool Arthur - i.e. that when $`xL`$ there is no witness $`y`$ that can persuade the verifier to believe that $`xL`$ with probability $`\frac{1}{3}`$.

We will define QMA analogously, where the verifier $`V`$ is a quantum machine, and the witness $`y`$ is a state of a polynomial number of qubits. We denote by $``$ the Hilbert space of one qubit.

###### Definition 3

QMA: $`L𝒬𝒜`$ if there exists a quantum polynomial time verifier $`V`$ and a polynomial $`p`$ such that:

* $`xL|\xi ^{p(|x|)},Pr(V(|x|\xi )=1)2/3`$
* $`xL|\xi ^{p(|x|)},Pr(V(|x|\xi )=1)1/3`$

Another possible definition would be to take $`|\alpha `$ as a classical witness, i.e. a basis state, but leave $`V`$ to be a quantum machine. We call this class Quantum Classical MA (QCMA).

###### Definition 4

QCMA: $`L`$ QCMA if there exists a quantum polynomial time verifier $`V`$ and a polynomial $`p`$ such that:

* $`xLy|y|=poly(|x|),Pr(V(|x|y)=1)2/3`$
* $`xLy,|y|=poly(|x|),Pr(V(|x|\alpha )=1)1/3`$

###### Claim 1

MA $``$ QCMA$``$QMA.

Proof: The left inclusion is trivial. The right inclusion follows from the fact that the quantum verifier can force Merlin to send him a classical witness by measuring the witness before applying on it the quantum algorithm.$`\mathrm{}`$

It is unclear whether the two classes, $`QCMA`$ and $`QMA`$ are the same; See open question 5 for further discussion. In any case, for the purposes of this paper, we will limit ourselves to the class QMA, where the witnesses are quantum.

### 2.1 Amplification

In all the above definitions of $`MA,QCMA`$ and $`QMA`$, we have used as our completeness parameter (i.e. one minus the error probability in case $`xL`$) the value $`2/3`$ and as our soundness parameter (the bound on error probability in case $`xL`$) the value $`1/3`$. We can denote this choice by MA$`(2/3,1/3)`$ or QMA$`(2/3,1/3)`$. In general, we can define the classes MA$`(c,s)`$ or QMA$`(c,s)`$ with general completeness and soundness parameters, which are functions of the input’s length. It turns out that we have a lot of freedom in the choice of these parameters, and we can make them either polynomially close to each other, or exponentially close to $`1`$ or $`0`$, without changing the complexity classes we are dealing with. In other words, amplification of the completeness and the soundness from polynomial separation to exponentially small error can be done in polynomial overhead. This is done using parallel repetition and taking the appropriate majority. More formally, for the case of the classical class $`MA`$:

###### Theorem 1

MA$`(c,c1/n^g)`$ MA$`(2/3,1/3)=`$MA$`(1e^{n^g},e^{n^g})`$ where we require $`g`$ to be a constant and $`0<c,c1/n^g<1`$.

Proof: If $`c`$ and $`s`$ are separated by some $`1/poly(n)`$, we run the verifier polynomially many times, say $`m`$, using independent random coins at each time. In case $`xL`$ the expected number of acceptances is at least $`cm`$, whereas in case $`xL`$ it is at most $`sm`$; The Chernoff bound111The Chernoff bound guarantees that the average of polynomially many repetitions of independent experiments will converge exponentially fast to the expected value guarantees that we can distinguish between the cases with only polynomially number of independent experiments with exponentially small error. This proves the inclusions $`𝒜(c,c1/n^g)𝒜(2/3,1/3)𝒜(1e^{n^g},e^{n^g})`$ where the other direction is trivial. $`\mathrm{}`$

Hence, we can conveniently move between the definition of MA with either one of these three possible choices of parameters.

###### Remark 1

The class MA as we defined it has two sided errors; In fact, this class is equivalent to MA with only one sided error, i.e. with completeness $`1`$ and soundness bounded away from $`1`$. It is unclear whether the same holds in the quantum case; See open question 4.

This nice freedom in the choice of parameters, due to the parallel repetition, holds also in the quantum case, however with a slightly more complicated proof.

###### Theorem 2

QMA$`(c,c1/n^g)`$ QMA$`(2/3,1/3)=`$QMA$`(1e^{n^g},e^{n^g})`$ where we require $`g`$ to be a constant, $`0<c,c1/n^g<1`$.

Proof: The proof of this theorem is slightly more subtle than the simple proof in the classical case. We will first prove that QMA$`(2/3,1/3)`$ is contained in QMA$`(1e^{n^g},e^{n^g})`$, i.e. that we can amplify soundness and completeness exponentially. The idea of remains the same as in the classical case: the verifier should perform polynomially many independent experiments and output the majority vote. However, unlike in the classical case, the verifier cannot perform many independent experiments on the same witness provided by the prover since after measuring it the witness will have changed; Neither can the verifier copy the quantum witness state before verifying it, due to the no cloning theorem which states that an unknown quantum state cannot be copied. The verifier thus needs to ask the prover to provide him with polynomially many copies of the witness. This is problematic, since the prover might try to cheat by entangling the witnesses he provides. We will have to show that such a strategy cannot help the prover in case $`x`$ is not in the language.

We construct a new verifier which runs in parallel polynomially many copies of the verifier $`V`$, then outputs the majority. The existence of a witness for the new verifier in case $`xL`$ is trivial since it is simply duplicate copies of the original witness. To prove soundness, one might suspect that entanglement between the provers can be used to bypass the fact that the error goes exponentially to $`0`$. To show this cannot happen, we treat the verifiers as if they are applied one after the other, and not in parallel. This is correct since the verifiers operate on different qubits and so they commute. We know that the probability that the first copy of $`V`$ outputs $`1`$ is less than $`1/3`$. After the first verifier was applied, we can apply the second verifier. The second verifier gets as an input some state, which can be conditioned on the result of the measurement of the first verifier. However, regardless of what this output was, it is still correct that the probability for an output $`1`$ is less than $`1/3`$. And so on for the remaining of the verifiers. Hence, the probability for the majority of the verifiers being $`1`$ can be bounded from above by the probability that polynomially many independent Bernoulli trials with bias $`1/3`$ will be $`1`$, which decays exponentially by Chernoff.

The idea of the inclusion QMA$`(c,c1/n^g)`$QMA$`(2/3,1/3)`$ is exactly the same, except that instead of majority vote among the polynomially many verifiers, we need to count the number of accepting verifiers, and accept only if this number is above $`(c+s)/2`$ times the number of experiments. The other inclusions are trivial. $`\mathrm{}`$

In the rest of the survey, we will interchange between the different choices of parameters according to our convenience.

### 2.2 Complexity

Before we continue, let us summarize what is known about these classes in terms of complexity. The most important class in quantum complexity theory is the class $`BQP`$, which consists of those problems which can be solved by a quantum machine with error probability bounded below half; This is considered as the class of tractable problems on a quantum computer. It is to be compared with the class $`BPP`$ which is the same class for classical computers. Of course, we have that $`BPPBQP`$, and that $`BQPQMA`$. But how powerful is the class $`QMA`$? Can we upperbound it? Adleman et. al. proved that $`BQP`$ is contained in a large class, called $`PP`$. A language $`L`$ is in $`PP`$ if there exists a Turing machine that runs in polynomial time on an input $`x`$, and such that if $`xL`$ it outputs $`1`$ with probability larger than $`1/2`$, and if $`xL`$ it outputs $`0`$ with probability larger than $`1/2`$. Note that the difference between the output probability and $`1/2`$ can be exponentially small. This makes the class possibly much stronger than the class $`BPP`$; In particular, $`PP`$ contains $`NP`$ (see  lecture $`7`$). It turns out that the above upper bound on $`BQP`$ can be generalized to prove the same inclusions for the class $`QMA`$, i.e. $`QMAPP`$. This fact was first noted by Kitaev and Watrous who build on a simplification of  by Fortnow and Rogers to prove it. To summarize we have that:

###### Theorem 3

$`BPPBQPQCMAQMAPP.`$

This is almost all that is known regarding the relation of $`BQP`$ and $`QMA`$ to classical complexity classes. To give intuition about what this upper bound means regarding the quantum complexity power, we note that the class $`PP`$ is known to be contained in perhaps a more natural class, $`PSPACE`$, which is the class of languages that can be recognized by a Turing machine that uses polynomial space (but can take exponential amount of time.)

We now proceed to define the complete problem for $`QMA`$: Local Hamiltonian.

## 3 The Local Hamiltonian Problem

In this section we will define what can be thought of as the quantum analog of $`3SAT`$, called the “local Hamiltonian problem”.

###### Definition 1

5-Local Hamiltonian problem

* Input: $`H_1,\mathrm{}H_r`$, A set of $`r`$ Hermitian positive semi definite matrices operating on the space of five qubits, $`^5`$, with bounded norm $`H_i1`$. Each matrix comes with a specification of the $`5`$ qubits (out of the total $`n`$ qubits) on which it operates. Each matrix entry is given with poly(n) many bits. Apart from $`H_i`$ we are also given two real numbers, $`a`$ and $`b`$ (again, with polynomially many bits) such that $`ba>1/poly(n)`$.
* Output: Is the smallest eigenvalue of $`H=H_1+H_2+\mathrm{}+H_r`$ smaller than $`a`$ or are all eigenvalues larger than $`b`$?

We slightly abuse notation here by writing $`H=H_1+H_2+\mathrm{}+H_r`$; $`H_i`$ are matrices operating on different qubits, and the summation is over their extension to the entire set of qubits (tensor product with identity). This abuse of notation will be used throughout the paper, and it will be clear that we mean the summation of the operators as operators on $`n`$ qubits.

Note that the defined problem is a promise problem: we are promised that one of the two possible outputs occurs. In other words, we don’t care what the output is for Hamiltonians with minimal eigenvalue between $`a`$ and $`b`$.

In the same way, one can naturally define the $`k`$-local Hamiltonian problem for any $`k`$. We will see that $`5`$-local Hamiltonian is QMA complete, and the reason for the number five will only be apparent towards the very end of the proof. However it is unclear whether it is necessary to consider $`5`$ local Hamiltonian or whether a smaller number suffices; See open question number 1 for further discussion.

### 3.1 Connection to $`3SAT`$

We now show that the local Hamiltonian problem is a natural generalization of $`3SAT`$ to the quantum world. For this, we explain how $`3SAT`$ can be viewed as a $`3`$-local Hamiltonian problem. We will work with qubits, but all operations are now classical operations in disguise. Let $`\varphi =C_1C_2\mathrm{}C_r`$ be a 3-SAT formula on $`n`$ variables, where each $`C_i`$ is a clause, i.e. an OR over three variables or their negations. For every clause $`C_i`$ we define a $`8\times 8`$ matrix $`H_i`$, operating on three qubits. $`H_i`$ is a projection on the unsatisfying assignment of $`C_i`$. For example, for the clause $`C_i=X_1X_2\neg X_3`$ we get the matrix:

$$H_i=\left(\begin{array}{cccccccc}0& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0\end{array}\right)=|001001|$$

since $`001`$ is the only unsatisfying assignment for $`C_i`$. $`H_i`$ defined this way is a projection matrix. Moreover, it is Hermitian. If we look at $`H_i`$, its eigenvectors are all basis vectors of three qubits, with the vectors corresponding to satisfying assignments having eigenvalues $`0`$, and the vector of the unsatisfying assignment corresponding to the eigenvalue $`1`$. We then consider the operation of $`H_i`$ on all the qubits, by taking tensor product of $`H_i`$ with identity on the rest of the qubits. We denote the new matrix by $`H_i`$ too, again by slight abuse of notation; It will be clear from context which of these we are talking about. If $`z`$ is an assignment to the $`n`$ variables which satisfies a clause $`C_i`$, then $`H_i|z=0`$. Otherwise, $`H_i|z=|z`$. We can view this as if the matrix $`H_i`$ “penalizes” assignments that do not satisfy $`C_i`$ by giving them one unit of “energy”. We denote $`H=_{i=1}^rH_i`$, and observe that $`H|z=q|z`$ where $`q`$ is the number of clauses unsatisfied by $`z`$. All eigenvalues of $`H`$ are non negative integers, and zero is an eigenvalue of $`H`$ if and only if $`H`$ corresponds to a satisfiable formula. Otherwise, the smallest eigenvalue of $`H`$ is at least $`1`$. Thus, $`3SAT`$ is equivalent to the following problem: “Is the smallest eigenvalue of $`H`$ $`0`$ or is it at least $`1`$?”, which is an instance of the $`3`$local Hamiltonian problem.

## 4 Local Hamiltonians is in QMA

###### Theorem 1

The $`k`$-Local Hamiltonian problem is in QMA for any $`k=O(log(n))`$.

Proof: We first want to show that if the Hamiltonian $`H`$ has an eigenvalue smaller than $`a`$, i.e. if we are in a “yes” instance, then there exists a witness that Marlin can use to convince Arthur for this fact. The obvious witness to use, is simply an eigenstate with eigenvalue smaller than $`a`$. Let us denote this ground state by $`|\eta `$ and its corresponding eigenvalue by $`\lambda `$. We will construct a procedure which outputs $`1`$ with probability which is related to this eigenvalue. To illustrate the idea, consider first the simpler case in which all the Hamiltonians $`H_i`$ are merely projections, $`H_i=|\alpha _i\alpha _i|`$. In this case, we note that

$$\lambda =\eta |H|\eta =\underset{i=1}{\overset{r}{}}\eta |H_i|\eta =\underset{i=1}{\overset{r}{}}\eta |\alpha _i\alpha _i|\eta =\underset{i=1}{\overset{r}{}}|\eta |\alpha _i|^2$$
(1)
or,

$$\lambda /r=(1/r)\underset{i=1}{\overset{r}{}}|\eta |\alpha _i|^2$$
(2)
We note that $`|\eta |\alpha _i|^2`$ is exactly the probability to get a positive answer when measuring the state $`|\eta `$ in the basis $`|\alpha _i`$ and the subspace orthogonal to it. Thus, equation 2 gives the following interpretation of $`\lambda /r`$: It is simply the probability to get the answer $`1`$ when we pick $`i`$ randomly between $`1`$ and $`r`$ and measure $`|\eta `$ in the basis $`|\alpha _i`$ and the subspace orthogonal to it. This implies an easy way to design an experiment, or a quantum verification procedure on the input state $`\eta `$, which outputs $`1`$ with probability $`1\lambda /r`$ and $`0`$ otherwise. Pick an $`i\{1,\mathrm{}r\}`$ uniformly at random, measure $`|\eta `$ in the basis $`|\alpha _i`$ and the orthogonal subspace, and output $`0`$ if the measurement resulted in a projection on $`|\alpha `$; output $`1`$ otherwise. The probability for $`1`$ is exactly $`1\lambda /r1a/r`$. On the other hand, if $`H`$ is a “no” instance, i.e. all eigenvalues are larger than $`b`$, then for any vector $`|\eta `$,

$$\eta |H|\eta =\underset{i=1}{\overset{r}{}}\eta |H_i|\eta b;$$
(3)
The probability for $`1`$ in the experiment is in this case

$$1\eta |H|\eta /r1b/r;$$
(4)
Since we know that $`ba1/n^g`$, we also have that the probabilities for $`1`$ for the “yes” and “no” instances are polynomially different: $`1a/r>1b/r+1/n^g`$. We can amplify this difference using the amplification theorem and this proves that the problem is indeed in QMA, if the Hamiltonians are simple projections.

We remark that since the projections are local, i.e. involve at most $`log(n)`$ qubits, such a measurement can be performed by a polynomial quantum verifier.

To deal with the more general case, where $`H_i`$ are general Hermitian positive semidefinite matrices with norm at most $`1`$, we note that any such matrix can be written in its spectral decomposition,

$$H_i=\underset{j=1}{\overset{dim(H_i)}{}}w_j^i|\alpha _j^i\alpha _j^i|$$
(5)
We now impose the following trick which enables us to toss a coin with probability $`1\eta |H_i|\eta `$. We first add one qubit to the system, in the state $`|0`$. We then apply the following unitary transformation on the qubits of $`H_i`$ and on the extra qubit:

$$T|\alpha _j^i|0=|\alpha _j^i(\sqrt{w_j^i}|0+\sqrt{1w_j^i}|1)$$
(6)
We now prove that the measurement of the extra qubit outputs $`1`$ with probability $`1\eta |H_i|\eta `$. To see this, write

$$|\eta =\underset{j}{}y_j|\alpha _j^i|\beta _j^i$$
(7)
using the Schmidt decomposition. After the transformation $`T`$, this state evolves to

$$T|\eta =\underset{j}{}y_j|\alpha _j^i|\beta _j^i(\sqrt{w_j^i}|0+\sqrt{1w_j^i}|1)$$
(8)
The probability to measure $`1`$ is then the squared norm of the following vector:

$$\underset{j}{}\sqrt{1w_j^i}y_j|\alpha _j^i|\beta _j^i.$$
(9)
This squared norm is just

$$\underset{j}{}(1w_j^i)|y_j|^2=1\underset{j}{}w_j^i|y_j|^2$$
(10)
but we know that

$$\eta |H_i|\eta =\underset{j}{}w_j^i|y_j|^2.$$
(11)
We can now describe the exact verification procedure: Pick a random index $`i`$, and perform the above test for $`H_i`$: Add one qubit, apply $`T`$ and measure the extra qubit. The outcome will be $`1`$ with probability

$$\underset{i}{}(1/r)(1\eta |H_i|\eta )=1\eta |H|\eta /r$$
(12)
If we are in a “yes” instance, this number will be larger than $`1a/r`$; If we are in a “no” instance, it will be smaller than $`1b/r`$, and the proof is completed just as in the simple projections case. $`\mathrm{}`$

## 5 QMA Completeness

In this section we will show that the $`5`$-local Hamiltonian problem is QMA-hard. The proof is complicated, and we will start with an overview.

### 5.1 Reminder of the Cook-Levin Proof

The proof that local Hamiltonian is QMA complete bears a lot of resemblance to Cook-Levin’s proof that 3SAT is NP-Complete. Let us briefly sketch the idea underlying the Cook-Levin’s proof, so that we can refer to it later on. Consider an NP problem, $`L`$. There is a Turing machine which operates on $`x,y`$ where $`x`$ is a supposedly member of $`L`$ and $`y`$ is a supposed witness for this fact, and $`M`$ checks that $`x`$ is in the language using $`y`$. We now want to construct a reduction to $`3SAT`$, i.e. to design a Boolean formula which is satisfiable if and only if $`x`$ is in the language, i.e. if the Turing machine performed a successful computation which started with the input and ended with “accept” or $`1`$, in the first site on the tape. To construct such a formula, we consider the variables $`x_{i,t}`$ where $`i`$ runs over all reachable locations on the tape in the polynomial time limit and $`t`$ runs over the time steps. $`x_{i,t}`$ are variables which can get any of some constant number of possible values; These values correspond to a finite description of the state of the Turing machine related to the location $`i`$ on the tape at time $`t`$. They include what is written on the tape at that time and that location, the state of the Turing machine at that time, and whether the head of the Turing machine is at that location or not. An assignment to these variables can be viewed as a history of some computation; a description of how the Turing machine evolved in time. The 3-SAT formula we construct is essentially checking that this evolution is a valid evolution of the Turing machine. Each clause in the formula will look at three subsequent cells at some time $`t`$, say $`x_{i1,t},x_{i,t}`$ and $`x_{i+1,t}`$ plus the cell $`x_{i,t+1}`$. Given the values of $`x_{i1,t},x_{i,t}`$ and $`x_{i+1,t}`$, it is possible to know whether the value of $`x_{i,t+1}`$ is valid or not; Thus, the clause is satisfied if and only if $`x_{i,t+1}`$ evolves from $`x_{i1,t},x_{i,t}`$ and $`x_{i+1,t}`$ by a valid computation. We also add clauses that check that the input is really $`x`$, i.e. clauses of the form $`x_{i,0}`$ if the $`i^{}th`$ input bit was $`1`$, and $`\neg x_{i,0}`$ if the $`i^{}th`$ input bit was $`0`$. Finally, we check that the output is accept by adding the clause $`x_{1,T}`$, which is satisfied if the first site is $`1`$ at the end of the computation at time $`T`$. Each of these verifications is local, since the evolution of the Turing machine is local, and thus each corresponds to a clause. Note that our variables have a constant but possibly large set of possible values; It is easy to see that such formulas can be converted to formulas over Boolean variables, and that each clause can be converted to many clauses each operating only on three variables. All these details are none of our concern; The main issue, which we will try to mimic in the quantum case, is that the history of a Turing machine can be verified locally.

### 5.2 The Quantum analog- Sketch

The idea of the quantum proof is very similar. We know that $`L`$ is in $`QMA`$; Thus, there exists a quantum circuit, using two-qubit gates, which accepts an input $`x`$ with some witness $`|\xi `$ with high probability (we will assume it is exponentially close to $`1`$) if $`x`$ is in $`L`$ and rejects with exponentially close to one probability if $`xL`$ given any witness. We want to reduce this problem to the local Hamiltonian problem, i.e. to construct a Hamiltonian which will have small eigenvalue in the $`xL`$ case and only large eigenvalues otherwise.

How to construct the analog? Drawing from the Cook-Levin proof, we want the history of the computation to be our witness, which we hope to be able to verify locally. Our first guess for the quantum witness would thus be the sequence of states which constitute the history of the computation:

$$|x|\xi ,U_1|x|\xi ,U_2U_1|x|\xi ,\mathrm{},U_T\mathrm{}U_2U_1|x|\xi .$$
(13)
However, there is a serious problem with this suggestion. Let us assume for a moment that $`U_1`$ is simply the identity gate, and all we want to check is whether the first and second states given to us by the prover are the same, and we want to do this via a local Hamiltonian. In general, we want to design a local Hamiltonian which when applied on $`|\alpha |\alpha `$ it behaves differently than when applied on $`|\alpha |\beta `$, if $`|\beta `$ is quite different from $`|\alpha `$. The problem is that a local Hamiltonian has access only to the reduced density matrix of the state $`|\alpha |\beta `$ to five qubits at a time. In other words, $`\eta |H|\eta `$ for any state $`|\eta `$ will be exactly the same if we move to $`|\eta ^{}`$ as long as it has the same reduced density matrices as $`|\eta `$ on all sets of five qubits. It is very easy to construct two states which agree on all density matrices of five qubits, but are completely different due to their overall correlations or entanglement. Hence, using only local Hamiltonians we cannot hope to be able to verify the correctness of the time evolution if the states are given to us sequentially. However, entanglement which was the source of this problem, can also help us solve it. Consider the following superposition

$$\frac{1}{\sqrt{2}}(|0|\alpha +|1|\beta )$$
(14)
From the reduced density matrix of just the first qubit, we can learn a lot about whether the states $`|\alpha `$ and $`|\beta `$ are the same or different; in fact, the reduced density matrix of the first qubit tells us the angle between these two states, as one can easily verify. This means that if the histories are given to us in superposition, there is hope that local measurements or observables like our local Hamiltonian will be able to verify the correctness of the time evolution.

The idea is therefore to ask the prover for the history of the computation, not in the form of sequential states but rather in a superposition over all time leafs:

$$|\eta =\frac{1}{\sqrt{T+1}}\underset{t=0}{\overset{T}{}}U_t\mathrm{}.U_1|x,\xi |t$$
(15)
we will see later how this state can actually be verified for correctness. In the book this idea of moving from time evolution to a time-independent local Hamiltonian is attributed to Feynman.

Except for this main difference of using superposition over time instead of sequential time, there is another essential difference in the proof. In the classical case the eigenvalues are integers, and so to show soundness one only has to show that the resulting formula is not satisfiable if $`x`$ is not in the language. The corresponding statement would be that the smallest eigenvalue of $`H`$ is not $`0`$; In the classical case, this automatically means that it is at least $`1`$. In the quantum case, due to the continuous nature of the model, the fact that the smallest eigenvalue is larger than $`0`$ is not enough; One actually has to show that it is at least polynomially bounded away from zero, because the accuracy achieved by the verification process is only polynomial, i.e. we can only amplify a polynomial separation and not an exponentially small separation. To bound the lowest eigenvalue from below Kitaev uses a geometrical argument, augmented with some nice ideas of how to perform the analysis involving the known theory of random walks on the line, represented here by the time axis.

### 5.3 The reduction

Let $`L`$ be a problem in QMA. Then there exists a quantum circuit $`Q`$ with two-qubit gates $`U_1,\mathrm{},U_T`$ such that for an input $`|x`$ and a witness $`|\xi `$ the output qubit has more than $`1e^n`$ probability to collapse on $`|1`$ if $`xL`$ and less than $`e^n`$ probability to collapse the first qubit on $`|0`$ otherwise. Given this sequence of gates, we will construct an input to the local Hamiltonian problem, i.e. a sequence of local matrices. For now, our matrices will not be completely local, but instead will operate on two qubits among the $`n`$ computer qubits plus an extra $`T+1`$ dimensional Hilbert space, which will serve as a clock, and which is augmented to the right of all the other qubits. We will modify the Hamiltonian later on so it is truly $`5`$-local, but for the sake of simplicity we present the main part of the proof using this extra $`T+1`$ dimensional Hilbert space. We denote by the subscript $`C`$ the subspace of the clock. The subscript $`i`$ at the foot of operators means that they operate on qubit number $`i`$; The projection operator $`\mathrm{\Pi }^{|\alpha }`$ means project on the subspace spanned by $`|\alpha `$. Our Hamiltonian will be a sum of three main terms, $`H=H_{in}+H_{out}+H_{prop}`$.

* $`H_{in}`$ is a matrix that checks that the input for the first $`n`$ qubits is indeed $`x`$, where we do not care about the witness; It can be anything. This check need to verify that the $`i`$th bit is indeed $`x_i`$, at time $`0`$, for all $`i`$ between $`1`$ to $`n`$. This is done by projecting the state to time $`0`$ (by projecting the clock state to time $`0`$), and then projecting the remaining state to the space orthogonal to $`|x_i`$:

$$H_{in}=\underset{i=1}{\overset{n}{}}\mathrm{\Pi }_i^{|\neg x_i}|00|_C$$
(16)
* $`H_{out}`$ is a matrix that checks that the output is $`1`$ at time $`T`$, again, by first projecting the clock to time $`T`$ and then projecting the state to the subspace orthogonal to $`|1`$ on the first qubit which carries the answer of the quantum circuit:

$$H_{out}=\mathrm{\Pi }_1^{|0}|TT|_C$$
(17)
* $`H_{prop}`$ checks that the propagation of the computational process is done according to the given circuit. It is a sum of $`T`$ terms,

$$H_{prop}=\underset{t=1}{\overset{T}{}}H_{prop}(t)$$
(18)
where each term checks that the propagation from time $`t1`$ to $`t`$ is correct:

$$H_{prop}(t)=\frac{1}{2}(I|tt|+I|t1t1|U_t|tt1|U_t^{}|t1t|)$$
(19)

During the proof of the completeness part, it will become clear why each of these terms really verifies what we claim it does. Note that each term in the above Hamiltonian indeed satisfies our constraints of being Hermitian, positive semi-definite and of norm at most $`1`$; There is one problem, which is that it is only $`log`$-local and not local, since it operates on two qubits among the main qubits plus the clock space (which can be represented by logarithmically many qubits, which is the reason why we call it $`log`$-local.) We will fix this problem only much later and for now we work with the Hamiltonian $`H`$ as defined. To complete the reduction we also need to specify $`a`$ and $`b`$; We let $`a=1/T^{10}`$, and $`b=1/4(T+1)^3`$.

The claim is that the constructed Hamiltonian has an eigenvalue less than $`a`$ if $`x`$ is in the language that the quantum circuit accepts, and otherwise all the eigenvalues of the Hamiltonian are larger than $`b`$. Once we prove both claims (completeness and soundness) we will be done; The two together imply that solving the local Hamiltonian problem for the Hamiltonian that is associated with a certain circuit, is a way to decide the answer of the circuit, (i.e. solving the Hamiltonian problem is QMA hard: any QMA problem can be solved using a machine that solves the local Hamiltonian problem.) It will remain only to deal with the locality problem which we will do at the very end.

### 5.4 Completeness

To prove completeness, we want to show that a “yes” instance of the QMA problem transforms to a “yes” instance in the Local Hamiltonian problem. If $`xL`$, the $`H`$ we constructed has an eigenvalue smaller than $`a`$. For this, it suffices to prove the following claim:

###### Claim 2

If $`x`$ is accepted by the circuit $`Q`$, for some quantum witness $`|\xi `$, with probability which is larger than $`1ϵ`$, then the Hamiltonian $`H=H_{in}+H_{prop}+H_{out}`$ constructed above given $`x`$ and the circuit $`Q`$ has an eigenvector with eigenvalue $`ϵ`$.

Proof: To see why the claim is true, in analogy with the classical case, the state we will use is the history of the computation

$$|\eta =\frac{1}{\sqrt{T+1}}\underset{t=0}{\overset{T}{}}U_tU_{t1}\mathrm{}U_1|\gamma _0|t$$
(20)
where $`|\gamma _0`$ is the state at the beginning of the computation (a tensor product of the input and the witness to the machine) and $`|t`$ is a clock state.

The intuition is that this state is “almost” a zero eigenstate of the Hamiltonian $`H`$, since is “almost” satisfies all the tests this local Hamiltonian checks. More formally, we claim that

$$\eta |H|\eta ϵ.$$
(21)
which suffices to prove the claim.

To calculate $`\eta |H|\eta `$ we first note that

$$H_{in}|\eta =0.$$
(22)
It is less obvious but can be easily checked that for each $`t=1,\mathrm{}T`$

$$H_{prop}(t)|\eta =0.$$
(23)
The reader is recommended to verify this step, since it explains the definition of the propagation Hamiltonian, which is one of the main conceptual steps in the proof. The intuition is that the propagation Hamiltonian is composed of four parts, all confined to the projections on the span of the two time leafs $`|t1`$ and $`|t`$. Two terms in the Hamiltonian $`H_{prop}(t)`$, $`I|tt|+I|t1t1|`$ correspond simply to picking out the state at those times. In addition, there are two extra terms: the term, $`U_t|tt1|`$ which corresponds to a forward propagation in time, and a term $`U_t^{}|t1t|`$ which corresponds to backwards propagation in time; When applied on the projection of the state to the two time steps $`|t1`$ and $`|t`$, the forward propagation in time term picks just the $`t1`$ time step and propagates it forward by applying $`U_t`$ to it, and then the resulting state gets canceled with the $`t`$ time step; The same happens with the backwards propagation term which picks up the time step $`t`$, propagates it one step backwards by applying $`U_t^{}`$ and then this term gets canceled with it. with the $`t1`$ time step.

It is left to check what happens to $`|\eta `$ when we apply $`H_{out}`$. When we apply $`H_{out}`$ on $`|\eta `$ we get a projection on the part of $`|\eta `$ which rejects. Since the probability for rejection is $`ϵ`$, we get that the norm squared of $`H_{out}|\eta `$ is at most $`ϵ`$, and hence $`\eta |H_{out}|\eta =H_{out}|\eta ^2ϵ.`$ Hence, the minimal eigenvalue of $`H`$ is less than $`ϵ`$. $`\mathrm{}`$

### 5.5 Soundness

To complete the reduction, we need to show that if $`xL`$, the minimal eigenvalue of $`H`$ is larger than the chosen $`b`$.

###### Theorem 2

If $`xL`$ then the minimal eigenvalue of $`H`$ is $`\frac{1}{4(T+1)^3}`$.

Proof: To prove this theorem we will put together several lemmas. The idea is to write $`H`$ as a sum of two Hamiltonians, $`H_1=H_{in}+H_{out},H_2=H_{prop}`$, and to use the following geometrical lemma, which gives a lower bound on the lowest eigenvalue of a sum of two Hamiltonians, given some conditions on the eigenvalues and eigenspaces of the two Hamiltonians.

###### Lemma 1

Let $`H_1`$ and $`H_2`$ be two Hermitian positive semi-definite matrices, and let $`N_1`$ and $`N_2`$ be the eigenspaces of the eigenvalue $`0`$, respectively. If the angle between $`N_1`$ and $`N_2`$ is some $`\theta >0`$, and the second eigenvalue of both $`H_1`$ and $`H_2`$ is $`\lambda `$ then the minimal eigenvalue of $`H_1+H_2\lambda \mathrm{sin}^2(\theta /2)`$.

Proof: Consider an eigenvector of $`H_1+H_2`$, $`|\delta `$ such that $`|\delta =1`$. For at least one of the subspaces $`N_1`$ or $`N_2`$ The angle between $`|\delta `$ and this subspace is at least $`\frac{\theta }{2}`$. W.L.O.G let this subspace be $`N_1`$. We have

$$\delta |(H_1+H_2)|\delta =\delta |H_1|\delta +\delta |H_2|\delta \delta |H_1|\delta .$$

We write

$$|\delta =|\mu +|\mu ^{}$$

where $`|\mu ,|\mu ^{}`$ are the projections of $`|\delta `$ onto $`N_1`$ and the orthogonal subspace to $`N_1`$ respectively. Then

$$\delta |H_1|\delta =\mu ^{}|H_1|\mu ^{}\mu ^{}^2\lambda $$

where the first equality follows from the fact that $`N_1`$ and and its complement are invariant to the application of $`H_1`$ and the second follows from the definition of $`H_1`$ and $`\lambda `$. We also know that $`\mu ^{}^2sin^2(\theta /2)`$ because the angle between $`N_1`$ and $`|\delta `$ is at least $`\theta /2`$, and this completes the proof. $`\mathrm{}`$

To use the geometrical lemma, we will assume $`xL`$ and give lower bounds on the second eigenvalues of $`H_1`$ and $`H_2`$, as well as a lower bound on $`\theta `$. We will first bound the second eigenvalues of $`H_1`$ and $`H_2`$.

###### Lemma 2

The second eigenvalue of $`H_1`$ is at least $`1`$.

Proof: The second eigenvalue of $`H_1`$ is $`1`$ since $`H_{in}`$ and $`H_{out}`$ are projections and hence their eigenvalues are $`0`$ and $`1`$. Since the eigenspaces of the eigenvalue $`1`$ of $`H_{in}`$ and $`H_{out}`$ are orthogonal (because they operate on different times), they commute, and so their second eigenvalue is simply the minimal second eigenvalue of the two. $`\mathrm{}`$

###### Lemma 3

The second eigenvalue of $`H_2=H_{prop}`$ is at least $`\frac{1}{2(T+1)^2}`$.

Proof: It turns out that for this and further arguments it is simpler to look at $`H_{prop}`$ in a rotated basis. The eigenvalues of a matrix are not changed when looked at in a different basis. Hence we define the unitary matrix $`R`$ as follows:

$$R=\underset{t=0}{\overset{T}{}}U_t\mathrm{}U_1|tt|.$$
(24)
$`R`$ is unitary since it is a block diagonal matrix with each of its blocks unitary. What $`R`$ does is basically rotate the basis in each time leaf to the basis which one gets if one applies the first $`t`$ computation steps on the computational basis. Hence, in the new rotated basis, the computation is simply the identity. Now, it is easy to check that

$$R^{}H_{prop}(t)R=\frac{1}{2}(I|tt|+I|t1t1|I|t1t|I|t1t|)$$
(25)
We can write $`H_{prop}=IA`$ where $`A`$ is a $`(T+1)\times (T+1)`$ of the form:

$$A=\left(\begin{array}{cccccccc}\frac{1}{2}& \frac{1}{2}& 0& 0& 0& 0& 0& 0\\ \frac{1}{2}& 1& \frac{1}{2}& 0& 0& 0& 0& 0\\ 0& \frac{1}{2}& 1& \frac{1}{2}& 0& 0& 0& 0\\ 0& 0& \frac{1}{2}& 1& \frac{1}{2}& 0& 0& 0\\ 0& 0& 0& \frac{1}{2}& 1& \frac{1}{2}& 0& 0\\ 0& 0& 0& 0& \frac{1}{2}& 1& \frac{1}{2}& 0\\ 0& 0& 0& 0& 0& \frac{1}{2}& 1& \frac{1}{2}\\ 0& 0& 0& 0& 0& 0& \frac{1}{2}& \frac{1}{2}\end{array}\right)$$

$$=I\left(\begin{array}{cccccccc}\frac{1}{2}& \frac{1}{2}& 0& 0& 0& 0& 0& 0\\ \frac{1}{2}& 0& \frac{1}{2}& 0& 0& 0& 0& 0\\ 0& \frac{1}{2}& 0& \frac{1}{2}& 0& 0& 0& 0\\ 0& 0& \frac{1}{2}& 0& \frac{1}{2}& 0& 0& 0\\ 0& 0& 0& \frac{1}{2}& 0& \frac{1}{2}& 0& 0\\ 0& 0& 0& 0& \frac{1}{2}& 0& \frac{1}{2}& 0\\ 0& 0& 0& 0& 0& \frac{1}{2}& 0& \frac{1}{2}\\ 0& 0& 0& 0& 0& 0& \frac{1}{2}& \frac{1}{2}\end{array}\right)=IB$$

The eigenvalues of $`R^{}H_{prop}R`$ or equivalently of $`H_{prop}`$ are simply the eigenvalues of $`A`$ (with multiple appearances), or $`1`$ minus those of $`B`$; It suffices then to find the eigenvalues of $`B`$.

Interestingly, the matrix $`B`$ is a familiar matrix from the theory of random walks and we will use this fact in the analysis of its eigenvalues. For a direct proof see Kiteav. Here we refer to the theory of random walks due to its intriguing connection with the subject at hand. For a nice exposition of random walks, see Lovasz’s survey. Returning to our matrix $`B`$, it turns out that it is the stochastic matrix corresponding to a simple random walk on the time axis, from $`0`$ to $`T`$. with a loop at both ends. The largest eigenvalue of this matrix is $`1`$, corresponding to the eigenvector which is the uniform limiting distribution. This eigenvalue gives the $`0`$ eigenvalue of $`A`$ and hence of $`H_{prop}`$. In random walk theory, one is very interested in the second eigenvalue of the stochastic matrices corresponding to random walks since the second eigenvalue is directly related to the rate at which the random walk mixes to its limiting distribution. $`B`$’s second largest eigenvalue $`\lambda _2`$ is bounded from below by the conductance $`\varphi `$ of the graph on which the random walk is applied, using Jerrum and Sinclair’s bound:

$$1\lambda _2\varphi ^2/2$$
(26)
The conductance of the random walk is $`\frac{1}{T+1}`$ which gives $`1\lambda _2\frac{1}{2(T+1)^2}.`$ Since $`1`$ minus the second largest eigenvalue of $`B`$ is exactly the second smallest eigenvalue of $`A`$, this implies the desired result. $`\mathrm{}`$

It is left to give a lower bound on the angle between the two null spaces.

###### Lemma 4

The angle between $`N_1`$ and $`N_2`$ satisfies $`sin^2(\theta /2)\frac{1}{2(T+1)}`$.

Proof: $`H_1=H_{in}+H_{out}`$ is a projection, and hence the null space is simply the subspace orthogonal to the space on which $`H_1`$ projects. Hence, $`N_1`$ is equal to the direct sum of three subspaces:

$$N_1=(|xx|W|00|)(|11|W|TT|)_{t=1}^{T1}(W|tt|)$$
(27)
where $`W`$ is the entire Hilbert space for the remaining of the qubits. $`N_2`$, the null space of $`H_{prop}`$, is exactly the space spanned by all valid computations starting with an arbitrary state $`|\alpha `$ on the qubits of the input and witness together. These are all states of the form:

$$|\eta =\frac{1}{\sqrt{T+1}}\underset{t=0}{\overset{T}{}}U_t\mathrm{}U_1|\alpha |t.$$
(28)
The fact that such states are in the null space of $`H_{prop}`$ was shown before; The fact that all states in the null space of $`H_{prop}`$ are of this form follows from looking at the rotated $`R^{}H_{prop}R`$, as before. The null space of the rotated $`H_{prop}`$ is simply the entire space on the computer register times the null space of the clock matrix $`A`$; The null space of the matrix $`A`$ is exactly all constant vectors. This is a standard claim, following from the fact that the random walk $`B`$ defines on the line is aperiodic, ergodic, and converges to the uniform vector. (One can readily prove this fact also from scratch, by considering the effect of $`A`$ on the eigenvector corresponding to eigenvalue $`1`$, and looking at the maximal coordinate.)

Now, to find $`N_2`$, the null space of $`H_{prop}`$, we have to rotate the null space of $`RH_{prop}R^{}`$ (which is all the Hilbert space on the computer qubits times constant vectors on the clock space) back to the original basis, by applying $`R`$ and $`R^{}`$ from both sides. It is easy to see that for any state

$$|\alpha \frac{1}{\sqrt{T+1}}\underset{t=0}{\overset{T}{}}|t$$
(29)
rotating it back gives a state of the form of equation 28.

We now want to bound the angle between $`N_1`$ and $`N_2`$, which is the minimal angle between two vectors from both spaces. Any vector in $`N_2`$ is of the form of equation 28, i.e. a history of a certain computation, and the angle $`\varphi `$ between such a history $`|\eta `$ and $`N_1`$ is given by

$$cos^2(\varphi )=\mathrm{\Pi }_{N_1}|\eta ^2$$
(30)
where $`\mathrm{\Pi }_{N_1}`$ denotes the projection onto $`N_1`$. This is true since $`|\eta `$ is of norm $`1`$. Thus we have that the angle $`\theta `$ between $`N_1`$ and $`N_2`$ is the minimal angle $`\varphi `$ between a history vector and the space $`N_1`$, or equivalently:

$$cos^2(\theta )=max_{|\eta N_2}\{\mathrm{\Pi }_{N_1}|\eta ^2\}$$
(31)
We now claim that for any $`|\eta N_2`$ we have:

$$\mathrm{\Pi }_{N_1}|\eta ^21\frac{1}{2(T+1)}.$$
(32)
The proof of this will complete the proof of the lemma, using equation 31. To prove the upper bound of equation 32, we observe that the norm squared of the projection onto $`N_1`$ is simply the sum of the norms squared on the projections on the different parts of $`N_1`$, as a direct sum of subspaces. If we write $`N_1`$ as a direct sum of the different spaces spanned by times $`t=1,\mathrm{},T1`$, then since $`|\eta `$ is the uniform superposition over time, the projection of $`|\eta `$ on each of the middle time step gives $`\frac{1}{T+1}`$, and so the total contribution of the middle time leafs is $`\frac{T1}{T+1}`$.

We now claim that the contribution of the first and last leafs together is far from the maximal possible contribution $`\frac{2}{T+1}`$. Intuitively, this is due to the fact that the projection on $`N_1`$ sums up the projection on $`x`$ as input in the beginning of the computation plus the projection on “accept” at the end of the computation. However, since $`|\eta `$ represents a valid computation by a circuit that does not accept $`x`$, it cannot be the case that both projections are maximal. To quantify this statement, we observe that we can write $`|\eta `$ as a sum of two states:

$$|\eta =\frac{1}{\sqrt{T+1}}\underset{t=0}{\overset{T}{}}|\gamma _t|t=\frac{1}{\sqrt{T+1}}\underset{t=0}{\overset{T}{}}(a|\gamma _t^1+b|\gamma _t^2)|t=a|\eta _1+b|\eta _2$$
(33)
where $`|\gamma _0^1`$ is the normalized projection of $`|\gamma _0`$ on the input being $`x`$, and $`|\gamma _0^2`$ is the normalized projection on the orthogonal subspace, and $`|\gamma _t^1`$,$`|\gamma _t^2`$ are simply the states obtained from the initial states by applying the computation. The norm sqaured of the projection of the first time leaf of $`|\eta `$, $`\frac{1}{\sqrt{T+1}}|\gamma _0|0`$, onto $`N_1`$ is $`\frac{a^2}{T+1}`$. The norm squared of the projection of the last time leaf of $`|\eta `$, $`\frac{1}{\sqrt{T+1}}|\gamma _0|T`$, onto $`N_1`$ is the norm squared of

$$\frac{1}{\sqrt{T+1}}(a|\delta _T^1+b|\delta _T^2)$$
(34)
where $`|\delta _T^1,|\delta _T^2`$ are the projections of $`|\gamma _T^1,|\gamma _T^2`$ on “accept”, respectively (we are using the linearity of projection.) Now we have that

$$|\delta _T^1^2e^n$$
(35)
since the circuit accepts with probability less than $`e^n`$ if $`x`$ is not in the language. Hence,

$$a|\delta _T^1+b|\delta _T^22e^n+b^2$$
(36)
and so the total norm squared of the projection on $`N_1`$ is at most

$$\mathrm{\Pi }_{N_1}|\eta ^2\frac{1}{T+1}(a^2+2e^n+b^2)+\frac{T1}{T+1}(1\frac{1}{2(T+1)})$$
(37)
using the fact that $`a^2+b^2=1`$. This completes the proof.$`\mathrm{}`$

To complete the proof of the theorem 2, we simply apply the geometrical lemma 1 using the bounds we have shown for the eigenvalues and for $`\theta `$. $`\mathrm{}`$

This completes the proof of the hardness of Local Hamiltonian for QMA, if we are allowed to use Hamiltonians which operate on spaces of polynomial dimension; In the next section we make the last step that is needed to convert the Hamiltonian to a $`5`$-local Hamiltonian consisting of terms operating on five qubits only.

## 6 Improving from $`log`$ local to $`5`$local

To move from operators on the entire clock to local operators, represent the time in unary representation on $`T`$ qubits which will serve as the clock qubits. For example, time $`t=4`$ is represented by the $`T`$ qubit state $`|111100\mathrm{}00.`$ To modify the Hamiltonian accordingly, we replace all operators on the clock space by operators that operate on three qubits at most. We apply the following modifications:

$`|tt1||110100|I`$ (38)
$`|t1t||100110|I`$
$`|tt||110110|I`$
$`|t1t1||100100|I`$
where in all these cases $`|110100|`$ or the similar terms operate on qubits $`t1,t,t+1`$ of the clock qubits and the identity $`I`$ operates on the remaining $`T2`$ clock qubits. This will hold in all terms of $`H_{prop}`$, except for two exceptions to the above - when $`t=1`$ and $`t=T`$, in order not to refer to bits $`0`$ and $`T+1`$ of the clock which do not exist. For $`t=1`$ we will drop the first bit of the 3-bit operator, so the operator $`|10|`$ on the original clock becomes $`|1000|`$ on the first two bits; and similarly $`|01|`$ on the original clock becomes $`|0010|`$ on the first two bits in the unary clock. For the case $`t=T`$ we drop the $`3^{rd}`$ bit of the operators in the same manner. The final $`H_{prop}`$ which we get is

$$H_{prop}^{}(t)=\frac{1}{2}(I|110110|+I|100100|U_t|110100|U_t^{}|100110|)$$
(39)
where the three qubit operators operate on qubits $`t1,t,t+1`$. For $`H_{prop}^{}(1)`$, $`H_{prop}^{}(T)`$ we get a slightly different expression with the clock operators operating only on two qubits as explained above.

As for $`H_{in}`$ and $`H_{out}`$, we again change $`|tt|`$ to be an operator on three qubits for the middle time leafs and two qubits for the beginning and end leafs.

We first claim that restricting ourselves to the subspace spanned by states with the clock qubits being in valid unary representations, all previous claims hold. Explicitly, as can be easily checked:

###### Claim 3

For any state $`|\eta `$ which represents a valid history of a computation, (in unary representation) we still get $`H_{prop}^{}|\eta =0`$.

From this, using exactly the same arguments as used before, we have that

###### Claim 4

If $`|\eta `$ is a history of an accepting computation, then $`\eta |H^{}|\eta ϵ.`$

Hence, completeness will go through with these modifications. However, soundness will not go through because of the following reason. The $`T`$ qubits that we have introduced have many more possible states except for valid unary representations of some time step. The $`H^{}`$ we have defined operates on such states as well; To prove soundness, we need to show that among such states there are no states of small eigenvalue in case of $`x`$ not in the language. This might be complicated, and we resort to a different solution.

In addition to the modifications of the existing terms in the Hamiltonian, we introduce a new term which penalizes the state of the clock qubits if they are not unary representation of some time step. We call this term $`H_{clock}`$; It locally checks that the clock bits are a valid unary representation. All we need to check is that two consequent bits cannot be in the state $`|01`$; This can be done by a sum of local projections, as follows:

$$H_{clock}^{}=\underset{t=1}{\overset{T}{}}|0101|_{t1,t}I.$$
(40)
Our (truly!) final Hamiltonian is defined to be

$$H^{}=H_{in}^{}+H_{out}^{}+H_{prop}^{}+H_{clock}^{}$$
(41)
Clearly, $`|\eta `$ (with a unary clock) is an eigenvector of eigenvalue $`ϵ`$ of the new Hamiltonian $`H^{}`$, since it is a zero eigenvector of $`H_{clock}^{}`$, and so completeness is preserved.

For the proof of soundness, we observe that $`H^{}`$ keeps the subspace that is spanned by all states in which the clock qubits are valid unary representations invariant; Let us call this subspace $`𝒟`$. The orthogonal subspace, $`𝒟^{}`$, is also invariant under the operation of $`H^{}`$. $`H^{}`$ operates on $`𝒟`$ just as the previous $`H`$ did, and hence on this subspace the lower bound on the eigenvalues holds as before; On the orthogonal subspace $`𝒟^{}`$ the eigenvalue of $`H^{}`$ is at least $`1`$ since $`H_{clock}^{}`$ detects at least one violation. Hence, overall, the lower bound from theorem 2 holds here too. This completes the proof of completeness of $`5`$-local Hamiltonian.

###### Remark 2

Why 5? We remark here regarding the necessity of three qubits Hamiltonians instead of one qubit Hamiltonians to control the propagation in time. One can naively suggest to use the one qubit Hamiltonian $`|10|`$ operating on the $`t^{th}`$ clock qubit to represent the propagation from $`t1`$ to $`t`$, instead of the three qubit operator we use. This suggestion does not work for the following reason: the history states will no longer be eigenstates of $`H_{prop}^{}`$, since the one qubit time propagation terms might cause valid time leafs to propagate to invalid ones; E.g., $`|11100000`$ will propagate by $`U_6|10|_6`$ to $`|11100100`$. This does not happen when three qubit operators are used. It is an open question whether this obstacle can be overcome to show that $`3`$-local or $`4`$-local Hamiltonian is QMA complete; See open question 3.

## 7 Discussion and Open Questions

We have presented here a beautiful result by Kitaev which we believe is a fundamental stepping stone for the field of quantum complexity. We collect here a list of open questions it raises.

The first set of problems is related to the question of the expressiveness of the class QMA. There are hundreds of NP complete problems, from an enormous variety of fields; So far, the only interesting quantum MA complete problem we know of is the Local Hamiltonian problem.

###### Open Question 1

Find more quantum MA complete problems.

In particular,

###### Open Question 2

Is there a natural QMA complete problem which is not quantum related?

We have proved that $`5`$-local Hamiltonian is $`QMA`$ complete. What is the importance of the number five? It is unknown whether $`5`$ qubits are necessary. Perhaps even $`2`$locality suffices to achieve QMA completeness. This is very different from the classical situation, where it is known that $`3`$-SAT is NP complete but $`2`$-SAT can be solved in polynomial time.

###### Open Question 3

What is the complexity of $`k`$-local Hamiltonian with $`k=2,3,4`$?

The next question is related to the definition of the class $`QMA`$:

###### Open Question 4

Is QMA with two sided errors the same as QMA with one sided error?

This holds in the classical case, and the question is whether it holds quantumly. Kitaev and Watrous show the equivalence of one and two sided errors in certain cases (quantum interactive proofs with more rounds) but the proof does not carry over to this case.

Another open question which is related to the definition of $`QMA`$ is

###### Open Question 5

Is QCMA$`=`$QMA?

Due to the results presented in this survey, it seems reasonable to assume that the answer is yes. Our intuition behind this conjecture is that the quantum verifier limits itself in its tests of the quantum state to the reduced density matrices of five qubits; It therefore does not care about longer range entanglement. Perhaps such states that are specified by short range entanglement can be efficiently generated. In other words:

###### Open Question 6

Consider a (possibly very complicated) $`n`$ qubit state $`|\xi `$. Is there an efficient circuit that generates a state $`|\xi ^{}`$ which has (almost) the same reduced density matrices to any subset of five qubits?

If this can be done, this will prove the equality $`QCMA=QMA`$ since the classical witness can be the description of the quantum circuit, and the verifier can generate the state on its own. A proof that shows this equivalence is likely to be very insightful regarding quantum correlations. This question touches upon the interesting question of whether it is possible to develop a quantum analog of the beautiful theory of pseudo-random generators; In pseudo-random generation, one generates probability distributions that are very different from the uniform distribution but such that any circuit of some restricted set (say of bounded size) cannot tell the difference. The question we are asking is of a similar type, and can be viewed as a pseudo quantum generator type question, since we need the state to pass the test of the very restricted verifier who only looks at sets of five qubits.

The results presented here highlight a very interesting connection between Hamiltonians and unitary gates or quantum circuits, which Kitaev attributes to Feynman. We view this connection as fascinating and potentially very powerful. In particular, in exactly the same way $`QMA`$ circuits are translated to a local Hamiltonian, one can also translate $`BQP`$ circuits to a local Hamiltonian; It is very interesting to ask whether the other direction of moving from groundstates of local Hamiltonians to efficient circuits that generate them also holds. We cannot hope for a constructive version of this direction since it is $`QMA`$ hard, but an existence proof of such short circuits for ground states of local Hamiltonians will be very interesting, leading to a positive answer to open question 5 and to implications to the very important task of quantum state generation (see .)

###### Open Question 7

Given a local Hamiltonian, does there exist a polynomial size quantum circuit that generates (a state with non negligible projection on) its ground state?

We remark that Feynman’s point of view of moving from circuits to time independent Hamiltonians, enables one to translate short computation time into large spectral gap of Hamiltonians. The spectral gap of $`\mathrm{\Omega }(1/T^3)`$ achieved in kitaev’s proof is indeed expressed in terms of the computational time $`T`$. It is interesting to compare this to the framework of adiabatic quantum computation in which the opposite direction of moving from large spectral gaps to efficient state generation is taken, when one aims at generating a groundstate of a final Hamiltonian $`H_f`$ by designing a sequence of local Hamiltonians $`H_0,\mathrm{}H_f`$ all with large spectral gaps.

We end with a more general open problem which seems related to the results presented here:

###### Open Question 8

Does the quantum analog of the PCP theorem hold? Can we prove hardness of approximation for quantum computation?

Hopefully, the results and open questions presented in this survey will provide easy access to research in what we view as a fascinating area.

## 8 Acknowledgements

One of us (D.A.) wishes to thank Avi Wigderson for insightful comments during Kitaev’s first lecture about the subject.


text:
# Shot Noise and Proximity Effect in Superconductor–Normal-Metal Heterostructures

## 1 Introduction

The current in mesoscopic structures fluctuates in time. Due to the coherent nature of the transport, these fluctuations provide information on the quantum physics of the underlying transport mechanism (see Ref.  for a summary). For example, measuring the current noise $`S_I`$ in a tunnel junction allows to extract the effective charge of the carriers involved. The effective charge of a tunnel junction is defined similar to Fano factor by the ratio $`q_{\mathrm{eff}}^{\mathrm{tun}}=S_I/2I`$, where $`I`$ is the average current. This has been used to determine effective charges of $`e/3`$ and $`e/5`$ in the fractional quantum Hall regime. For non-opaque junctions the definition of an effective charge only makes sense in reference to something known. For example, in superconducting heterostructures one usually takes the normal state as reference point and we may define an effective charge in reference to that. In this way an effective charge $`2e`$ in the case of Andreev reflection for a diffusive contact has been predicted theoretically and determined experimentally .

It is also possible to measure nonlocal current-current correlations, the so-called crosscorrelations. A fermionic version of the Hanbury-Brown and Twiss experiment was performed and showed negative crosscorrelation . These originate from the Pauli exclusion principle, which leads to a noiseless stream of incoming particles at zero temperature. The electrons are scattered at a beam splitter one by one. Obviously an electron leaving in one lead can not leave in the other, therefore the time-dependent fluctuations in the two leads are anticorrelated, thus leading to negative crosscorrelations. This argument has been put on solid ground by Büttiker , who has shown that this holds for transport of fermions in arbitrary multi-terminal structures with uncorrelated leads.

A natural question arising in this context is, what happens if the incoming particles are correlated. This can be achieved by using a superconducting terminal, from which particles are injected by Andreev reflection, i. e. as correlated electron-hole pairs. In a single-mode beam-splitter geometry this can eventually lead to positive crosscorrelations. Some doubts have been raised, that the positive correlations survive in the many channel limit. Thus, we will study below one example of a superconducting beam splitter, in which large positive crosscorrelations appear. Similar results have been obtained in different geometries.

## 2 Diffusive Wire

We study a two-terminal geometry, where a diffusive wire is mounted between a normal and a superconducting terminal, see the inset of Fig. 1. We expect a doubling of the effective charge, both in the quantum coherent regime at zero energy, and in the incoherent regime $`EE_{Th}`$ (with Thouless energy $`E_{Th}=D/L^2`$). However, it is well know that the conductance is enhanced at intermediate energies due to the proximity effect – the so-called reentrant behaviour. To access the noise in this regime, we make use of an extended Keldysh Green’s function method outlined in Ref. . Inside the mesoscopic wire the quasiclassical transport equations are obeyed. In a diffusive normal metal wire they read

$$D\frac{}{x}\left(\stackrel{ˇ}{G}(x,\chi )\frac{}{x}\stackrel{ˇ}{G}(x,\chi )\right)=[iE\overline{\tau }_3,\stackrel{ˇ}{G}(x,\chi )].$$
(1)
Here $`D`$ is the diffusion constant and $`x`$ the coordinate along the wire, which has a length $`L`$. It’s conductance is $`G_\mathrm{N}=\sigma A/L`$ (cross section $`A`$). At both ends boundary conditions to reservoirs have to be supplied. At the normal end with ideal connection the Green’s function is continuous: $`\stackrel{ˇ}{G}(0,\chi )=\stackrel{ˇ}{G}_\mathrm{N}(\chi )`$. The current-correlations are encoded in the dependence on the so-called counting field $`\chi `$. The other end is connected to a superconducting reservoir by a contact of negligible resistance, which leads to the boundary condition $`\stackrel{ˇ}{G}(L)=\stackrel{ˇ}{G}_\mathrm{S}`$. Details of the calculation can be found in Ref..

In Fig. 1 we present results for the transport properties at zero temperature and for $`E_{Th}\mathrm{\Delta }`$. Both the differential current noise $`dS/dV`$ and the differential conductance $`dI/dV`$ show a reentrant behaviour. The energy dependence of both quantities is nonetheless different, demonstrating that the noise can not be simply obtained by multiplying a doubled energy-independent noise $`4eG_NV/3`$ by the differential resistance. Consequently this leads to an effective charge, defined by $`q_{\mathrm{eff}}(V)=(3/2)dS/dI`$, which drops below the value of $`2e`$ at energies of the below $`5E_{Th}`$. We believe this drop is due to a pair-pair correlation effect. This is supported by the fact the the suppression of the effective charge is mainly below the energy at which the maximal enhancement of the conductance occurs. A confirmation of this conjecture could be obtained in a system with two superconducting terminals, in which pair-pair correlations could be suppressed by destructive interference.

## 3 Beam Splitter

To address the question whether positive crosscorrelations can exist in a beam splitter geometry with one superconducting lead and two normal leads we study the layout shown in the inset of Fig. 2. The superconductor is held at zero voltage and the two normal terminals are biased symmetrically at the same voltage $`V`$. The terminals are connected by tunnel junctions to a central node. This could be either a small metallic island or a chaotic cavity and is assumed to be so large, that we can neglect charging effects. The transport properties are easily obtained using the circuit theory formulation. In fact, for a setup where an arbitrary number of terminals is connected to one common node by tunnel junctions the general solution can be obtained. Note also, that this solution includes not only the noise, but also the full counting statistics of this mesoscopic structure.

We will now concentrate on auto- and crosscorrelations only. These are defined as $`S_{ij}=2𝑑t\delta I_i(t)\delta I_j(0)`$, where $`I_{i(j)}(t)`$ are the time dependent currents in terminal $`i(j)`$. We obtain in the low-energy limit ($`T=0`$, $`V\mathrm{\Delta }`$):

$`G={\displaystyle \frac{g_S^2g_N^2}{(g_S^2+g_N^2)^{3/2}}}`$ , $`S=2G|eV|\left(25{\displaystyle \frac{g_S^2g_N^2}{(g_S^2+g_N^2)^2}}\right),`$
$`S_{12}={\displaystyle \frac{G|eV|}{2}}\left(15{\displaystyle \frac{g_S^2g_N^2}{(g_S^2+g_N^2)^2}}\right)`$ , $`S_{11}={\displaystyle \frac{G|eV|}{2}}\left(35{\displaystyle \frac{g_S^2g_N^2}{(g_S^2+g_N^2)^2}}\right).`$
For completeness we also cite the results for the case, in which the superconductor is in its normal state:

$`G^N={\displaystyle \frac{g_Sg_N}{(g_S+g_N)}}`$ , $`S^N=2G^N|eV|\left(12{\displaystyle \frac{g_Sg_N}{(g_S+g_N)^2}}\right),`$
$`S_{12}^N={\displaystyle \frac{G^N|eV|}{2}}{\displaystyle \frac{g_Sg_N}{(g_S+g_N)^2}}`$ , $`S_{11}^N={\displaystyle \frac{G^N|eV|}{2}}\left(23{\displaystyle \frac{g_Sg_N}{(g_S+g_N)^2}}\right).`$
In Fig. 2 we summarize the transport properties, emphasizing the difference between the superconducting state and the normal state. Note that the total current noise is given by $`S=2S_{11}+2S_{12}`$. An interesting observation is that the transport properties are invariant under inversion of the conductance ratio $`g_N/g_S`$. In the following we will thus distinguish the case of weak (or strong) proximity effect determined by $`g_Ng_S`$ and the case of optimal proximity effect defined by $`g_Ng_S`$. Below we will use the terminology weak for both the weak and the strong proximity regimes equally.

The conductance vanishes rapidly in the limit of weak proximity and shows a resonance in the regime of optimal proximity. This actually defines the condition for optimal proximity effect: the regime, in which the proximity effect has the largest impact on the conductance. Note, that without proximity effect the conductance would vanish always in the present geometry. In Figure 2 we defined the effective charge in the superconducting case with respect to the normal case: $`q_{\text{eff}}=SI^N/S^NI`$. This is in analogy to the diffusive wire, studied in the previous section. Remarkably, the effective charge shows an increase above $`2e`$ for the case of weak proximity. Around the resonance condition $`g_Sg_N`$ the effective charge drops below $`2e`$ and reaches a minimum of $`(3/2)e`$ for $`g_S=g_N`$. We note that this behaviour stems from our definition of the effective charge. The Fano factor for the superconducting case, defined by $`F=S/2eI`$, never increases above 2.

The most surprising observation is that we can obtain positive crosscorrelations in the superconducting beam splitter, whereas they are manifestly negative for the normal beam splitter. Interestingly the positive crosscorrelations are found in the limit of weak proximity, or in the absence of proximity. Thus, they should be obtained from simple arguments. Indeed, from a calculation of the full counting statistics, it follows that in the weak proximity limit the statistics consists of independent events of pair tunneling. The possible events are pair tunneling into terminal $`N_1`$ or $`N_2`$ and correlated tunneling in both terminals. These events occur with equal probabilities, however, in the limit of weak proximity these events are uncorrelated. Thus, two particle tunneling events into the same lead do *not* contribute to cross correlations. In contrast, tunneling of two particles into different leads is *automatically* positively correlated. Thus, it follows quite generally, that the crosscorrelations are positive.

Following this argumentation to the regime of optimal proximity effect in fact shows, that it is much harder to understand the occurrence of *negative* correlations in this regime. We propose the following interpretation. These negative crosscorrelations occur in the same regime, in which the effective charge drops below $`2e`$. For uncorrelated electrons a suppression of the effective charge is interpreted as a consequence of the Fermi statistics. More precisely, it is a consequence of the Pauli principle, that two fermions can not occupy the same state. Now, the same holds obviously for pairs of electrons. If a two particle state is occupied by two electrons, this state is blocked for other pairs of electrons. Cooper pairs are such objects, and can not occupy the same state twice. Note, that we speak of Cooper pairs, but rather mean an correlated electron pair, which has entered the normal metal node. In the limit of weak proximity, the average occupation of a state on the central node with an electron pair is small, and the occupation does not matter, therefore. The same holds in the limit of strong proximity, where the state is nearly always occupied. This changes in the limit of optimal proximity, where the occupation approaches $`1/2`$. Just as in the case of Fermions, this leads to a strong suppression of the Fano factor.

To understand the negative crosscorrelations we follow the previous argumentation. The Pauli repulsion of Cooper pairs reduces the noise in the ’incoming’ beam of Cooper pairs (similar to lowering the temperature in a fermionic beam). Let us, therefore, consider an incoming ’noiseless’ beam of Cooper pairs, which is distributed equally among the possible outgoing states. The crosscorrelations can be written in terms of occupations of the outgoing states $`n_{1,2}`$ as $`s_{12}=n_1n_2n_1n_2`$. The possible outgoing states are $`(n_1=2,n_2=0)`$, $`(n_1=0,n_2=2)`$, and $`(n_1=1,n_2=1)`$, where the last state is doubly degenerate. The average occupation in terminal 1 is then $`n_1=(1/4)\times 2+(1/2)\times 1=1`$, and the same for terminal 2. For the crosscorrelations we need $`n_1n_2`$. The first two outgoing states do not contribute, whereas the third yields $`(1/2)\times 1`$. Collecting all terms we find $`s_{12}=1/2`$, which is negative. The value of the crosscorrelations in Fig. 2 is only $`1/8`$. This discrepancy is probably due to the finite backscattering in the double tunnel junction geometry. Nevertheless the qualitative behaviour is correct.

## 4 Summary

We have shown that current-correlations in multi-terminal heterostructures display a number of quite remarkable properties, which depend on the phase coherent nature of quantum transport. The proximity effect in a diffusive wire modifies the conductance and the noise in a nontrivial way. Both are enhanced at energies of the order of the Thouless energy, which divides coherent and incoherent Andreev transport. We have defined an effective charge by referencing to the noise in the normal state. The effective charge displays a suppression below $`2e`$ for energies below $`E_{Th}`$, which could be due to coherent multiple Andreev-pair transport. For a multi-terminal structure with one superconducting and two normal metal arms, we have shown that positive crosscorrelations of the currents in the two arms are a generic feature in these system. It is remarkable, that in the region, in which the proximity effect has the strongest impact on the conductance, the crosscorrelations are negative. This can be explained by a Pauli exclusion principle for Cooper pairs in a transport process. Finally, we would like to emphasize the similarity of the noise behaviour in a diffusive wire and a multiple tunnel junction geometry. In particular, the suppression of the Fano factor in the regime of optimal proximity effect has probably the same origin. For the tunnel-junction geometry the finite occupation of the central node with Cooper pairs leads to a reduces Fano factor and positive cross correlations. In the diffusive wire the effective charge (equivalent to the Fano factor) are suppressed below energies of the order of $`E_{Th}`$, which is probably due to a finite occupation of the wire with Cooper pairs. A deeper understanding of this phenomenon is obviously interesting for further studies.

We acknowledge useful discussions with M. Büttiker, J. C. Cuevas, A. A. Kozhevnikov, D. E. Prober, B. Reulet, and P. Samuelsson. This work was supported by the Swiss NSF and the NCCR ”Nanoscience”.


text:
# Vertical Discontinuities in Self-Affine Surfaces Lead to Multi-affinity

## Abstract

Many systems of both theoretical and applied interest display multi-affine scaling at small length scales. We demonstrate analytically and numerically that when vertical discontinuities are introduced into a self-affine surface, the surface becomes multi-affine. The discontinuities may correspond to surface overhangs or to an underlying stepped surface. Two surfaces are numerically examined with different spatial distributions of vertical discontinuities. The multi-affinity is shown to arise simply from the surface of vertical discontinuities, and the analytic scaling form at small length scales for the surface of discontinuities is derived and compared to numerical results.

preprint: APS/123-QED

Many systems of both theoretical and applied interest display multi-affine scaling at small length scales Barabási et al. (1991); Barabási and Vicsek (1991); Barabási et al. (1992); Sarma et al. (1996); Dharmadhikari et al. (1999); Kim and Kong (2000). Recently, an extensive scaling analysis of surfactant templated hydrogel surfaces as measured by atomic force microscopy (AFM) was performed Chakrapani et al. . This analysis indicated that the hydrogel surfaces were self-affine; however, a later numerical study of a frustrated spring-network model of cross-linked hydrogels Buendia et al.  indicated multi-affine scaling. Reconciliation of these two observed behaviors led to an interesting and universal conclusion: introduction of vertical discontinuities into a self-affine surface leads to multi-affine scaling. To our knowledge, this has not previously been reported in the literature, most likely because height-height correlations are usually calculated for the second power of the height increments, in which case the surface constructed only of discontinuities resembles a random walk on all length scales. Here, we provide a discussion which explains this source of multi-affine behavior, and we present both numerical and analytic results.

Consider a one-dimensional, real, single-valued surface, $`z(x)`$, where $`x`$ is a real number on the interval, $`x[0,1]`$. The generalized height-height correlation function Barabási et al. (1991); Barabási and Vicsek (1991); Barabási et al. (1992); Sarma et al. (1996); Dharmadhikari et al. (1999); Kim and Kong (2000); Buendia et al.  for this surface is

$$C_q(r)=|z(x+r)z(x)|^q,$$
(1)
where $`\mathrm{}`$ denotes an average over all $`x`$ values, $`|r|<1/2`$, and $`q`$ is a positive, non-zero real number. Without loss of generality, we may assume that $`r`$ is positive, since $`C_q(r)=C_q(r)`$ for any function $`z(x)`$.

Often, $`C_q(r)`$ will display power-law behavior for $`rr_\times `$ and will display a constant value for $`rr_\times `$, where $`r_\times `$ is some cross-over length scale between the two behaviors. Surfaces displaying power-law correlations, $`C_q(r)=A_qr^{q\alpha _q}`$, fall into one of two categories: $`q`$-independent scaling, $`\alpha _q=\alpha `$, called self-affine scaling, and $`q`$-dependent scaling, called multi-affine scaling Barabási et al. (1991); Barabási and Vicsek (1991); Barabási et al. (1992); Sarma et al. (1996); Dharmadhikari et al. (1999); Kim and Kong (2000).

By introducing vertical discontinuities into a self-affine surface, we can cause the surface to become multi-affine. Consider the function $`z(x)`$, which is self-affine for all $`rr_\times `$. For the numerical results, self-affine surfaces were generated using the method of Ref. Voss (1985). We introduce a finite number, $`N`$, of vertical discontinuities into the function $`z(x)`$ such that the new surface is

$$z^{}(x)=\left\{\underset{i=1}{\overset{N}{}}\delta _i\mathrm{\Theta }(xx_i)\right\}+z(x),$$
(2)
where $`i`$ indexes the discontinuities, $`\delta _i`$ is the magnitude of the discontinuity at $`x=x_i`$, and $`\mathrm{\Theta }(y)`$ is a step function which is zero for $`y<0`$ and 1 for $`y0`$. Without loss of generality, we can assume an order to the set $`\{x_i\}`$ such that $`x_{i1}<x_i`$ and $`x_0=0`$.

Physically, $`z^{}(x)`$ can be thought of as describing a system with overhangs between regions with self-affine scaling, such as for the spring-network model of Ref. Buendia et al. , or the deposition of a very thin self-affine film onto a stepped surface. A typical stochastic realization of $`z^{}(x)`$ with equally spaced $`x_i`$ is shown in Fig. 1(a), and the corresponding generalized height-height correlation function, $`C_q(r)`$, is shown in Fig. 1(b). Figure 2 shows a similar plot, but the discontinuity positions, $`x_i`$, are chosen randomly and uniformly on the interval $`(0,1)`$. The number of discontinuities, $`N`$, is the same for both Fig. 1 and Fig. 2. For length scales $`rr_\times `$, the stepped surface, $`z_\mathrm{\Theta }z^{}(x)z(x)`$, is expected to be simply a random walk in height with $`\alpha _q=0.5`$, but this is not obvious in the numerical data because of the relatively small number of discontinuities in the $`x`$ interval.

From examination of the numerical results in Figs. 1 and 2, it is obvious that the multi-affinity is caused by the stepped surface, $`z_\mathrm{\Theta }(x)`$, and the generalized height-height correlation function of $`z_\mathrm{\Theta }(x)`$ can be analytically calculated for $`rr_\times `$, where $`r`$ is also much smaller than the smallest $`x`$ separation between discontinuities for finite systems with finite $`N`$.

$$C_q(r)=_0^1|\underset{i=1}{\overset{N}{}}\delta _i\left\{\mathrm{\Theta }(x+rx_i)\mathrm{\Theta }(xx_i)\right\}|^q𝑑x.$$
(3)
The argument, $`\mathrm{\Theta }(x+rx_i)\mathrm{\Theta }(xx_i)`$, is either 1 ($`x_irx<x_i`$) or 0 (otherwise), and thus, in the integration range $`x=x_ir`$ to $`x=x_i`$, only one of the $`N`$ discontinuities has a non-zero contribution to the integral. Equation (3) thus reduces to

$$\begin{array}{ccc}C_q(r)\hfill & =\hfill & _{i=1}^N_{x_{i1}}^{x_i}|_{i=1}^N\delta _i\{\mathrm{\Theta }(x+rx_i)\hfill \\ & & \mathrm{\Theta }(xx_i)\}|^qdx\hfill \\ & =\hfill & _{i=1}^N_{x_ir}^{x_i}|\delta _i|^q𝑑x\hfill \\ & =\hfill & r_{i=1}^N|\delta _i|^q.\hfill \end{array}$$
(4)
For comparison with Figs. 1 and 2,

$$\frac{1}{q}\mathrm{log}_{10}\{C_q(r)\}=\frac{1}{q}\mathrm{log}_{10}\{r\}+\frac{1}{q}\mathrm{log}_{10}\left\{\underset{i=1}{\overset{N}{}}|\delta _i|^q\right\},$$
(5)
and thus, $`\alpha _q=q^1`$ and $`\mathrm{log}_{10}\{A_q\}=\mathrm{log}_{10}\left\{N|\delta _i|^q\right\}`$. See Fig. 3. Note that the general form is independent of the $`x_i`$ distribution and depends on the $`\delta _i`$ distribution only through $`|\delta _i|^q`$.

Having derived the small-$`r`$ scaling behavior for the stepped surface, $`z_\mathrm{\Theta }(x)`$, it remains to be shown how this multi-affine stepped surface influences the multi-affinity of the complete or mixed surface, $`z^{}(x)`$. Consider the generalized height-height correlation function for the sum of the two surfaces

$$C_q(r)=|\mathrm{\Delta }_\mathrm{\Theta }^r(x)+\mathrm{\Delta }_z^r(x)|^q,$$
(6)
where $`\mathrm{\Delta }_\mathrm{\Theta }^r(x)=z_\mathrm{\Theta }(x+r)z_\mathrm{\Theta }(x)`$ and $`\mathrm{\Delta }_z^r(x)=z(x+r)z(x)`$. The two extremes of $`|z(x)||z_\mathrm{\Theta }(x)|`$ and $`|z_\mathrm{\Theta }(x)||z(x)|`$ should behave as multi-affine and self-affine surfaces, respectively, but for intermediate mixed surfaces, the behavior is more complex. For the numerical results shown in Fig. 4, two asymptotic scaling regimes are seen. For large $`q`$, the mixed surface tends towards multi-affine behavior with $`\alpha _q=1/q`$, and for small $`q`$, the mixed surface tends towards self-affine behavior with $`\alpha _q=\alpha `$.

We can derive the two asymptotic scaling behaviors for the mixed function by first considering that for $`rr_\times `$

$$\begin{array}{ccc}C_q(r)\hfill & =\hfill & |\mathrm{\Delta }_\mathrm{\Theta }^r(x)+\mathrm{\Delta }_z^r(x)|^q\hfill \\ & =\hfill & |\mathrm{\Delta }_z^r(x)\left(\frac{\mathrm{\Delta }_\mathrm{\Theta }^r(x)}{\mathrm{\Delta }_z^r(x)}+1\right)|^q\hfill \\ & =\hfill & |\mathrm{\Delta }_z^r(x)|^q|\frac{\mathrm{\Delta }_\mathrm{\Theta }^r(x)}{\mathrm{\Delta }_z^r(x)}+1|^q\hfill \\ & =\hfill & _0^1|\mathrm{\Delta }_z^r(x)|^q|\frac{\mathrm{\Delta }_\mathrm{\Theta }^r(x)}{\mathrm{\Delta }_z^r(x)}+1|^q𝑑x\hfill \\ & =\hfill & _{i=1}^N_{x_{i1}}^{x_i}|\mathrm{\Delta }_z^r(x)|^q|\frac{\mathrm{\Delta }_\mathrm{\Theta }^r(x)}{\mathrm{\Delta }_z^r(x)}+1|^q𝑑x.\hfill \end{array}$$
(7)
By noticing that $`\mathrm{\Delta }_\mathrm{\Theta }^r(x)=0`$ or $`\delta _i`$ in the interval $`x(x_{i1},x_i]`$,

$$\begin{array}{ccc}C_q(r)\hfill & =\hfill & _{i=1}^N_{x_{i1}}^{x_ir}|\mathrm{\Delta }_z^r(x)|^q|\frac{0}{\mathrm{\Delta }_z^r(x)}+1|^q𝑑x\hfill \\ & & +_{i=1}^N_{x_ir}^{x_i}|\mathrm{\Delta }_z^r(x)|^q|\frac{\delta _i}{\mathrm{\Delta }_z^r(x)}+1|^q𝑑x\hfill \\ & =\hfill & _{i=1}^N_{x_{i1}}^{x_ir}|\mathrm{\Delta }_z^r(x)|^q𝑑x\hfill \\ & & +_{i=1}^N_{x_ir}^{x_i}|\mathrm{\Delta }_z^r(x)|^q|\frac{\delta _i}{\mathrm{\Delta }_z^r(x)}+1|^q𝑑x.\hfill \end{array}$$
(8)
As $`q0`$, $`|\frac{\delta _i}{\mathrm{\Delta }_z^r(x)}+1|^q1`$, and as $`q\mathrm{}`$, $`|\frac{\delta _i}{\mathrm{\Delta }_z^r(x)}+1|^q|\frac{\delta _i}{\mathrm{\Delta }_z^r(x)}|^q`$. This gives the following approximations for the two asymptotic regimes,

$$C_q(r)\{\begin{array}{cc}|\mathrm{\Delta }_z^r(x)|^q=A_qr^{q\alpha }\hfill & q1\hfill \\ A_qr^{q\alpha }+rN|\delta _i|^q\hfill & q1,\hfill \end{array}$$
(9)
where the additional approximation $`_{x_{i1}}^{x_ir}\mathrm{}𝑑x_{x_{i1}}^{x_i}\mathrm{}𝑑x`$ is made, which is valid when $`r1`$.

For large $`q`$, the scaling may resemble either self-affine scaling or multi-affine scaling, depending on the exact behavior of $`A_q`$ for $`z(x)`$ and the behavior of $`|\delta _i|^q`$; however, for small $`q`$, the behavior will always resemble self-affine scaling, provided, of course, that the signal strength of $`z(x)`$ is sufficiently large compared to the stepped function signal strength to be numerically noticeable. For the mixed functions examined in Fig. 4, self-affine scaling is seen for small $`q`$ and multi-affine scaling with $`\alpha _q=1/q`$ is seen for large $`q`$, but this is not a universal outcome as indicated in Eq. (9).

The scaling behavior of a self-affine surface with vertical discontinuities was investigated numerically and analytically, and it was shown that the surface of discontinuities (the stepped surface) was the source of the multi-affine behavior. It was further shown numerically and analytically, that the general form for the scaling of the stepped surface at small length scales depends on the distribution of discontinuities only through $`|\delta _i|^q`$. Two asymptotic scaling behaviors were derived for the self-affine surface with discontinuities, and for the numerical results shown here, self-affine scaling is seen for small $`q`$ and multi-affine scaling with $`\alpha _q=1/q`$ is seen for large $`q`$. The large-$`q`$ asymptotic behavior is not universal and depends on the detailed $`q`$ dependence of the mixed function.

These results suggest the need to further study scaling and universality for a variety of systems where vertical discontinuities are known or are expected to exist. Such systems include many thin film deposition model and deposition processes onto stepped surfaces. For these processes, the deposition time should have a large effect on the multi-affine scaling behavior.

###### Acknowledgements.

The author thanks G. M. Buendía and P. A. Rikvold for useful discussions and comments on the manuscript. Funding was provided by the Netherlands Organization for Scientific Research (NWO).