{'fraction_non_alphanumeric': 0.03807195249738037, 'fraction_numerical': 0.007334963325183374, 'mean_word_length': 4.148451548451549, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 15, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the power quantum computation over real Hilbert spaces

We consider the power of various quantum complexity classes with the restriction that states and operators are defined over a real, rather than complex, Hilbert space. It is well know that a quantum circuit over the complex numbers can be transformed into a quantum circuit over the real numbers with the addition of a single qubit. This implies that BQP retains its power when restricted to using states and operations over the reals. We show that the same is true for QMA(k), QIP(k), QMIP, and QSZK.


Introduction
The standard quantum formalism specifies a complex Hilbert space, but one could just as well consider a real Hilbert space. In fact, a quantum formalism based on real Hilbert spaces has the same descriptive power as complex quantum formalism: given any description of a physical system using complex quantum formalism, there is a simple mapping to a description using real quantum formalism that gives the same predicted outcome statistics. Moreover, this description respects the division into subsystems [MMG09]. This means, for example, that there can be no experiment that can rule out real quantum formalism. 1 Now let us consider computation. Does the choice of real or complex Hilbert spaces change the power of various computing models? At first it might seem that this is obvious: if any quantum system can be described using real Hilbert spaces, then why not the physical systems underlying some computing model? For computing models where all parties are trusted this is indeed the case. BQP, EQP and related classes are all unchanged as well as classes where messages are classical, such at QCMA.
However, for interactive proofs, where the prover(s) are not trusted, there are three important problems. First, in the case of two or more subsystems the mapping from complex to real descriptions introduces entanglement not present in the original complex description. This is problematic for classes like QMA(2) which does not allow provers to be entangled. Second, the mapping from complex to real descriptions does not preserve inner products. Hence states can become more distinguishable, which is problematic for classes like QSZK where certain states are required to be indistinguishable from others. Finally, the mapping to real descriptions is not onto. Hence untrusted parties may have access to a larger set of operations than in the original complex description.

Contributions
For any quantum complexity class let us define a restricted class such that all states and operators are defined over the real numbers instead of the complex numbers. We name these classes by adding a subscript R. Thus BQP restricted to real gates and states becomes BQP R , etc.. We prove the following theorem: In order to prove this result we must overcome the difficulties mentioned in the introduction. The basic tool is an argument used in [MM11] to argue about security. The idea is this: in a certain basis the mapped description of a complex quantum state to a real quantum state looks like a coherent mixture of the original state and its complex state, identified by an extra qubit: where V is the change of basis matrix. Operators are similarly mapped: In this basis all the real operations of an honest party (the verifier, for example) commute with measuring the "extra" qubit in the Z basis. Hence we can reduce to a situation where we first measure to determine whether to perform original operations or complex conjugate operations, and then proceed. In either case the honest party has the same power, and susceptibility to being cheated, as in the original complex protocol. We use this argument in two ways. First, we use it to show that we can transform a complex protocol into a real protocol and retain the same completeness and soundness. This applies to all the complexity classes we consider. Second, in a multi-party setting, if one party is honest then the other party cannot distinguish between states any more than in the original protocol. We use this when arguing about QSZK.
The remaining tool that we use is an argument that when a multi-party computation is separable then entanglement is not required in the real simulation. We then use a recent result [HM10] showing that QMA(2) can be restricted to separable operations. This allows us to argue successfully in the case of QMA(2).

Real simulation
In this section we recall the relevant work on real simulation of arbitrary quantum systems over complex Hilbert spaces. In particular, we recall the real simulation of quantum circuits and multi-party computations. Importantly, we do not use the most obvious derivation, but use a different derivation which is conducive to our later arguments about computational complexity. We also consider another context for real simulation, where there is a multisubsystem computation which is separable.

Single party
It is a well known result that any quantum circuit can be simulated over a real Hilbert space by using one additional qubit. The basic idea is to store the 2-dimensional real vector space represented by a complex number in a 2-dimensional real vector space corresponding to the additional qubit added to the circuit. It is quite easy to derive the transformation needed to take states and gates over a complex Hlibert spaces to states and gates over real Hilbert space. Here we will use a somewhat non-obvious derivation that will be helpful later. This derivation is based on that of [MM11].
Consider a state | ψ on some complex Hilbert space. We may operate on it using some unitary gate U and finally measure it according to some Hermitian observable M , obtaining an expected value ψ | U † M U | ψ . We obtain the same expected value if we complex conjugate | ψ , U and M : Now suppose that we take a coherent mixture of the original circuit and its complex conjugate. That is, we start with a state where α 2 + β 2 = 1 and α, β ∈ R, then transform by the unitary and measure with the Hermitian observable Then we again obtain the same expected value: Now we have the following idea: since the imaginary part of the complex conjugate is opposite the imaginary part of the original, we might be able to arrange α and β so that the imaginary parts of the complex conjugate cancel those of the original, and we are left with something real. However the "extra" qubit gets in the way and it does not work out that way, but after a suitable change of basis we get something similar. We need α = β = 1 √ 2 and the qubit unitary Then we find This is the usual state we obtain if we represent the complex amplitudes a + ib in | ψ with the real qubit a | 0 + b | 1 . Thus we may understand the real simulation of a quantum circuit as a coherent mixture of the original circuit and its complex conjugate, under a suitable change of basis. Let us define the transformation R which takes complex states to real states (with double the dimension) as above: We define R( ψ |) analogously, and R applied to operators by where the third line follows from the observation that V ZV † = Y . We obtain the following properties of R(·).
Lemma 1. Let M , N be linear operators over a Hilbert space H. Further, let | ψ ∈ H. Then The first two lines are from the definition. The third and fourth line, and the last claim, are seen easily by undoing the change of basis by V and looking at the formulation in terms of the original and complex conjugate operators and vectors. The fifth line is obtained by the fact that the inner product is an equal mixture of the original and complex conjugate inner products, and hence only the real part remains.

Multiple parties
Suppose that we have some computation that happens between multiple parties and we wish to simulate the computation over real numbers instead of complex. Furthermore, we need the simulation to respect the original division into multiple parties. This can be accomplished by communicating the "extra" qubit between the parties, but this may not be feasible, for example in a Bell test. However, we can do the following: give a "copy" of the "extra" qubit to each party. When viewed as a coherent mixture of the original and complex conjugate computations this is immediately obvious. The state | ψ becomes with one of the "extra" qubits given to each party. An operator M applied by the jth party becomes where the subscript j indicates the jth "extra" qubit. Essentially, each party looks at their "extra" qubit to decide whether to apply the original or complex conjugate operator. Since the"extra" qubits are all correlated in the Z basis all the parties are coordinated. Interestingly, if we apply V as in the previous section to each of the "extra" qubits, we obtain a real state. We refer the reader to [McK10] section 2.5.4 for the details of this calculation.
We define a new transformation R (m) (·) by where there are m "extra" qubits, and analogously for R (m) ( ψ |). For operators we define R We obtain the following properties of R (m) (·).

Separable states and operations
Suppose that we have a computation with multiple subsystems which is separable. That is, the state and operators can all be written in the form where each M k,j is Hermitian and operates on the kth subsystem only (Hence M is also Hermitian.) To simulate general multi-partite computations the construction given in section 2.2 is required, and in particular this means that the state will be entangled across subsystems. In the case we are currently considering, we wish to maintain the separability. Fortunately, this is possible.
We will use the same methodology as in the previous sections, by considering coherent mixtures of the original and complex conjugate computation. For separable operators we can add an additional layer of complexity by considering a type of "partial" complex conjugation. The structure of the separable operator allows us to complex conjugate on only one subsystem in a well defined way. In the case of many subsystems, we can conjugate on a subset which we specify by way of a bit-string, which is the characteristic vector for the subset on which we conjugate: Let | ψ = | ψ 1 . . . | ψ m be a product state. Then Further, define M * z for z ∈ {0, 1} m to be M with (·) * k applied for each k such that z k = 1 (Note that the order does not matter) and analogously for | ψ * z .
Just as the complex conjugate computation gives the same outcome statistics as the original computation, partial complex conjugation also preserves statistics.
Proof. Note that it suffices to show Tr(M N ) = Tr(M * t N * t ) for t ∈ {1, . . . , m} since we may apply induction to obtain the full result. As well, it suffices to show the result for m = 2 and t = 1 since we may permute systems and combine m − 1 of the systems into 1 to reduce to this case.
Here the third line follows from the fact that M 1,j and N 1,k are Hermitian.
We are now ready to define the real simulation for a separable computation. We will consider the case of two subsystems, but the same techniques generalize for any number of subsystems. Also, we will only consider a measurement, but arbitrary separable superoperators can also be considered.
We begin with a product state | ψ = | ψ 1 | ψ 2 and a separable measurement M = j M 1,k ⊗ M 2,j . Consider the state and the operator Note that | ψ ′ is a product state since it can be written (after permuting registers) as 1 2 and M ′ is separable. Now let us evaluate Tr(| ψ ′ ψ ′ | M ′ ). First define Π z = | z z | 1,2 to be the projection on to the computational basis state | z on the "extra" qubits. Then z Π z M ′ Π z = M ′ and hence Lemma 3 applied for each z then gives Now we apply the same trick as for the other real simulations, and perform a change of basis by V on each "extra" qubit to obtain real states and operators. Thus we make the following definitions: Here R (2) 1 and R 2 are both just R as in section 2.1, but with different "extra" qubits. For operators we define We obtain the following properties:

Complexity implications
The real simulation for single systems and lemma 1 immediately imply that BQP = BQP R , EQP = EQP R and QCMA = QCMA R . We show that the analogous results are also true for QMA, QMA(2), QIP, MQIP and QSZK.

QMA = QMA R
Suppose we have a problem in QMA with a verifier A(x), which we model as a POVM element corresponding to "ACCEPT" for input x. That is, when the prover sends state | ψ , the verifier accepts with probability ψ | A(x) | ψ . We suppose that A(x) has completeness c and soundness s. It is clear that R Hence we obtain a real verifier that accepts valid real proofs with the same probability as the original verifier accepts valid proofs. In particular, the prover prepares R(| ψ ) and sends it along to the verifier, complete with the "extra" qubit, since the prover no longer needs it. Now consider an invalid real proof | φ sent to the real verifier R(A(x)). Note that, with a dishonest prover, we do not yet know 2 if | φ = R(| ψ ) for any | ψ so we must work a little harder than in the honest prover case. However, recall that there is a unitary transformation V such that Thus measuring V ZV † on the "extra" qubit commutes with R(A(x)). Since the qubit is then discarded we may assume that this measurement happens, and in particular that the prover does so. Hence the prover might as well have sent a mixture of V | 0 | ψ 0 and V | 1 | ψ 1 for some complex | ψ 0 and | ψ 1 . Note that the resulting mixture need not be real, but this only increases the power of the cheating prover. The probability of accepting is then a convex combination of ψ 0 | A(x) | ψ 0 and ψ 1 | A * (x) | ψ 1 . Since these are both at most s, the overall acceptance probability is at most s. Hence R(A(x)) is a verifier with the same completeness and soundness as A(x). Thus we have proved that QMA = QMA R .

QMA(2) = QMA R (2)
We first recall a recent result of Harrow and Montanaro [HM10]. They prove that QMA(k) = QMA SEP (2). Here QMA SEP (k) is the same as QMA(k) except that the "ACCEPT" POVM element A(x) is separable. Recall from the definition of QMA(k) that the provers must send unentangled states. Thus we are in the situation described in section 2.3. Now suppose we have a problem in QMA(k). We use Harrow and Montanaro's construction to obtain a problem in QMA SEP (2) with verifier separable A(x), again modelled as the "ACCEPT" operator, which has completeness c and soundness s. Suppose there exists a valid proof | ψ 1 | ψ 2 . Then prover 1 can send R (2) 1 (| ψ 1 ) while prover 2 can send R (2) 2 (| ψ 2 ). Meanwhile, the verifier becomes R (2) 1,2 (A(x)) since it is separable. We then have To analyze soundness we use an argument analogous to the QMA case. Suppose that some x is not in the language, so ψ | A(x) | ψ ≤ s for all | ψ . First we note that there exist unitaries V 1 and V 2 such that where | z is a computational basis state on the two provers' "extra" qubits. Thus measuring V † 1 ZV 1 on prover 1's "extra" qubit commutes with R (2) 1,2 (A(x)) and we may assume that this happens, and in particular that prover 1 does so. Similarly, we may assume that prover 2 measures their "extra" qubit in the basis V † 2 ZV 2 . Hence the provers might as well have sent a mixture of V 1 | j | ψ j V 2 | k | φ k for j, k ∈ {0, 1} and for some complex | ψ j and | φ k .
Note that the resulting mixture need not be real, but this only increases the power of the cheating prover. The probability of accepting is then a convex combination of the form By lemma 3 and the soundness of A(x), each ψ z 1 | φ z 2 | A * z (x) | ψ z 1 | φ z 2 is at most s and hence the overall acceptance probability is at most s. Thus R (2) 1,2 (A(x)) is a verifier with the same completeness and soundness as A(x) and we have proved that QMA SEP (2) = QMA(2) R and by extension QMA(2) = QMA(2) R .
We should point out that, unlike the proof for QMA here we are not allowed to simulate just any protocol for a QMA(k) problem. It must first be transformed into QMA SEP (2) protocol before the mapping to a real protocol is applied.

QIP(k) = QIP R (k)
First we argue that this result is indeed interesting. Since it is known that QIP = IP [JJUW10], it is trivially true that QIP R = QIP. However, since the QIP ⊆ IP inclusion is shown by proving that QIP ⊆ PSPACE there is not necessarily a relationship between the number of messages in a QIP protocol and the corresponding IP protocol. Indeed, a constant number of messages is not sufficient for IP unless AM = PH. Hence our result that QIP(k) = QIP R (k) is stronger than what can be derived from the fact that QIP = IP.
As for the proof, the situation for QIP is somewhat more complicated than for QMA since the prover and verifier must both perform computations, thus they must establish a shared pair of entangled "extra" qubits. However, a similar argument applies. We sketch the details.
Suppose we have a verifier A(x) for some problem in QIP(k) for k even. The verifier operates by preparing some initial state | 0 and applying some unitary U 1 (x). Then the verifier sends a portion of the state to the prover, keeping the rest in memory. After receiving a reply from the prover, the verifier applies U 2 (x). Continuing thus for some number of messages, the verifier finally measures according to M (x) and either accepts or rejects.
We can convert the entire procedure into a real quantum protocol as follows: the verifier prepares R (2) (| 0 ) which has two "extra" qubits. Then the verifier applies the unitary R (2) 1 (U 1 (x)) and sends the second "extra" qubit to the prover along with some portion of the remaining state, as in the original protocol. Note that the verifier sends this "extra" qubit on the first round only. The prover may use this "extra" qubit to perform operations, which are the prover's original operations transformed by R (2) 2 (·). After each pair of messages, the verifier applies R (2) 1 (U k (x)) and finally measures according to R (2) 1 (M (x)). It is easy to see that this real quantum protocol has the same completeness as the original protocol by appealing to lemma 2. For soundness we may apply an argument which analogous to that for QMA. We perform a change basis by V 1 ⊗ V 2 and find that, from the verifier's perspective, the entire protocol is a coherent mixture of the original protocol and its complex conjugate. We next note that (in this basis) measuring the first "extra" qubit (held by the verifier) in the Z basis commutes with all subsequent operations.
Thus the verifier might as well have flipped a coin and chose whether to perform the original protocol or the complex conjugate, announcing to the prover which one was chosen (hence the second "extra" qubit). Clearly in either case the soundness is identical to the original protocol, and hence the soundness of thereal quantum protocol is also identical to the original protocol.
For the case of QIP(k) with k odd we use a similar argument. Instead, however, the prover prepares the "extra" qubits and sends one to the verifier along with the initial message. Completeness is straightforward. For soundness we slightly modify the argument. Instead of the verifier choosing whether to perform the original protocol or the complex conjugate, the prover chooses.
Thus we have shown that QIP(k) = QIP R (k). One might wonder whether the multiparty real simulation is necessary: since the verifier and prover take turns they could communicate a single "extra" qubit back and forth. In fact, this is not sufficient. In the appendix we give an explicit example where the soundness of such a construction is not the same as in the original protocol.
The argument here is essentially the same as for QIP(k), except that we need to make sure that all the provers are able to perform operations. This is accomplished as follows. Since the provers are allowed prior entanglement, they may share an entangled set of m+1 "extra" qubits, and one prover entangles an additional qubit to send to the verifier along with the first message. If the original protocol had the verifier sending the first message then one of the provers sends an additional message at the beginning of the protocol containing just the "extra" qubit. This increases the number of messages by at most one. If the provers are not allowed prior entanglement, as in QMIP ne , then a different protocol is required. Here the verifier first prepares m + 1 "extra" and sends m of them to the m provers as the first m messages, keeping one behind. This increases the number of messages by at most m. 3 The arguments for soundness and completeness are by now predictable. The verifier's actions, in a suitable basis, look like a coherent mixture of the original protocol and the complex conjugate. Thus we may assume that either the provers together choose which version the verifier should perform, or the verifier chooses and announces this choice to the provers. Both the original and complex conjugate protocols have the same soundness so the real quantum protocol also has the same soundness.

QSZK
QSZK is essentially QIP with the additional restriction that, assuming an honest prover, at each step the verifier's state must be close (in trace distance) to the output of an efficient quantum circuit (after tracing out non-output qubits.) We need only show that the verifier's state is always close to the output of some efficient quantum circuit (assuming an honest prover).
Let P be the honest prover for some protocol. Then P ′ is the honest prover for the corresponding real protocol, where the operations of P ′ are those of P , transformed by R (2) 2 (·). Suppose that a dishonest verifier V ′ can use P ′ as a subroutine to produce a state that V ′ could not create efficiently alone. For our purposes we do not restrict V ′ to real operations, noting that this only increases V ′ 's power.
We now use the usual argument, but applied to P ′ rather than the verifier. In a suitable basis P ′ 's operations commute with measuring P ′ 's "extra" qubit, and hence P ′ 's actions look like either those of the original prover P or the complex conjugate P * . We first suppose that V ′ prepares the prover's "extra" qubit. Then the verifier can either produce some state ρ 0 , by choosing that P ′ perform the original protocol, or some other state ρ 1 by choosing that P ′ perform the complex conjugate protocol, or some mixture of ρ 0 and ρ 1 . Since we assume that the resulting state cannot be prepared by V ′ efficiently alone, either ρ 0 or ρ 1 must also have this property. But this contradicts the assumption that the original protocol (and by symmetry the complex conjugate protocol) is from QSZK. The case where P ′ prepares the "extra" qubit is similar, except the state produced is always 1 2 (ρ 0 + ρ 1 ).

Conclusions
We have demonstrated that a wide variety of important quantum complexity classes are unchanged when the quantum operations are restricted to be over a real Hilbert space. The arguments that we use are quite general and could be applied to other complexity classes as well. A The single party real simulation is not sufficient to show QIP(k) = QIP R (k).
Suppose we make the following argument: the prover and verifier take turns performing operations, so we really only need one "extra" qubit, and they can pass it back and forth along with the messages. We can thus transform the states and all operations according to R(·). Clearly the completeness is the same, but what about soundness? Here we give an example problem with an instance not in the language where in the original protocol the verifier accepts with probability arbitrarily close to 0, but for the real simulation with only one "extra" qubit there is a cheating prover that forces verifier to always accept. The problem we consider is quantum state distinguishability. This is a complete problem for the class QSZK [Wat02]. We are given two efficient quantum circuits Q 0 and Q 1 that produce outputs ρ 1 and ρ 2 after tracing out non-output qubits, and the promise that either ||ρ 1 − ρ 2 || 1 ≤ α (55) or ||ρ 1 − ρ 2 || 1 ≥ β with α, β ∈ [0, 1] and α < β 2 . The problem is to determine which of these is true. The basic solution to this problem is to prepare one of ρ 0 or ρ 1 at random and send it to the verifier. The prover attempts to decide which state was sent, and sends a guess to the verifier. The verifier the checks whether the prover was correct. If the prover is very often correct over many instances of this game, then the states must be far apart in the trace norm and the verifier accepts. If the states are close together then the prover will be correct about half of the time and the verifier rejects. 4 Now we consider two unitaries U 0 and U 1 which differ only in their global phase. In particular, U 0 | 0 . . . 0 = iU 1 | 0 . . . 0 . Clearly the two states must be completely indistinguishable since ρ 0 = ρ 1 . However, if we apply the real simulation and pass the "extra" qubit to the prover, the states are orthogonal and the prover can distinguish them perfectly! Indeed, according to lemma 1 A closer inspection reveals that R(U 0 | 0 . . . 0 ) = (X ⊗I)R(U 1 | 0 . . . 0 ). Thus the prover needs only to measure the "extra" qubit in the Z basis to distinguish the states. The reason that the previous proof fails for this construction is that the prover's measurement on the "extra" qubit does not commute with measurement in the V † ZV basis, so we can no longer view the verifier's actions as a mixture of the original and complex conjugate protocols (they share the "extra" qubit). In the construction with two "extra" qubits the verifier keeps one qubit, so all operations, both the verifier's and the prover's, commute with measurement in the V † ZV basis.