9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # A Theory of Physical Quantum Computation The Quantum Computer Condition

arXiv:quant-ph/0507141v2 20 Jul 2005

A Theory of Physical Quantum Computation: The Quantum Computer Condition

Gerald Gilbert, Michael Hamrick and F. Javier Thayer

Quantum Information Science Group? ? Mitre 260 Industrial Way West, Eatontown, NJ 07724 USA

Abstract. In this paper we present a new uni?ed theoretical framework that describes the full dynamics of quantum computation. Our formulation allows any questions pertaining to the physical behavior of a quantum computer to be framed, and in principle, answered. We refer to the central organizing principle developed in this paper, on which our theoretical structure is based, as the Quantum Computer Condition (QCC), a rigorous mathematical statement that connects the irreversible dynamics of the quantum computing machine, with the reversible operations that comprise the quantum computation intended to be carried out by the quantum computing machine. Armed with the QCC, we derive a powerful result that we call the Encoding No-Go Theorem. This theorem gives a precise mathematical statement of the conditions under which fault-tolerant quantum computation becomes impossible in the presence of dissipation and/or decoherence. In connection with this theorem, we explicitly calculate a universal critical damping value for fault-tolerant quantum computation. In addition we show that the recently-discovered approach to quantum error correction known as “operator quantum error-correction” is a special case of our more general formulation. Our approach furnishes what we will refer to as “operator quantum fault-tolerance.” In particular, we show how the QCC allows one to derive error thresholds for fault tolerance in a completely general context. We prove the existence of solutions to a class of time-dependent generalizations of the Lindblad equation. Using the QCC, we also show that the seemingly di?erent circuit, graph- (including cluster-) state, and adiabatic paradigms for quantum computing are in fact all manifestations of a single, universal paradigm for all physical quantum computation.

? Research ? E-mail

supported under MITRE Technology Program Grant 51MSR211. address: {ggilbert, mhamrick, jt}@mitre.org

1

2

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

Contents 1. Introduction 2. The Quantum Computer Condition 3. The Encoding No-Go Theorem 4. Quantum Components 5. Uni?ed Treatment of Quantum Computing Paradigms 6. Error Thresholds and Fault Tolerance 7. Conclusions Appendix A. Banach Spaces of Operators Appendix B. Completely Positive Maps and Fundamental Solutions Appendix C. Solving the Ersatz Quantum Computer Condition References 2 3 12 18 21 30 36 37 37 44 44

1. Introduction The promise inherent in quantum computing has stimulated a tremendous explosion of interest in the research community. Voluminous research has been carried out directed to many di?erent problems associated with the development and properties of quantum computational algorithms. Parallel to these e?orts, substantial investigations have been devoted to the problems associated with the development of actual quantum computing machines. A rigorous and fully general theory that connects quantum computing algorithms and quantum computing machines would be of considerable value. In this paper we present a new uni?ed theoretical framework that describes the full dynamics of quantum computation. Our formulation allows any questions pertaining to the physical behavior of a quantum computer to be framed, and in principle, answered. We refer to the central organizing principle developed in this paper, on which our theoretical structure is based, as the Quantum Computer Condition (QCC), a rigorous mathematical statement that connects the irreversible dynamics of the quantum computing machine, with the reversible operations that comprise the quantum computation intended to be carried out by the quantum computing machine. The actual dynamics of the system that we intend to use as a practical quantum computing machine are those of an open quantum mechanical system, burdened with various dissipative and/or decoherence e?ects. The QCC provides a set of mathematical constraints that must be satis?ed by a physical system if we intend to use that system as a quantum computing machine. Armed with the QCC, we derive a powerful result that we call the Encoding No-Go Theorem. The Encoding No-Go theorem gives a precise mathematical statement of the conditions under which fault-tolerant quantum computation becomes impossible in the presence of dissipation and/or decoherence. We provide a rigorous de?nition of damping, which includes the phenomena of dissipation and decoherence, and explicitly calculate a universal critical damping value for fault-tolerant quantum computation. This fundamental theorem has deep formal signi?cance. Moreover, it also furnishes criteria for solving diverse problems associated to actual physical quantum computer realizations, such as determining which practical design choices for quantum computing machines are not viable.

A THEORY OF PHYSICAL QUANTUM COMPUTATION

3

In addition we show that the recently-discovered approach to quantum error correction known as “operator quantum error-correction” (OQEC) is actually a special case of our general formulation. Our approach furnishes what we will refer to as “operator quantum fault-tolerance” (OQFT). In particular, we show how the QCC allows one to derive error thresholds for fault tolerance in a completely general context. In this paper we de?ne the concept of a quantum component, which allows us to study realistic implementations of quantum computers, in which decoherence and/or dissipative e?ects are present, using a dynamical equation of motion suitable for describing an open quantum system. By using the QCC, we are able to reconcile the apparent contradiction between: (1) the fact that quantum computations are speci?ed by unitary transformations, the associated dynamics of which are intrinsically reversible, and (2) the fact that quantum computers, qua practical machines, are inevitably characterized by irreversible dynamics. The reconciliation suggests an analogy with the ?uctuation-dissipation theorem, which relates irreversible dynamics to equilibrium properties in a large class of physical systems. In this paper we present an existence proof for fundamental solutions to useful classes of time-dependent generalizations of the Lindblad equation. This provides a useful tool in analyzing a wide variety of open quantum mechanical systems. Our framework is su?ciently general to encompass, and describe in a uni?ed manner, the currently-known “paradigms” for quantum computation, including the circuit-based (“two-way computing”) paradigm, the graph state-based (“one-way computing”) paradigm and the adiabatic quantum computer paradigm. Using the QCC, we show by explicit construction that these seemingly di?erent paradigms are in fact all manifestations of a single, universal paradigm for all physical quantum computation.1 2. The Quantum Computer Condition 2.1. Introduction. In this section we present the Quantum Computer Condition, a rigorous mathematical statement of the constraints that determine the viability of any practical quantum computing machine. To achieve the goal of practical quantum computation we must produce an actual physical device that implements a predetermined unitary operator U acting on some Hilbert space. The Quantum Computer Condition relates the unitary operator representing a quantum computation to the actual physical device intended to perform that computation. The speci?cation of U de?nes ideally the quantum computation to be performed by the quantum computing machine. Generically, the result of a quantum computation, U , is then used to carry out the probabilistic evaluation of some classical function. The complete quantum computation comprises a number of elements, including ? Preparation of a quantum state for initialization. ? Measurement of a quantum state for readout.

1 In the particular case of the graph state-based paradigm (which includes cluster state-based models), we not only show that the paradigm is a manifestation of the unifying picture provided by the QCC, but also introduce a de?nition of graph state-based quantum computers that generalizes the graph state models previously de?ned in the literature.

4

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

? Various tasks that can be performed by classical computers, such as preprocessing of the data, or postprocessing of the output into some humanly comprehensible form. However, the above list of elements are not what is “important” about quantum computers. Rather: ? The distinctive element of quantum computation is the “ability to perform quantum gates”(c.f. [23], §4.6). Mathematically, a quantum gate is a unitary (hence reversible) operator U acting on a Hilbert space. The formally de?ned “gates,” as such, are not “devices.” They are concepts: they don’t implement themselves. A machine is required to physically implement the abstractly de?ned unitary transformation. The actual, physical computing device intended to implement the transformation is described mathematically by a completely positive trace-preserving map, P , that transforms the input state to the output state. We will refer to a physically realizable device intended to implement an ideal quantum computation as a quantum component. In this paper we study realistic quantum components, in which decoherence and/or dissipative e?ects are present, using a dynamical equation of motion suitable for describing an open quantum system.2 We must reconcile the fact, and apparent paradox, that a non-reversible mapping, P , is used to “implement” a reversible one, U. 2.2. The Motivation of the Quantum Computer Condition. Mathematically, a quantum computation is a unitary operator U in the unitary group of a Hilbert space. A quantum component is described by a completely positive trace-preserving map P which maps the set of trace class operators on the Hilbert space to itself. The map P accounts for decoherence and dissipation, as well as unitary evolution. We will subsequently discuss in more detail the actual form for P . In our analysis we will consider the action of P on density matrices ρ → P · ρ rather than on state vectors (and correspondingly the action of U on density matrices ρ → U ρU ? , rather than the action of U on state vectors). This is because, due to the presence of decoherence and/or dissipation, our system will almost always evolve into a mixed state, which can only be described by a density matrix ρ.3 In order to motivate the Quantum Computer Condition (QCC), let us ?rst consider the abstractly-de?ned quantum computation itself, prescribed by the unitary

2In order to analyze the e?ects of dissipation and/or decoherence one must use some method of approximating the dynamics of the degrees-of-freedom comprising the rest of the universe “outside of” the quantum computer. This is of course because the complete, detailed, exact analytical solution to the Schr¨ odinger equation of the universe, for all degrees-of-freedom, is not known. One reasonable approach is to construct a Lindblad-type equation, based on a presumption of underlying Markovian dynamics, in which environment degrees-of-freedom are traced over in such a way as to result in a ?rst-order (in time) di?erential equation. In this paper, for de?niteness, we utilize a generalized Lindblad-type equation to describe the environment: this is used merely in order to exemplify how one may take into account the e?ects of dissipation and/or decoherence. However, most of the results in our paper, including the crucial Encoding No-Go Theorem, are independent of this choice, and in particular are independent of the assumption of underlying Markovian dynamics. 3Other reasons for utilizing density matrices rather than state vectors include the generic importance in quantum information theory of trace-preserving completely positive maps (which restrict to transformations on density matrices), and the useful algebraic and analytic properties of density matrices (density matrices for instance form a weak-? compact convex set).

A THEORY OF PHYSICAL QUANTUM COMPUTATION

5

operator U . This is assumed to be given, and is represented by (1) abstract computation : U ρU ? .

The action of the quantum component intended to e?ect the computation is represented by (2) practical implementation : P · ρ .

Motivated by the notion of having the machine implement the computation, if we were to require that the identity (3) P · ρ = U ρU ?

hold for all density states ρ, then the action of P would in fact be identical to the action of the unitary operator. This would imply that P preserves von Neumann entropy ([32], §5.3), and hence actually models a system with neither decoherence nor dissipation, which is not the case for a practical quantum computing machine. Thus, equation (3) cannot furnish the correct constraints for realistic quantum computation. We will accordingly refer to equation (3) as the ersatz quantum computer condition (E QCC).4 More realistically, taking into account the inevitable presence of decoherence, we can require that (3) hold for some restricted set of density states. In this case, the solution set will correspond to decoherence-free subspaces. In order to analyze this, we must carefully distinguish between the two di?erent Hilbert spaces that arise in this problem. The abstract quantum computation is de?ned on the Hilbert space of logical quantum states, Hlogical , so that we have (4) U : Hlogical → Hlogical . In contrast, the presence of decoherence (which a?ects the actual device) necessitates that the completely positive trace-preserving map P (which represents the actual device) is associated to a di?erent Hilbert space, Hcomp , the states of which are referred to as computational quantum states. The decoherence-free subspace is contained within Hcomp . (The speci?c decoherence is accounted for in the explicit form of P ). As noted above, a consequence of the decoherence is that P operates on density matrices rather than on state vectors. Letting T(Hcomp ) be the Banach space of trace-class operators on Hcomp , we have (5) P : T(Hcomp ) → T(Hcomp ).

In order to replace E QCC (equation (3)) with an equation that properly incorporates decoherence e?ects so that it can be used to determine decoherence-free subspaces, we must introduce suitable encoding and decoding maps that connect the relevant Hilbert spaces. We can hope to ?nd an encoding operator Menc de?ned on a space of logical inputs and a decoding operator Mdec with values in a space of logical outputs, the actions of which are given by (here T(Hlogical ) is the Banach space of trace-class operators on Hlogical , analogous to T(Hcomp )) (6) Menc : T(Hlogical ) → T(Hcomp )

4Although the E QCC does not describe practical quantum computing machines, we note that it can be shown that in the ?nite-dimensional case, the set of ρ which satisfy (3) is an algebra AP,U which depends on both P and U . The details of how one explicitly obtains the algebra AP,U of solutions to (3) are given in Appendix C.

6

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

and (7) (8) such that (cf equation (3)) Mdec : T(Hcomp ) → T(Hlogical ), Mdec(P · (Menc(ρ))) = U ρU ?

for all logical inputs ρ. We will refer to equation (8) as the “encoded ersatz quantum computer condition (eE QCC).5 The existence of the encoding and decoding maps Menc and Mdec is a consequence of the presumed existence of an associated decoherence-free subspace of Hcomp , of dimension greater than or equal to the dimension of Hlogical . The meaning of eE QCC given in eq.(8) is as follows. Given a chosen quantum computation, U , we wish to construct a physical “machine,” P , that implements U . In order to do this we must ?nd encoding and decoding maps Menc and Mdec such that the equation is satis?ed for all ρ. This is a crucial di?erence between eqs.(8) and (3): requiring that eq.(3) holds for all ρ implies a machine that preserves von Neumann entropy, does not dissipate heat and does not decohere, and thus does not describe a practical quantum computing device. In contrast, eq.(8) holds for all states ρ, but does so by making use of the encoding and decoding operators to map to a decoherence-free subspace. The eE QCC (eq.(8)) formally holds for all density states ρ, similar to eq.(3), but the use of the encoding and decoding maps in eq.(8) e?ectively con?nes the solution to a restricted set in Hcomp . However, eq.(8) does not in general provide an acceptable condition to connect the dynamics of a practical quantum computing device to the constraints implied by the unitary operator U that de?nes the abstract quantum computation. This is because the formulation presented by (8) does not address situations in which residual errors cannot be completely eliminated, even with the use of decoherencefree subspaces, and/or other error correction methods [20], [28]. To recapitulate, eq.(3) describes a quantum computer that performs the required computation U , but only if the implementing device, described by the completely positive map P , neither dissipates heat nor decoheres. We thus reject this expression as a viable quantum computer condition because it describes a system that is e?ectively impossible to achieve. In contrast, eq.(8) describes a quantum computer that performs the required computation U , but only if the device described by the completely positive map P implements the required decoherence-free subspace with absolutely no residual errors. This does not provide a su?ciently general formulation: we need to consider situations in which residual errors cannot be completely eliminated. 2.3. The Presentation of the Quantum Computer Condition. We wish to allow for the likelihood that, even if a decoherence-free subspace can be found, and even if error correction procedures are applied, there will still be residual errors characterizing the operation of the quantum computer. Such a situation may arise even if error correction is correctly applied: for instance, in the application of concatenated error codes, one iterates the concatenation process until the error probability is reduced to a value that is deemed “acceptable” [28], [24]. This ?nal error probability, though small, is not exactly zero. The important point is that

5Note that no encoding map is required on the right-hand side of equation (8) since the unitary U by de?nition acts on Hlogical .

A THEORY OF PHYSICAL QUANTUM COMPUTATION

7

it is prudent to write down our quantum computer condition so as to re?ect the inevitable survival of some amount of residual error. In order to quantify the degree to which the actual computational device, represented by P , cannot exactly (because of residual error) implement the ideal quantum computation, represented by U , we consider the following di?erence (cf eq.(8)) (9) Mdec (P · (Menc(ρ))) ? U ρU ? .

We now compute for this di?erence a suitable norm on matrices (this norm is made more precise below), as (10) Mdec (P · (Menc(ρ))) ? U ρU ? .

This quantity is of fundamental importance: it is a measure of the inaccuracy of the implementation of U by P . It tells us how well a practical quantum computing device actually implements an ideally-de?ned quantum computation. We will refer to the scalar quantity given by (10) as the implementation inaccuracy associated to the pair U and P . In connection with this, we introduce a parameter, α, to specify the maximum tolerable implementation inaccuracy, so that we have (11) Mdec(P · (Menc(ρ))) ? U ρU ? ≤ α.

2.3.1. Formal Statement of the Quantum Computer Condition (QCC). Motivated by the above considerations, we now introduce and formally de?ne an inequality of fundamental importance in the theory of quantum computation that we will refer to as the Quantum Computer Condition. We will formally designate this condition by QCC(P, U, Menc , Mdec, α). In the following, we will impose no constraint on the dimensionality of the Hilbert space, and in particular we allow Hilbert spaces of in?nite dimensions. Let U be a unitary on Hlogical and P be a trace-preserving completely positive map on T(Hcomp ). Let Menc : T(Hlogical ) → T(Hcomp ) and Mdec : T(Hcomp ) → T(Hlogical ) be completely-positive, trace-preserving encoding and decoding maps (with no further restrictions of any kind on the encoding and decoding maps). The Quantum Computer Condition, QCC(P, U, Menc, Mdec , α), holds i? for all density matrices ρ ∈ T(Hlogical ), we have (12) Mdec(P · (Menc (ρ))) ? U ρU ?

1

≤ α,

where T(Hcomp ) and T(Hlogical ) are the Banach spaces of trace-class operators on Hcomp and Hlogical , respectively, and · 1 is the Schatten 1-norm de?ned in Appendix A. It should be noted that an alternate measure of distance between density matrices to that provided by the Schatten 1-norm is given by the ?delity function [23]. One could write an alternate form of the QCC in terms of the ?delity that would be essentially equivalent to the form of the QCC given in (12) above. Using an obvious notation to denote the QCC written with each of these de?nitions of distance, the two forms are related as follows. Given a quartet {P, U, Menc, Mdec}, one can show that if QCCSchatten(P, U, Menc , Mdec, α) is satis?ed, then the ?delity-based version of QCC given by QCC?delity (P, U, Menc, Mdec , α′ ) is also satis?ed, where α′ = α′ (α) is a function of α. The form of QCC based on the Schatten 1-norm given above in (12) is more convenient for our purposes for a number of mathematical reasons, including the fact that that the ?delity, as such, is not a proper norm. For instance, the statement and proof of the Encoding No-Go Theorem carried out in

8

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

§3 below are more conveniently presented making use of the form of the QCC based on the Schatten norm. Note that Menc and Mdec do not represent physical operations: all physical operations are carried out by the quantum component P . If the proper distinction between these maps and P is not observed, one could include the entire computation in the de?nition of the maps, with the absurd conclusion that any quantum computation could be performed in the absence of any real hardware. 2.3.2. Some implications of the QCC. The QCC is a remarkably powerful expression. It constitutes a kind of “master expression” for physical quantum computation. The inequality (12) concisely incorporates a complete speci?cation of the full dissipative, decohering dynamics of the actual, practical device used as the quantum computing machine, a speci?cation of the ideally-de?ned quantum computation intended to be performed by the machine, and a quantitative criterion for the accuracy with which the computation must be executed given the inevitability of residual errors surviving even after error correction has been applied. Making use of the QCC, one can state and prove (we do this is in §3, the next section of the paper) a fundamental and powerful theorem in the subject of quantum computing, the Encoding No-Go Theorem. This no-go theorem gives a precise mathematical statement of the conditions under which fault-tolerant quantum computation becomes impossible in the presence of dissipation and/or decoherence. Apart from its formal signi?cance, the theorem can be used to compare di?erent proposed physical approaches to actually building a quantum computing machine, with the no-go condition furnishing a criterion for the practical engineering viability of various choices. As a further indication of the power and general applicability of the QCC, we show that one can apply it to the known, seemingly distinct “paradigms” for quantum computing, based on (1) the use of quantum circuits built up out of quantum gates (the circuit-based paradigm, or “two-way” quantum computing), (2) the use of graph states or cluster states (the graph state-based paradigm, or “one-way” quantum computing) and (3) the use of specially chosen Hamiltonians describing adiabatic dynamics (the adiabatic quantum computer paradigm). The QCC allows one to show that these apparently di?erent de?nitions of a quantum computer are in fact manifestations of the same underlying formulation: there is only one paradigm for quantum computers. The application of the QCC to di?erent quantum computing paradigms is discussed in §5. The encoding-decoding pair Menc and Mdec that appear in the QCC are de?ned quite generally as completely positive trace-preserving maps. This formulation is su?ciently general to encompass all possible encodings associated with standard quantum error correction (QECC) techniques, decoherence-free subspaces and noiseless subsystems. More generally still, we show below in §2.3.3 that the recently discovered approach known as “operator quantum error correction” (OQEC) is in fact a special case of our more general QCC formulation. In addition the QCC can be used to extend OQEC to what we will refer to as “operator quantum faulttolerance” (OQFT). In particular, we show in §6 below how the QCC allows one to derive error thresholds for fault tolerance in a completely general context.

A THEORY OF PHYSICAL QUANTUM COMPUTATION

9

Another signi?cant consequence of the QCC is that it resolves the apparent paradox that the quantum computations we wish to perform are de?ned by reversible operators, but the actual devices that we must use to execute the computations are necessarily described by irreversible maps. We note that this is reminiscent of the ?uctuation-dissipation theorem, which relates irreversible dynamics to equilibrium properties in a large class of physical systems. Inspection of (12) reveals that the paradox is resolved through the transformations provided by the encoding and decoding maps associated to the QCC. Roughly speaking, reversible behavior of the actual device is enabled only on the code subspace de?ned by Menc and Mdec . Note that if one describes quantum computing solely in terms of the unitary transformations that de?ne the computations, it is not too surprising that the resulting computational model is in some way “powerful.” After all, unitary transformations on ?nite dimensional spaces include such powerful operations as the discrete Fourier transform which are known to play an important role in number theoretic problems. Rather than regarding the power of the ideally-de?ned quantum computation as the remarkable thing, the truly remarkable thing would be the construction of an inherently irreversible device that actually implements the reversible, unitary map to a speci?ed level of accuracy. It is this possibility that our QCC expresses and makes mathematically precise. The QCC can thus be used to formulate and prove assertions about the physical solvability of particular computational problems. 2.3.3. Operator quantum error correction (OQEC) as a special case of QCC. The recently developed theory of operator quantum error correction [18], [19] uni?es many apparently disparate approaches to the practical problem of dealing with errors in quantum information. Among these approaches are quantum error correction, decoherence free subspaces and noiseless subsystems. Here we show that OQEC is in fact a special case of the general statement of the QCC. In this section we demonstrate that the entire formalism of OQEC can be obtained from QCC by choosing Menc and Mdec as described below, and by setting setting U = I and α = 0 in the QCC, so that the reduction QCC → OQEC is given by: (13) QCC(P, U, Menc , Mdec, α) → QCC(P, I, Menc , Mdec, 0) . In the scheme of OQEC, the techniques of (standard) quantum error correction, decoherence free subspaces and noiseless subsystems are subsumed under the uni?ed concept of “correctability.” This is de?ned formally as follows. Let Hcomp be a Hilbert space with a decomposition Hcomp = H A ? H B ⊕ K , where H A , H B and K are discussed in the following paragraph. We identify this as the computational space Hcomp of this paper because, as we shall see below, it describes the space on which the real physical processes of error and recovery operate. Let S be the semigroup given by (14) S = {σ ∈ L(Hcomp ) : ?σ A ∈ L(H A ), ?σ B ∈ L(H B ), such that σ = σ A ? σ B } , where L(·) is the space of bounded operators6 on the appropriate Hilbert space, with the operator norm, and let E and R be completely-positive, trace preserving maps

6In §2.3.3 of this paper we assume (following [19]) that all Hilbert spaces are ?nitedimensional. Although not discussed in [19], it is important to note that if one makes this

10

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

on L(Hcomp ) corresponding to error processes and recovery processes, respectively. We say that S is correctable for E i? (15) where PS e?ectively projects density matrices onto the H A ? H B subspace of Hcomp . Physically speaking, H B is the Hilbert space which carries the information to be protected from errors, the “noiseless subsystem,” while H A is the Hilbert space on which the errors are permitted to operate freely, the “noisy subsystem.” K is the orthogonal complement of H A ? H B in Hcomp and is simply projected out by PS . Thus, in (15), TrA σ represents the quantum information which is to be protected. The left side of (15) describes the e?ect of allowing errors to operate on the full state σ , and then applying recovery procedures. (The projection and the trace simply extract the state of the noiseless subsystem.) According to (15), correctability thus means that the recovery procedure does in fact recover the state of the noiseless subsystem, TrA σ , without error. As we now show, the de?nition of correctability is actually a special case of the QCC. Note ?rst that correctability, as de?ned above, applies to a quantum channel as opposed to a quantum computer. It describes the transportation of a quantum state in a noisy environment as opposed to the “processing” of a quantum state so as to implement a quantum computation. In order to make the connection with the QCC, we may therefore think of the quantum channel as a quantum computer that implements the identity operation: (16) U = IHlogical In the de?nition of correctability, the part of the state containing the information of interest is recovered without error. This corresponds to taking α = 0 in the QCC. Note that, as discussed above, this is not practically achievable for quantum computers. This is less obviously an issue for the theory of operator error correction as currently formulated [18], [19], since that theory addresses a relatively circumscribed set of circumstances in which one is concerned with transporting quantum states rather than implementing a quantum computation. In particular, the error process E , which is speci?ed in advance, only operates once on the quantum state being transported. Error processes associated with the constituent parts of quantum computers operate each time the constituent part operates on the the quantum state being processed. The problem of fault tolerant quantum computation is inherently more complex than the problem of error correction/protection for a quantum channel. We will discuss this more fully in §6 below. Setting U = I and α = 0 in the quantum computer condition, we obtain (17) or (18) where ρ ∈ L(Hlogical ).

7

?σ ∈ S, (TrA ? PS ? R ? E ) σ = TrA σ ,

(Mdec ? P ? Menc) ρ ? ρ

1

= 0,

(Mdec ? P ? Menc ) ρ = ρ ,

assumption, there is then no need to distinguish between bounded operators in L(·) and traceclass operators in T (·). This distinction is important in the other sections of our paper where we allow Hilbert spaces of in?nite as well as ?nite dimensionality. 7As noted in the previous footnote, we are assuming in §2.3.3 that H logical is ?nitedimensional.

A THEORY OF PHYSICAL QUANTUM COMPUTATION

11

We now proceed to de?ne the encoding map Menc. For this purpose we de?ne a map Wenc : L(Hlogical ) → L(H B ) that encodes the logical quantum state ρ in a state σ B of the noiseless subsytem. We further de?ne a map Wadj (σ A ) : L(H B ) → L(H A ? H B ) that adjoins an arbitrary state σ A of the noisy subsystem to the state σ B , that is (19) Wadj (σ A ) : σ B → σ ≡ σ A ? σ B Menc ≡ Wadj (σ A ) ? Wenc

We then de?ne the full encoding map that appears in the QCC as follows: (20)

The map P characterizes the dynamics of the physical computer, which in this case is just the (noisy) channel followed by the recovery procedure: (21) P ≡R?E

We note that the current formulation of the theory of operator quantum error correction implicitly assumes that the recovery process R can be implemented without error, even though this requires, in general, that coherent operations be performed on entangled quantum states. Once again, the emphasis on error correction alone avoids the more di?cult issue of achieving true fault tolerance. Finally we de?ne the decoding map as: (22)

?1 Mdec = Wenc ? TrA ? PS ,

which extracts the state of the noiseless subsystem and decodes it to obtain a state in the logical space L(Hlogical ). With the above de?nitions, the QCC becomes (23)

?1 Wenc ? TrA ? PS ? R ? E ? Wadj (σ A ) ? Wenc ρ = ρ .

Applying Wenc to both sides, and recalling that Wenc ρ = σ B = TrA σ , we obtain (24) TrA ? PS ? R ? E ? Wadj (σ A ) ? Wenc ρ = TrA σ .

Noting that Wadj (σ A ) ? Wenc ρ = σ , we obtain the correctability condition of [18], [19]: (25) (TrA ? PS ? R ? E ) σ = TrA σ .

In summary, we have shown that the formalism of operator quantum error correction actually arises as a special case of an underlying de?nition of physical quantum computation given by the QCC. In addition, examination of operator quantum error correction (OQEC) from the perspective of the QCC reveals limitations and restrictions implicit to the formalism of operator quantum error correction, and inherited from the previously known, standard approaches to error correction (QECC). These limitations render direct application of either OQEC or QECC to questions of fault tolerance somewhat problematic, whereas the QCC approach is more immediately applicable. Thus, the QCC enables one to generalize OQEC to operator fault tolerance (OQFT).

12

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

3. The Encoding No-Go Theorem 3.1. Introduction. Armed with the QCC, in this section we state and prove a theorem of crucial importance in the theory of physical quantum computation. This is the Encoding No-Go Theorem, which gives a precise mathematical statement of the conditions under which fault-tolerant quantum computation becomes impossible in the presence of damping. Damping, for which we provide a mathematically rigorous de?nition below, includes the e?ects of dissipation and decoherence. The No-Go theorem for a completely positive trace-preserving map P corresponding to a putative quantum computing device then asserts that, in the presence of su?cient damping, the quantum computer condition QCC(P, U, Menc, Mdec , α) (cf (12)) cannot be satis?ed for any encoding-decoding pair, unless Hlogical has dimension 1: there is then e?ectively no quantum computer. (In the case that dim Hlogical = 1 we are of course unable to de?ne a meaningful quantum computation at all.) As part of the No-Go Theorem we explicitly calculate a universal critical damping value for fault-tolerant quantum computation. We precisely state and prove this theorem in the remainder of §3. 3.2. Encoding and Decoding Maps. An encoding-decoding pair are completely positive, trace-preserving maps Menc : T(Hlogical ) → T(Hcomp ) (26) Mdec : T(Hcomp ) → T(Hlogical ).

Encoding-decoding pairs provide the link between a completely positive map P : T(Hcomp ) → T(Hcomp ) corresponding to a physical device and a unitary operator U : Hlogical → Hlogical corresponding to a quantum computation. We will place no further restrictions on encoding-decoding pairs. Now, suppose Menc, Mdec is an t encoding-decoding pair. Then the adjoint maps Mt dec , Menc are unit preserving completely positive maps. (Adjoint maps of completely positive maps are de?ned in (132) in Appendix B.) 3.3. Damping and γ -damping. Dissipative and decohering e?ects are consequences of damping. To begin the development of the No-Go Theorem, we introduce a mathematically precise de?nition of the damping of a quantum mechanical system, to which we refer as γ -damping. Definition 3.1. Let H be a Hilbert space. A completely positive tracepreserving map P : T(H ) → T(H ) is γ -damped i? there is an abelian von Neumann algebra A ? L(H ) such that for all T ∈ L(H ), there is an ST ∈ A such that (27) P t (T ) ? ST

∞

≤γ T

∞,

where the operator norm · ∞ is de?ned in Appendix A. Note that larger values of γ correspond to less damping of the system. To make contact with the physically intuitive notion of damping, we apply this de?nition to the example of the simple harmonic oscillator subject to phase damping. For such an harmonic oscillator, the ij th element of the density matrix, 2 ρij = i|ρ|j , decays exponentially as e?κ(i?j ) , where we are working in the basis of energy eigenstates identi?ed by the labels i and j . The quantity κ is characteristic of the speci?c oscillator and its coupling to the environment. The completely positive map P transforms the initial, general density matrix for the system into a density matrix with exponentially-decaying o?-diagonal elements. Under the in?uence of

A THEORY OF PHYSICAL QUANTUM COMPUTATION

13

damping, as the o?-diagonal states of the oscillator decay and approach zero, the density matrix converges to a diagonal density matrix in the {ij } basis speci?ed above. This is true for all initial con?gurations of the oscillator, and thus the damping process tends to an abelian set of ?nal con?gurations. (The damping parameter κ that characterizes the decay of the o?-diagonal elements of the density matrix is related to the quantity γ that appears in (27). As noted above, larger values of γ correspond to less damping and hence smaller values of κ.) 3.4. No-Go Theorem for Encodings. We now state the main result of §3: the Encoding No-Go Theorem. Theorem 3.2 (The Encoding No-Go Theorem). Suppose that QCC(P, U, Menc , Mdec, α) holds. If P : T(Hcomp ) → T(Hcomp ) is √ γ -damped and 2γ + α < 2/4, then Hlogical has dimension 1. To prove the Encoding No-Go Theorem, we ?rst derive in §3.5 a number of general mathematical results on completely positive maps. We then apply these speci?cally to obtain a proof of the Encoding No-Go Theorem in §3.6 below. 3.5. Completely Positive Maps with Abelian Factorizations. We begin with the following lemma, which furnishes a superoperator version of the de?nition of γ -damping. For any abelian von Neumann algebra A ? L(H ) there is a unitpreserving completely positive projection operator EA : L(H ) → A. This fact is elementary, but also follows from injectivity [7] of such algebras, in the case H is separable. Lemma 3.3. If P is γ -damped, A is as given in De?nition 3.1 and EA : L(H ) → A is a unit-preserving completely positive projection mapping EA : L(H ) → A, then (28) P t (T ) ? EA P t (T ) P t (T ) ? EA P t (T )

∞ ∞

≤ 2γ T

∞

∞.

Proof. Note that EA is a linear mapping of norm ≤ 1 and thus (29) ≤ P t (T ) ? ST ≤γ T

∞ ∞,

as claimed.

≤ 2γ T

+ EA ST ? EA P (T )

+ ST ? EA P t (T )

t ∞

∞

In the remainder of this section we prove an important technical result used in the proof of the no-go theorem, namely that completely positive maps F : L(H ) → L(H ), which factor through completely positive maps into abelian von Neumann algebras, cannot be used to approximate unitary √ operators U on H if dim(H ) ≥ 2. More precisely, we will show that for any β < 2/4, there is at least one non-zero operator T for which (30) We ?rst de?ne what it means for a completely positive map to factor through an abelian von Neumann algebra: Definition 3.4. Let A be a C? -algebra with a multiplicative unit. A unit preserving completely positive map F : A → A has an abelian factorization (or brie?y is abelian factorizable) i? there is an abelian von Neumann algebra B and U ? T U ? F (T )

∞

≥β T

∞.

14

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

unital completely positive maps Q : A → B, R : B → A such that F is the composition R ? Q. If F : L(H ) → L(H ) is abelian factorizable, then it follows from the de?nition that for any unit-preserving completely positive maps Q, R, the completely positive map Q ? F ? R is abelian factorizable. We begin by providing a characterization of abelian factorizable maps. Proposition 3.5. Let A be an arbitrary C? -algebra with multiplicative unit. A unit preserving completely postive map F : A → A factors through a ?nitedimensional abelian von-Neumann algebra i? there are unit preserving positive linear functionals ρ1 , . . . , ρm ∈ A? and positive elements G1 , . . . , Gm ∈ A of norm m ≤ 1, such that i=1 Gi = I and

m

(31)

F (T ) =

i=1

ρi (T )Gi

?T ∈ A.

Proof. We ?rst note that positive maps from an abelian C? -algebra or into an abelian C? -algebra are automatically completely positive (see [29],[6]). Thus the map F given by Equation (31) is completely positive. Let B, Q : A → B, R : B → A as in De?nition 3.4, but with B ?nite dimensional and let E1 , . . . , Em be the minimal non-zero projections of B. Then

m m m

(32)

F (T ) = R

i=1

Ei Q(T )Ei

=R

i=1

ρi (T )Ei

=

i=1

ρi (T )R(Ei ).

Letting Gi = R(Ei ),

m m m

(33)

i=1

Gi =

i=1

R(Ei ) = R

i=1

Ei

= I.

This completes the proof. In general, unit-preserving completely positive maps with arbitrary abelian factorizations can be approximated by maps of the form (31). Proposition 3.6. If a completely positive map F : A → A has an abelian factorization, then there is a generalized sequence of maps {Fκ }κ∈K each having m the form Fκ (T ) = i=1 ρi (T )Gi which converges to F in the point-norm topology, that is for each T ∈ A, Fκ (T ) → F (T ) in the norm of A. Proof. Let B, Q : A → B, R : B → A as in De?nition 3.4. Given T1 , . . . , Tm ∈ A, let B0 be a ?nite dimensional abelian von-Neumann subalgebra of B and E a linear projection operator8 B → B0 such that (34) Q(Ti ) ? E(Q(Ti ))

∞

≤ ?.

∞

Since Q is contractive, it follows that (35) F (Ti ) ? R ? E ? Q(Ti ) ≤ ?.

Now apply the preceding result.

8These operators are sometimes referred to as conditional expectations.

A THEORY OF PHYSICAL QUANTUM COMPUTATION

15

Assume H is a ?nite dimensional Hilbert space. We will consider trace functionals on two distinct spaces of operators: one on the space L(H ), which we denote by tr, and the other on the space L(L(H )) of linear mappings L(H ) → L(H ), which we denote troper . We will prove that abelian factorizable completely positive maps cannot approximate the identity map on L(H ). To do this we will show that the trace functional troper separates, in a sense to be made precise in the next paragraph, the identity operator on L(H ) from abelian factorizable completely positive F . Note that troper (IL(H ) ) = dim2 (H ). Lemma 3.7. Suppose the Hilbert space H has ?nite dimension n. For any unit-preserving abelian-factorizable completely positive map F : L(H ) → L(H ), troper (F ) ≤ n.

(36)

Proof. It su?ces to prove this for F which have the form (31). Referring to that representation, each positive functional ρi can be represented by a non-negative operator Si as follows: (37) ρi (T ) = tr(T Si ), Since ρi (I ) = 1, Si also has unit trace and in particular, Si ≤ I . Moreover m i=1 Gi = IH . Now

m

troper (P ) =

i=1 m

tr(Si Gi ) tr(Gi Si Gi )

i=1 m 1/2 1/2

= (38) ≤ =

i=1

tr(Gi Gi )

i=1 m

1/2

1/2

tr(Gi ) = tr(IH ) = n.

The previous lemma gives us a lower bound on the trace of I ? F for F abelian factorizable: (39) We can use the above lower bound on the trace of I ? F to obtain a lower bound on the norm of the operator I ? F : L(H ) → L(H ), where we consider L(H ) with the Schatten 2-norm · 2 , de?ned in Appendix A. The Schatten 2-norm is the norm that arises from the trace inner product on L(H ), also known as the HilbertSchmidt norm. We denote the corresponding operator norm on L(H ) → L(H ) by · 2→2 . If F is self-adjoint as an operator on the space L(H ) with the trace inner product, then from Lemma 3.7, we immediately obtain the bound 1 (40) I ? F 2→2 ≥ 1 ? . n In fact, the lower bound (40) is true for general unit-preserving abelian factorizable completely positive maps F . To see this, write F = FRe + iFIm where both FRe , troper (I ? F ) ≥ n2 ? n.

16

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

FIm are self-adjoint operators (not necessarily completely positive, however). Now (41) Therefore (42) I ?F

2→2

troper (I ? FRe ) = troper (I ? F ) ≥ n2 ? n. ≥ I ? FRe

2→2

≥ 1 ? 1/n.

In the discussion that follows, we need to consider another norm on the space L(H ) → L(H ) in addition to the norm · 2→2 just considered. The new norm, which we denote · ∞→∞ , is also an operator norm on L(H ) → L(H ), but relative to the · ∞ norm on L(H ). The · ∞→∞ norm is di?erent from the · 2→2 norm, but for ?nite dimensional spaces H the two norms are equivalent, which means that each norm is bounded relative to the other. To obtain the bounding constants, note that if T ∈ L(H ), √ (43) T ∞ ≤ T 2 ≤ n T ∞. From this it follows that 1 √ F (44) n ≤ F ≤ √ n F

2→2 .

2→2

∞→∞

which is the desired relative bound. In (40), if we substitute F by I ? F , we immediately obtain the following proposition: Proposition 3.8. Suppose H is a Hilbert space of ?nite dimension n. If a unit-preserving completely positive map F : L(H ) → L(H ) has the form (31), then (45) I ?F

∞→∞

≥ n?1/2 (1 ? 1/n).

To prove the crucial result for the No-Go Theorem, we only use case n = 2 of (45). Theorem 3.9. Suppose H is of dimension ≥ 2. If F is a unit-preserving √ completely positive map on L(H ) with an abelian factorization and β < 2/4, then (46) U ? T U ? F (T )

∞

≥β T

∞

for at least one T ∈ L(H ). √ If H is ?nite dimensional, we can take β = 2/4. Proof. Replacing F by the completely positive map T → U F (T )U ? , we can assume without loss of generality that U = I . To prove this, we will show that the assertion that (47) T ? F (T )

∞

<β T

∞,

?T ∈ L(H ),

leads to a contradiction. However, (47) implies (48) I ?F

∞→∞

≤ β.

We now reduce the proof to the case H has dimension 2, by considering a Hilbert space K of dimension 2 and completely positive unit-preserving mappings Q : L(K ) → L(H ) and R : L(H ) → L(K ) such that R ? Q is the identity map on L(K ).

A THEORY OF PHYSICAL QUANTUM COMPUTATION

17

If IH can be approximated to within β of the abelian factorizable F , then RF Q is also abelian factorizable and √ (49) IK ? RF Q = RIH Q ? RF Q ≤ IH ? F ≤ β < 2/4. However, in this contradicts Proposition 3.8. In the ?nite dimensional case, the norm is actually √achieved so that in (48) the ≤ sign can be replaced by < and so we can take β ≤ 2/4 as claimed.9 3.6. Proof of Encoding No-Go Theorem. 3.6.1. Two Lemmas. Lemma 3.10. Suppose that QCC(P, U, Menc , Mdec , α) holds. If P : T(Hcomp ) → T(Hcomp ) is γ -damped and A and EA are as identi?ed in Lemma 3.3, then for every T ∈ L(Hlogical ), (50)

t t ? Mt enc EA P Mdec (T ) ? U T U ∞

≤ (2γ + α) T

∞.

Proof. The QCC(P, U, Menc, Mdec , α) implies that for every ρ ∈ T(Hlogical ) with ρ 1 ≤ 1 and self-adjoint T ∈ L(Hlogical ), (51) tr Mdec (P (Menc (ρ))) ? U ρU ? T

? t t = tr ρ Mt enc (P (Mdec (T ))) ? U T U

≤α T It follows that for every T ∈ L(Hlogical ), (52) (53)

∞.

A is commutative and by Lemma 3.3, for each T ∈ L(Hlogical ) P t (T ) ? EA P t (T )

∞

t t ? Mt enc (P (Mdec (T ))) ? U T U

∞

≤α T

∞.

∞.

Thus using the fact that Mdec and Menc have norm ≤ 1, for every T ∈ L(Hlogical ),

t t ? Mt enc EA P Mdec (T ) ? U T U ∞ t t t t t Mt enc EA P Mdec (T ) ? Menc P Mdec (T ) ∞ t t ? Mt enc P Mdec (T ) ? U T U ∞ ∞.

≤ 2γ T

(54)

≤

+

≤ (2γ + α) T

Lemma 3.11. If Hlogical is of dimension ≥ 2,√ and P , U , Menc , Mdec and EA are the same as in Lemma 3.10, and if β < 2/4, then for some non-zero T ∈ L(Hlogical ), (55)

t t Proof. The unit-preserving completely positive map R = Mt enc EA P Mdec factors through the abelian von Neumann algebra A; this follows from the presence of the projection operator EA in the expression for R. Then (55) follows from Theorem 3.9. 9We note that it is possible to derive explicit results as well for the case n = 3. In this √ case one can show that one obtains a larger numerical bound than 2/4, which applies when dim(Hlogical ) ≥ 3. t t ? Mt enc EA P Mdec (T ) ? U T U ∞

≥β T

∞

18

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

3.6.2. Statement of Proof of Encoding No-Go Theorem. Proof. By the hypotheses of the Encoding No-Go Theorem √ (Theorem 3.2), √ the quantity 2γ + α < 2/4. Choose β such that 2γ + α < β < 2/4. From Lemma 3.10, it follows that for every T ∈ L(Hlogical ), (56)

t t ? Mt enc EA P Mdec (T ) ? U T U ∞

< (2γ + α) T

∞.

On the other hand by (55) in Lemma 3.11, there is a non-zero T such that (57)

t t ? Mt enc EA P Mdec (T ) ? U T U ∞

≥β T

∞.

Since T ∞ > 0, equations (56) and (57) imply β ≤ 2γ + α, which contradicts the choice of β . 3.7. Interpretation of Encoding No-Go Theorem. The Encoding No-Go Theorem is an extremely powerful application of the QCC. With this theorem, one can calculate the amount of damping for which fault-tolerant quantum computation becomes impossible. When the amount of damping exceeds the critical amount, which means that the value of 2γ becomes less than the critical value 2γcritical = √ 2/4 ? α, we ?nd that the only solutions to the QCC are those for which dim Hlogical = 1. As noted above, in this case no meaningful quantum computation is possible, since not even one quantum bit can be accomodated. In order to analyze the constraints on solutions to QCC(P, U, Menc, Mdec , α) implied by the No-Go Theorem, we regard the pair {U, α} as given, since both the desired quantum computation U , and the maximum acceptable implementation inaccuracy α, are prescribed. We assume that U is de?ned on a Hilbert space Hlogical such that dim(Hlogical ) ≥ 2, to allow meaningful quantum computation. For practical applications, one then seeks to determine triples {P, Menc, Mdec } that satisfy QCC(P, U, Menc , Mdec, α). The No-Go Theorem, on the other hand, identi?es conditions in which QCC(P, U, Menc , Mdec, α) is not satis?ed. Thus the No-Go Theorem provides a useful calculational tool for eliminating prospective quantum computer implementations that are guaranteed to fail. With the criterion provided by the No-Go Theorem, we can bound the space of solutions to QCC(P, U, Menc, Mdec , α). This allows exploration of trade-o?s amongst the members of the triple {P, Menc , Mdec}, with which one may construct generalized “phase diagrams” that indicate boundaries between potentially acceptable and de?nitely unacceptable values for P , Menc and Mdec . 4. Quantum Components 4.1. Introduction. As de?ned in Section 2, we refer to a physically realizable device intended to implement a quantum computation as a quantum component. Mathematically, a quantum component is represented by a completely positive, trace preserving map, P . The detailed form of P , as an explicit function, is dictated by underlying equations of motion. For a closed physical system, the quantum mechanical dynamics of the system are given by the Schr¨ odinger equation associated to a particular Hamiltonian H. However, for the general problem of a practical quantum computer, we must analyze realistic quantum components that interact with their environment, dissipate heat and exhibit decoherence. We must thus utilize a formulation that yields equations of motion appropriate to open quantum mechanical systems.

A THEORY OF PHYSICAL QUANTUM COMPUTATION

19

The connection to the Quantum Computer Condition presented in Section 2 is made by starting with the appropriate equations of motion that describe the dynamical evolution of a realistic quantum component interacting with its environment. One proceeds by solving the appropriate equations of motion. The explicit solution thus obtained provides the time-dependence of the quantum mechanical state of the open system. In principle, this allows us to deduce the explicit functional form of P . Formulations of equations of motion for quantum components that interact with complex environments comprised of many degrees-of-freedom necessarily involve approximations of one sort or another, and there is not in general a unique choice. In this section we illustrate the general approach by making use of a Lindbladtype equation (made more precise below) to describe how one obtains the quantum component P that appears in the Quantum Computer Condition. 4.2. Dynamical Equations of Motion. 4.2.1. Time-dependent generalization of the Lindblad equation. The state of a quantum mechanical system de?ned on a Hilbert space H can be modeled by a density operator ρ(t) whose time dependence obeys a linear (time dependent) equation (58) d ρ(t) = A(t)ρ(t), dt

where A(t) is an operator acting on T(H ), the Banach space of trace class operators on H . For a closed system we have the Schr¨ odinger equation, and the right-handside of (58) is given by (59) i A(t)ρ = ? [H(t), ρ],

where the Hamiltonian H(t) is a self-adjoint operator which may depend on the parameter t. However, it would be impractical to describe realistic quantum components using (59), since writing down the detailed Hamiltonian operator to account for all of the degrees-of-freedom comprising the quantum component and its environment would be intractable. Motivated by the work of Lindblad [21], we make use instead of the following expression for the action of A(t) on ρ: (60) i A(t)ρ = ? [H(t), ρ] + Lj (t)ρL? j (t) ? 1 ? L (t)Lj (t), ρ 2 j

j

where as above the H(t) is a self-adjoint operator which may depend on the parameter t, and the Lj are operators that describe e?ects arising from interaction with the environment, such as dissipation and decoherence. These operators are generalizations of the Lindblad operators of [21]; unlike the treatment given by Lindblad in [21], however, which considered only time-independent Hamiltonians H and time-independent dissipative perturbations Lj , with all operators bounded, we will allow unbounded and time-dependent H(t) and time-dependent (but still bounded) dissipative perturbations Lj (t). Our treatment generalizes that given

20

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

in [21], and we will refer to the equation of evolution (61) d i ρ(t) = ? [H(t), ρ] + dt Lj (t)ρL? j (t) ? 1 ? L (t)Lj (t), ρ 2 j

j

as the time-dependent generalization of the Lindblad equation. As an example of how one may approximate the dynamics of a quantum component interacting with a complex environment, this equation provides a starting point to the derivation of P used in the Quantum Computer Condition. For this purpose we need to consider solutions to equations of the type given in (61) known as “fundamental solutions.” 4.3. Fundamental Solutions. The concept of a fundamental solution associated to an evolution equation (see [30], §4.4) of the general form (58), such as (61) in particular, where ρ is a function with values in the Banach space T(H ) and A(t) is a one-parameter family of (possibly unbounded) linear operators on T(H ), will play an important role in this paper. A fundamental solution associated to an equation of motion is a solution of an operator version of the original equation. We show below how, given a fundamental solution, one obtains the completely positive, trace preserving map P that appears in the Quantum Computer Condition. Fundamental solutions are given by a family {Pt,s }t≥s≥0 of bounded operators on T(H ) indexed on pairs of real numbers t and s satisfying equations (62) and (63) Ps,s = I. d Pt,s = A(t)Pt,s dt

The intended interpretation of Pt,s is that if the system is in state ρ at time s, then the system will be in state Pt,s · ρ at later time t, that is (64) ρ(t) = Pt,s · ρ(s). 4.3.1. Existence and Positivity Properties of Fundamental Solutions. The problem of the existence and uniqueness of fundamental solutions is a central one in the mathematical theory of evolution equations. In addition to addressing the question of the existence of fundamental solutions, it is important for our analysis to determine the positivity properties of fundamental solutions. This is because, as we shall see, the complete positivity of the map P that explicitly appears in the Quantum Computer Condition is inherited from the complete positivity of the set of fundamental solutions {Pt,s }. Positivity is important in ensuring that the set {Pt,s }, as well as P , carry density matrices to density matrices. For equations of motion associated to ?nite dimensional systems, existence and uniqueness of solutions follows from the Lipschitz theorem on ordinary di?erential equations. Lindblad’s analysis extended to in?nite-dimensional (but bounded) systems, so, more generally, Lindblad characterized the in?nitesimal generator of a norm continuous completely positive semigroup [21], which corresponds to the case of (58) in which A(t) is constant and norm bounded (but possibly in?nitedimensional), i.e., for the standard, time-independent Lindblad equation. In order to generalize Lindblad’s analysis to allow us to study in?nite-dimensional, unbounded, time-dependent quantum systems, we will need to consider general evolution equations (58) in which A(t) may be unbounded as well as time-dependent,

A THEORY OF PHYSICAL QUANTUM COMPUTATION

21

for the in?nite-dimensional case. The general theory of such equations was developed by Kato, Yosida and others in the 1950’s. We will rely on results of Kato [14] which pertain to both existence of solutions and positivity properties, and on Theorem 4.4.1 of [30] which pertains to existence of solutions; moreover, we will use a constructive form of the theorem (which follows from an examination of the proof) which expresses the fundamental solution as a limit of a product of exponentials. The basic assumption of the approach is that if the A(t) are generators with su?ciently smooth variation, then fundamental solutions exist. Our system comprised of a quantum component interacting with its environment, described by (61), consists of a time-dependent Hamiltonian H(t) characterized by a time-dependent perturbation V (t) of a (possibly unbounded) self-adjoint operator H0 so that we have H(t) = H0 + V (t). In order to apply Kato’s theory for time dependent evolution equations, we will assume among other things that the perturbation V (t) does not change the domain of H0 . For the necessary background see ([14],[30]). We now state a proposition that asserts the existence and complete positivity of fundamental solutions to operator versions of the time-dependent generalization of the Lindblad equation given in (61): Proposition 4.1. For suitably regular time-varying potentials V (t) and dissipation operators Lj (t), there exists a strongly continuous completely positive operator Pt,s which is a fundamental solution to the time-dependent generalization of the Lindblad equation. The exact statement of the conditions for the above in the form of a theorem, and proof, are given in Appendix B in §B.3 and §B.4. 4.4. Construction of Quantum Components. Having established the existence and complete positivity of fundamental solutions to the operator form of the underlying equation of motion for our system (comprised of the quantum component interacting with its environment), it is straightforward to obtain an expression for the completely positive, trace preserving map P , characterizing the quantum component, that explicitly appears in the QCC. This is simply obtained by noting (cf (64)) that the time-evolution of the state ρ(t) between an initial ?xed time s ? ? (corresponding to the start of the quantum computation) and a ?nal ?xed time t (corresponding to the end of the quantum computation) is fully speci?ed by the fundamental solution de?ned with respect to those time values, Pt ?,s ?, so that we have (65) ?) = Pt s), ρ(t ?,s ? · ρ(?

and hence the completely positive, trace-preserving map P that appears in the QCC is given by the equivalence (66) P ≡ Pt ?,s ? . 5. Uni?ed Treatment of Quantum Computing Paradigms 5.1. Introduction. In this section we show that the QCC provides a unifying framework in which to describe on the same footing the currently-known “paradigms” for quantum computation, including the circuit-based paradigm, the graph state-based paradigm, the adiabatic quantum computer paradigm. The QCC subsumes all of these into a single, unifying paradigm for quantum computing.

22

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

5.2. Circuit-based paradigm. In this section we describe the speci?cation of quantum components based on the “circuit-based” paradigm of quantum computation. We proceed as follows: (1) For purposes of clarity, we begin in 5.2.1 by working in an idealization in which there is no noise present. For this idealized case we obtain the general form of the completely positive map P characterizing the quantum component. We then apply the result (for the noiseless idealization) to several speci?c realizations of the circuit-based paradigm. These include qubit-based quantum computers (these utilize states, the operators for which have a discrete eigenspectrum, i.e., qubits in the case of 2-level systems), quantum continuous variable-based quantum computers (these utilize states, the operators for which have a continuous eigenspectrum, such as coherent states), and liquid state NMR-based quantum computers. (2) Having obtained the general form for P in the noiseless case, for each of the three above-mentioned realizations of the circuit-based paradigm, we then explain in 5.2.2 how to modify the analysis, in a way appropriate to all choices of circuit realization, so as to account for the e?ects of noise. 5.2.1. Idealized Circuits in the Absence of Decoherence and Dissipation. A quantum circuit is described by a set G of gates operating in some speci?ed order on elements of a set R of objects. The quantum states of these objects constitute the information which is “processed” by the gates of the quantum circuit. We associate with each object i of R a Hilbert space H (i) that describes the possible states of that particular object. The Hilbert space for the full set of objects on which the circuit operates is then (67) Hcircuit =

i∈R

H (i) .

?? , so The gates in G, labeled by the index ?, are described by unitary operators V that the unitary operator describing the (noiseless) operation of the circuit is (68) Vcircuit =

?∈G

?? , V

where the product of operations is ordered in accordance with the de?nition of the ?? that appear in the multiplicand of (68) are in principle circuit. The factors V obtained from the fundamental solution to the appropriate underlying equation of motion, following the procedure outlined in Section 4 above.10 Each gate operates on a subset Σ? of the information elements, leaving the rest una?ected: (69)

Σ? ?? = V? ? V

IH (i)

i∈ / Σ?

,

10It is extremely important to note that we are not discussing here the abstractly de?ned quantum computation itself, which is prescribed in advance, and is represented by the unitary operator U that appears explicitly in the second term under the norm symbol in the QCC given in (12). Rather, we are discussing quantities that represent elements of a physical device that is to be used as an actual quantum computing machine. As such, the quantities under discussion here are to be regarded as “building blocks” for the ?rst term under the norm symbol in (12).

A THEORY OF PHYSICAL QUANTUM COMPUTATION Σ

23

where IH (i) is the identity operator on H (i) , and V? ? is the transformation e?ected by the ?th gate, so that we may express the unitary operator describing the idealized circuit as (70) (71) P ·ρ

? = Vcircuit ρVcircuit ? ? ? ?∈G

′ ?∈G

where the prime indicates that the second product reverses the order of the factors relative to the ?rst product.11 Up to this point we have made no restrictions on the Hilbert spaces or the types of gates appearing in the speci?cation of the circuit. We now describe three special cases of interest within the circuit-based paradigm: qubits, quantum continuous variables, and liquid state NMR. We obtain the completely positive, trace preserving map P that characterizes the implementation of the circuit for each example, thus showing that the QCC provides the proper foundational presentation of a quantum computer for all the cases. (Case 1) Circuit-realization with qubits The great majority of the research in quantum computation has focussed on circuits for which the information elements are qubits de?ned on a two dimensional Hilbert space C2 , so that the full Hilbert space of the circuit is (72) Hcircuit = C2

?|R|

= ?

?? ? ρ ? V

? ?? , V ?

?

.

where |R| is the cardinality of the set of computational qubits. Usually the set of gates is chosen from a relatively small set of operations, each of which acts on only 1 or 2 qubits. Specializing (69) to the case of a circuit built out of gates acting only on 1 or 2 qubits (this would be the proper description, for instance, of a machine that uses the universal set of quantum gates), we have (73) or (74) ?? = V (ij ) ? V ? Ik .

k(=i,j )∈R

?? = V (i) ? V ?

Ik ,

k(=i)∈R

where Ik is the identity operator acting on the copy of C2 associated to the k th qubit. With these de?nitions, the operator P that characterizes the implementation of the qubit-based realization of a quantum computer designed according to the circuit-based paradigm is given by (68) and (70). We thus see that the circuitbased paradigm, on which a large amount of the research in the ?eld is based, is properly described by the QCC. (Case 2) Circuit-realization with quantum continuous variables

11We strongly reiterate the message given in Footnote 10: It is only coincidentally the case

that the form of (70) resembles that of (3). Both the right- and left-hand sides of (70) describe the physical device (i.e., P ), not the abstractly-de?ned quantum computation U , and thus both sides of eq.(70) are to be associated with the ?rst term under the norm symbol in the QCC given in (12).

24

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

Alternatively, we may select di?erent Hilbert spaces H (i) appropriate for quantum computation using quantum continuous variables (QCV). For instance, the H (i) might describe the states of simple harmonic oscillators. The full Hilbert space of the circuit, and the gate operations out of which it is built, are then de?ned analogous to the above prescriptions for the qubit-based quantum computer. In this way we arrive at a speci?cation of the quantum component P appropriate to the case of computation by QCV. Thus, the QCV realization of the circuit-based paradigm is also seen to be properly described by the QCC. (Case 3) Circuit-realization with NMR states The treatment of quantum computation by nuclear magnetic resonance (NMR) in liquids requires special consideration due to the fact that the NMR sample e?ectively contains many copies of the circuit carrying out the same computation. In this case we de?ne the Hilbert space of the system as (75)

?N s HNMR = Hcircuit ,

where Ns is the number of copies of the circuit, which requires that we extend the de?nition of the unitary operation for the circuit as follows: (76) We then obtain (77)

? P ρ = VNMR ρVNMR ?N s . VNMR = Vcircuit

which describes the NMR-based quantum computer in the QCC.12 5.2.2. Quantum Circuits in the Presence of Decoherence and Dissipation. Thus far in this section we have restricted ourselves to a discussion of quantum circuits in the absence of decoherence and dissipation. This is re?ected in our description of the gates as implementing purely unitary operations, as in (68). Even at this level of description the circuit is not necessarily error-free. Unitary errors derive from a situation in which the evolution of the quantum circuit is unitary, but the circuit does not implement exactly the desired unitary computation: (78) Vcircuit = U .

Unitary errors can arise from either the design or the physical implementation of the circuit. Design errors arise, for example, due to the the fact that a universal set of quantum gates only allows for the implementation of an arbitrary unitary operation U to within an arbitrarily small tolerance [23]. In general there will then be some residual error implied by the very design of the circuit. Implementation errors result from inaccuracies in the physical parameters governing the unitary evolution associated with a gate as compared with the speci?cation of those parameters by the design. For example, an interaction Hamiltonian may be applied for a longer time than speci?ed, or there may be errors in the ?eld strengths or couplings in the interaction Hamiltonian.

12In connection with (77) we repeat the admonition given in Footnote 11 .

A THEORY OF PHYSICAL QUANTUM COMPUTATION

25

In addition to unitary errors, we also need to deal with errors resulting from decoherence and dissipation. We will refer to these simply as decoherent errors.13 ?? , where the In this case the gates are described by completely positive maps P hat on the P indicates that this quantum component is a single gate, and the index ? identifying the particular gate, as above. In addition to replacing unitary operations representing the gates by completely positive maps, it is also important to account for errors occurring in the transmission of quantum states from one gate to the next. This means that the transmission channels are also represented by ?? . In e?ect, the transmission completely positive maps designated by the symbol P channels (including any quantum memories used to store the states) are regarded ?? = I . If we call as gates that (ideally) implement the identity transformation: V the set of transmission channels C , the completely positive map that describes the circuit is then (79) P =

?∈G∪C

?? , P

where the index ? now identi?es both the transmission channels (in C ) and the gates (in G). ?? are obtained by explicitly solving the equations of motion for The operators P the physical device that implements the gate. The result may be written formally as the sum of two terms, one of which represents the action of the unitary operator ?? describing the ideal gate as speci?ed by the circuit design, and the other of which V represents the e?ects of unitary implementation errors as well as decoherence and/or dissipation: (80)

? ?? ρ = (1 ? ?? ) V ? ?ρ , ?? ρV ?? P + ?? Q

where ?? is the probability that an error occurs during the operation of the gate, and ? ? is a completely positive map that represents the e?ects of the error. Although Q we have indicated how this follows in principle from an explicit solution of the detailed dynamics of the gate (as described in §4), an error model of this form is often assumed from the outset. The latter approach necessitates the choice of ? ? to represent the errors. For instance, in investigating the some speci?c operator Q properties of quantum error correcting codes one often invokes a “depolarization” qubit error model in which ? ? 3 1 ? ? ρ ≡ ?ρ + σj ρσj ? , Q 4 j =1

(81)

where the σj are the Pauli matrices acting on a single qubit. The advantage of this approach is that it abstracts the physical implementation of the quantum computer from the design of the circuit while retaining the main features of decoherence that must be addressed in the development of any practical quantum computer. The disadvantage is that the abstraction must then be justi?ed relative to the detailed

13The case of liquid state NMR admits another type of error, which arises when the operators ? (k) appearing in (76) e?ect di?erent unitary errors on di?erent copies (k ) of the circuit. These V circuit are known as incoherent errors.

26

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

physical implementation of the computer in order to apply rigrously the results of any analysis based on (81). Whether we arrive at (80) by detailed calculation or by abstraction, we may use it in conjunction with (79) to describe the operation of the entire circuit:

(82)

P ·ρ=

?

? (1 ? ?? ) Vcircuit ρVcircuit +

1?

?

(1 ? ?? )

?f Qf ρ ,

where Qf incorporates the e?ects of the individual gate errors. We de?ne an error probability associated with the entire circuit: (83) with which we have (84)

? P · ρ = (1 ? ?f ) Vcircuit ρVcircuit + ?f Qf ρ .

?f ≡ 1 ?

?

(1 ? ?? ) ,

We will make use of this error model in applying the QCC to the problem of ?nding error thresholds for fault tolerance in §6. We note that eqs. (80) and (84) connect theoretical analysis with experimental observations. A general theoretical method for obtaining an explicit expression for the quantum component, P , in terms of the underlying equation of motion for the system, has been given above in §4. From an experimental perspective, explicitly writing (80) or (84) is a goal of quantum process tomography, which is by de?nition the experimental method of determining the evolution of open quantum systems [33]. 5.3. Adiabatic Quantum Computing Paradigm. We now show that the QCC also provides the proper framework in which to formulate the adiabatic quantum computing paradigm. In adiabatic quantum computing, the quantum component can be described by a Lindblad equation incorporating a Hamiltonian of the form: (85) Hadiabatic (t) = f (t) H0 + g (t) Hf

where f and g are smooth functions of time with f (0) = 1, f (T ) = 0, g (0) = 0 and g (T ) = 1, so that the adiabatic Hamiltonian goes smoothly from H0 to Hf over time. The full Lindblad equation may then be written as (86) i d ρ(t) = ? [Hadiabatic (t) + V (t), ρ] + dt Lj (t)ρL? j (t) ? 1 ? L (t)Lj (t), ρ 2 j ,

j

where V (t) represents unitary errors and the terms involving Lj (t) represent interactions with the environment. The computation begins with an an initial preparation of the ground state of the Hamiltonian H0 . Provided the conditions for adiabatic evolution are satis?ed, evolution under the exact adiabatic Hamiltonian takes the ground state of H0 to

A THEORY OF PHYSICAL QUANTUM COMPUTATION

27

the ground state of Hf with a high degree of accuracy. We identify the operator U that appears in the QCC as a unitary operator that describes this desired behavior: (87) U : |φ0 → |ψ0 .

where |φ0 is the ground state of H0 , |ψ0 is the ground state of Hf , and U is otherwise arbitrary. The physical realization of the adiabatic quantum computer is described by (86), and thus implements the desired operation U only approximately. This is due to the approximation inherent in the adiabatic evolution itself, as well as any additional unitary errors, decoherence and dissipation. We express this fact quantitatively by using the fundamental solution of (86) to derive the map P (as described above in §4) that describes the operation of the adiabatic quantum component. The construction of the QCC then follows. Note that the special case of the adiabatic quantum computer is characterized under QCC(P, U, Menc, Mdec , α) by two unique features: (1) the encoding and decoding maps, Menc and Mdec are identities, and (2) the QCC is required to hold only for the ground state of the initial Hamiltonian, that is, for ρ = |φ0 φ0 | . 5.4. Graph state-based (including cluster state-based) paradigm. We now consider the cluster-based approach to quantum computation ([25],[26], [27]), which is formulated in terms of an array of two level quantum systems. The systems in the array are referred to as sites and are elements of some set L which has a geometrical structure such as a 1 or 2 dimensional lattice; in addition to the geometrical structure there is also a ?ow structure which models the ?ow of information through the cluster. The two-dimensional Hilbert space corresponding to a site s ∈ L is denoted Hs and the Hilbert space H of the entire cluster system is the tensor product (88) Hcluster =

s∈L

Hs .

A key concept in the cluster approach is measurement at a site s ∈ L considered as an operation on quantum mechanical states. As an operation on pure states, the measurement corresponds to a pair of self-adjoint projections Es , 1 ? Es on Hs . In terms of the cluster system, we identify the projection Es with a projection on Hcluster de?ned by (89) E = Es ? IHm

m=s

where IHm is the identity operator acting on Hm . The associated projective measurement on the cluster Hilbert space Hcluster is the completely positive map on density states14 (90) The cluster scheme is illustrated in Figure 1. A general class of cluster-type con?gurations associated to graphs has been introduced in the literature ([27], [4]). Given a graph G = (nodes, edges), the lattice sites are the elements of nodes. Each lattice site a ∈ nodes has associated with it

14We note that the message of Footnote 11 applies to this equation.

PE · ρ = EρE + (1 ? E )ρ(1 ? E ) .

28

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

H1,3 H1,2 H1,1

H2,3 H2,2 ··· H2,1

Hn,3 Hn,2 Hn,1

Figure 1. Two-dimensional cluster con?guration (the arrow denotes time ?ow) a two-dimensional Hilbert space Ha and an “entanglement” projection operator F that acts on the Hilbert space (91) Hgraph =

a∈nodes

Ha

as follows:15 To each (a, b) ∈ edges, de?ne the projector of the form (92)

n∈nodes\{a,b}

IHn ? F(a,b) .

de?ned in terms of the Pauli matrices by (93) Then de?ne (94) F =

(a,b)∈edges

F(a,b) =

1 (a) (b) (a) (b) . I + σz + σz ? σz ? σz 2 F(a,b) .

F is a projection, since all the projectors Fa,b pairwise commute. 5.4.1. The Cluster Measurement Scheme. In the cluster-based approach as explained in [25], a computation is realized by a sequence of projective measurements performed on di?erent sites s ∈ L. The projective measurement that is to be performed at each step of the computation is determined by a scheme that speci?es at which site to make the measurement and what observable to measure at that site. These two choices depend on the outcome of the preceding measurements. In order to specify this process, a discrete time “?ow” between the sites is also given. This ?ow determines the sequencing of sites to measure. It is important to note however that the speci?c projective measurement taken at each site depends on the outcome of the measurement taken at the preceding site. At the level of speci?cation, we can also consider the cluster measurement scheme as given by a multi-rooted tree T. In Figure 2 we illustrate such a tree which because of spatial limitations is singly rooted. The tree consists of nodes and directed branches. Each node on the tree T corresponds to a pair (s, A) where s ∈ L is a cluster site and A is a two-level observable on Hs . We will refer to s as the cluster site corresponding to the tree node (s, A). Each node ? = (s, A) of the

15Such operators are considered from the more general point of view as partial isometries below in De?nition 5.2 and in the discussion preceding it.

A THEORY OF PHYSICAL QUANTUM COMPUTATION

29

E? (A) n = (s, B ) E ? (B ) E ? (D ) E + (D ) E+ (B )

E+ (A) m = (t, C ) E ? (C ) E + (C )

Figure 2. Example scheme of a cluster computation

tree has two outgoing branches corresponding to the two possible outcomes of the measurement of A. These two branches correspond to the spectral projections of A, which we denote E+ (A), E? (A). It is important to note that many di?erent nodes of T may correspond to the same cluster site, that is two distinct computation sequences may take us to the same node but at which di?erent measurements are taken. In fact, in the usual cluster approach all computation sequences traverse the exact same cluster nodes. This means that at each horizontal level of the tree T, the nodes all have the same cluster site. In the general scheme outlined above, no such restriction exists. Thus we may consider schemes in which not only the subsequent measurement depends on previous outcomes, but in which the site at which the measurement is taken also dependent on previous outcomes. For clusters that are not arranged in a 1 dimensional array, we can avoid the use of multiply rooted trees if we allow cluster systems that are not restricted to twolevel systems. This means that the Hilbert space Hs corresponding to a site s ∈ L can have arbitrary dimension. In that case, the corresponding node observables are allowed to have more than two outcomes and in particular, the speci?cation tree may not be binary. A complete path (that is one which originates at the root node and terminates at a leaf node) of T is speci?ed by a sequence of measurement outcomes, where the observable measured is associated to a node of the tree. Mathematically, each measurement outcome is expressed by one of the spectral projections associated to the measurement and graphically represented by an edge of the tree. A complete measurement outcome associated to a path is a sequence of projections, where each projection corresponds to a traversal of an edge of the tree as follows: (95)

0 1 2 3 k ?0 ?→ ?1 ?→ ?2 ?→ ?3 ?→ · · · ?→ ?k+1 .

E±

E±

E±

E±

E±

The projective measurement associated to the cluster consists of the projective measurements on sites following the branches of the cluster scheme tree. We can explicitly write this down:

30

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

Theorem 5.1. The projective measurement on a cluster is of the form (96) PT · ρ = Eτ

P∈PathT τ ∈P

ρ

τ ∈P

Eτ

where Eτ is a projector on the cluster site corresponding to the edge of the cluster scheme tree. Note that for each P ∈ Path(T), all the Eτ with τ ∈ P commute. 5.4.2. Quantum Components in the graph state-based paradigm. We now show that the graph state-based paradigm of quantum computation is properly described by the QCC. The paradigm has been described in the literature as employing an entangled substrate upon which a series of conditional projective measurements is performed. The projective measurements are used to carry out a computational algorithm, but can also be used to read input from a macroscopically observable input register or output to a macroscopically observable output register. The entangled substrate corresponds to some particular Hilbert subspace of entangled vectors which may be characterized in various ways, for instance as the range of an entangling operation or as the solutions to some eigenvalue equations. Correspondingly, we should expect that the mathematical formulation of the graph model of a quantum component also consist of two parts (We assume as given the Hilbert space Hgraph ): (1) An initial “entanglement producing” operation of some kind. (2) The projective measurement on Hgraph corresponding to the graph scheme. In our approach, we have already discussed how to formalize the step (2) above. However, there are several choices for the entanglement generating step (1). In the examples discussed in the literature, these are given by a self-adjoint projection operator, but it is natural from our viewpoint to consider more generally partial isometries V : H → H . Definition 5.2. A graph state-based quantum component C is a pair (V, T) given by a cluster scheme T and an “entanglement” partial isometry V on Hgraph . The completely positive map associated to C is de?ned by (97) QC · ρ = EP V ρV ? EP

P∈Path(T)

Thus, we see that, just as for the circuit-based paradigm and the adiabatic quantum computing paradigm, the QCC provides an over-arching framework in which to formulate the graph-state based paradigm of quantum computing. Moreover, in this section we have generalized the de?nition of graph state- (and cluster state-) based quantum computers that has previously appeared in the literature. Our generalization consists of two features: (1) our de?nition allows for arbitrarily di?erent measurements to be carried out at di?erent nodes at the same level of the multi-rooted tree T, and (2) our de?nition replaces the use of a self-adjoint projection operator as an entanglement generator with the more general notion of a partial isometry (which includes self-adjoint projections as a special case). 6. Error Thresholds and Fault Tolerance 6.1. Introduction. In §2.3.3 we showed that the recently discovered approach to error correction known as “operator quantum error correction” is in fact a special case of the general QCC formulation. Given the general applicability of the QCC to

A THEORY OF PHYSICAL QUANTUM COMPUTATION

31

all quantum computing paradigms (cf §5), as well as to all techniques for protection against errors (including quantum error correction, decoherence-free subspaces and noiseless subsystems), the QCC thus provides a uni?ed framework for a fully general analysis of fault tolerance in quantum computing. We refer to this as operator quantum fault tolerance (OQFT). As an example of OQFT, in this section we describe the application of the QCC to the analysis of error thresholds for fault tolerance in the circuit paradigm. To make contact with previous research, we begin by discussing this subject from the perspective of the well established method based on the analysis of error probabilities [28], [1], [15], [16], [24], [2]. Since the QCC in fact provides the underlying framework in which to study any issues associated with physical quantum computation, we then reformulate the problem in terms of the QCC. This allows us to relate the results of the two approaches, and to determine the extent to which the previously utilized approach (based on the method of error probabilities) is in fact justi?ed based on the insight provided with the QCC. 6.2. The Method of Error Probabilities. In this section we brie?y describe the method of error probabilities. We begin by identifying a quantum operation that we wish to implement and specifying a circuit that (ideally) implements the operation. We then identify an error model for the gates in the circuit that accounts for the inevitable e?ects of dissipation and decoherence that come into play when the gates are implemented with real devices. By hypothesis, the probability that an error occurs in this “direct” implementation of the operation is too high for it to be useful as a component in a quantum computer. In order to render the circuit more fault tolerant, we specify a second, more complicated, circuit using quantum error correction. The circuit now operates on the set of encoded qubits obtained by encoding the logical qubits of the direct implementation using a QECC. The gates in the original circuit are replaced by collections of gates that operate on the encoded qubits. Additional gates are added to carry out the QECC’s recovery procedure wherever an error is detected. The error model is then applied to the gates in this new circuit. The error correction clearly provides some degree of protection against errors, but it also necessitates a larger number of gates, so that there are then more opportunities for errors to occur. In order to determine whether this procedure has improved the fault tolerance, we compare the probability of an uncorrected error occurring during operation of the QECC version (?QECC ) with the probability of any error occurring in the “direct” f implementation (?direct ). If the QECC error probability is smaller, that is, if f (98) ?QECC f ?direct f <1,

then the procedure has been at least partially successful. If the error probability of the new circuit is still too high, we can reduce the error probability further by concatenating the code, that is by encoding the qubits used in the QECC version using the same QECC and by redesigning the circuit to handle the second level of encoded qubits. By repeating the process of concatenation we can arrange that the error probability be made arbitrarily small. The key point is that (98) can be shown to hold only if the failure probabilities of the individual gates are less than some threshold value that depends on

32

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

the relative complexity of the encoded vs. un-encoded versions of the circuit. The thresholds appearing in these conditions are known as “error thresholds.” If the threshold conditions are satis?ed, then the use of concatenated codes will provide fault tolerant operation to within some speci?ed tolerance. The problem of achieving fault tolerant quantum computation is reduced to the problem of constructing implementations of the primitive gates that satisfy the error threshold conditions. 6.3. Operator Quantum Fault Tolerance and the QCC. We now reconsider the above problem from the perspective of OQFT by making use of the QCC. Our goal is to identify a quantum component P , that implements (approximately) a quantum computation, U , that is, we write the quantum computer condition, QCC(P, U, Menc , Mdec, α), (99) Mdec(P · (Menc (ρ))) ? U ρU ?

1

≤α

for some suitable choice of encoding and decoding maps, Menc and Mdec . For simplicity of notation we de?ne an operator (100) so that the QCC becomes (101) ? ρ ? U ρU ? P

1

? ≡ Mdec · P · Menc , P

≤α.

We begin by developing a “zero-th order” implementation that does not use a QECC. In the absence of errors, we assume that the implementation faithfully implements the computation U : (102) ? (0) ρ = Mdec V (0) (Mencρ) V (0)? = U ρU ? . P circuit circuit

With the error model (84) we have (103) ? (0) ρ?U ρU ? = P

1 ? ?f

(0)

(0) ? (0) (0)? (0) ? Mdec Vcircuit (Menc ρ) Vcircuit +?f Q f ρ?U ρU

1

,

where, for generality, we have subsumed the encoding and decoding maps into the ? f . (The maps are identities for the zero-th order circuit.) With (102) de?nition of Q the left hand side of the QCC takes the simple form (104) ? (0) ρ ? U ρU ? = ?(0) Q ? (0) ρ ? U ρU ? P f f

1

.

Note from (83) that the failure probability for this circuit is, to lowest order, linear in the error probabilities for the gates which make up the circuit: (105) ?f ? O (?? ) ,

(0)

(recall that ?? represents gate error, cf (83)) a fact which, as we shall see, is crucial to the derivation of an error threshold.

A THEORY OF PHYSICAL QUANTUM COMPUTATION

33

We next construct the “?rst order” implementation of U , which operates in the codespace of the QECC. By the preceding arguments, this implementation will satisfy (106) ? (1) ρ ? U ρU ? = ?(1) Q ? (1) ρ ? U ρU ? P f f

1

.

Following [24], we consider the case that errors a?ect the qubits in the circuit independently and that the QECC recovery procedure is su?cient to correct a single error in any one qubit. In that case, the encoded circuit will exhibit an unrecoverable error only if two or more single qubit errors occur. In this case, the error probability will be quadratic in ?? to leading order: (107) ?f ? O (?? )2 .

(1)

At this point, the QECC has not eliminated all errors, but has resulted in a circuit with error probabilities that are quadratic, rather than linear, in the error probabilities of the primitive operations. We have now introduced two implementations of the computation. If either implementation satis?es the QCC, then there is no need to continue. If the implementations do not satisfy the QCC, then it is meaningful to ask whether this can be achieved by concatenating the code. In order to answer this question, we begin by asking another, related question: has the QECC improved the fault tolerance of the implementation relative to the QCC? In other words, we wish to know under what conditions it is true that for all ρ (108) or alternatively (109)

16

? (1) ρ ? U ρU ? P

1

? (0) ρ ? U ρU ? < P

1

,

supρ

Using (104) and (106), this becomes ?f

(1)

? (1) ρ ? U ρU ? P ? (0) ρ ? U ρU ? P

(1)

1 1

<1.

(110)

supρ

(0) ?f

·

(0) Qf ρ

Qf ρ ? U ρU ? ? U ρU ?

1 1

<1.

The above equation represents the extension of (98) to OQFT obtained by using the general framework provided by the QCC. Clearly it does not reduce to a simple ratio of error probabilities, as in (98) above. The reason for this is that this formulation of the error threshold problem based on the QCC takes into account not only error probabilities, ?f , but also expressions involving the norms of operators that characterize the “strength” of the errors. To see this, note that we began by ? (0) for the zero-th order assuming an error model represented by the operation Q f implementation. The error model in the encoded implementation is represented, in ? (1) . There is no reason to suppose that these general, by a di?erent operation, Q f

16Relation (109) is actually a stronger condition than (108) for in?nite-dimensional vector

spaces.

34

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

error models are equally e?ective in perturbing the computation. This is re?ected in the di?erence in the norms: (111) ? (1) ρ ? U ρU ? Q f

1

? (0) ρ ? U ρU ? = Q f

1

.

To further emphasize this point, we obtain the above result (98) based on the assumption that the error models are “commensurate” in the sense that (112) ? (1) ρ ? U ρU ? Q f

1

? (0) ρ ? U ρU ? ≈ Q f

1

.

We shall shortly return to the question of whether this is a good approximation. With this assumption, the condition (110) then becomes ?f ?f

(1)

(113)

(0)

1,

which is identical to the result (98) obtained by the method of error probabilities. We obtain the form of the error threshold by noting from (105) and (107) that the numerator and denominator of (113) are, to lowest order, quadratic and linear, respectively, in ?? , so that (114) ?f

(1) (0) ?f

=

?ν

A?ν ?? ?ν + · · ·

?

B? ?? + · · ·

.

At this point, it is straightforward to obtain a threshold if we set the ?? equal to each other, and take ? ≡ ?? . Then one obtains the error threshold comparable to those obtained in [24], [13], [35], as (115) ?

?

B?

?ν A?ν

.

The desired behavior of the concatenated QECC described above follows if we successively apply the approximation (112) at each level of concatenation: (116) ? (i+1) ρ ? U ρU ? Q f

1

? (i) ρ ? U ρU ? ≈ Q f

1

.

We note that Aliferis, Gottesman and Preskill [2] also relate the ratio of error probabilities for successive levels of concatenation to an overall measure of the “accuracy” of the quantum computation. Their approach di?ers from the one described here in three important ways: (Contrast 1) Accuracy in [2] is de?ned in terms of the probabilities pi of the outcomes i of measurements on the ?nal output state for an ideal, as compared with a noisy, circuit: (117)

i

|pnoisy ? pideal |. i i

In contrast, we de?ne the accuracy of the implementation by the QCC. (Contrast 2) The threshold proofs in [2] rely on proofs that the implementations at each level of concatenation are conditionally correct relative to the noise model. In this case the ratio of error probabilities ?(i+1) /?(i) is automatically the quantity

A THEORY OF PHYSICAL QUANTUM COMPUTATION

35

of interest in comparing performance at each level of concatenation. Here, in contrast, the QCC provides the ?gure of merit at each level of concatenation, and the dependence on error probabilities is inferred. (Contrast 3) As a consequence of the two preceding points, [2] makes contact with the notion of accuracy only at the highest level of concatenation, at which the entire quantum component may be viewed as a black box. Here, the QCC is applied systematically at each level of concatenation. At this point we have shown that we can obtain the standard form of the error threshold result from the QCC by introducing the assumption (116) on the relative strengths of the error models appropriate to successive levels of concatenation of the QECC. We now investigate the validity of the approximation. We begin by making some reasonable assumptions about the error operators and the initial state of the ? (i) are trace preserving, and thus describe computer. We note that the operators Q f the evolution of the quantum component if a failure has in fact occurred, as can be seen by setting ?f = 1 in (84). It is then reasonable to expect that the state resulting from its operation on ρ will be “close” to the maximum entropy state17 in the sense that, for small δp , (118) ? (i) ρ ? ρI Q f

p

< δp ,

where ρI is the maximum entropy state, and the value of p identi?es the Schatten p-norm associated to the corresponding Schatten p-class (cf (126)). On the other hand, it is normally the case that the input state for the quantum computation is a pure state, and thus so is the state U ρU ? . In this case, it is straightforward to show that (119) and (120) ρI ? U ρU ? =1? 1 , N ρI ? U ρU ? =2? 2 N

1

∞

where N is the dimension of Hlogical . Since (121) ? (i) ρ ? U ρU ? = Q f ? (i) ρ ? ρI + ρI ? U ρU ? Q f ,

we have, by triangle inequalities, (122) or (123) 1? 1 ? (i) ρ ? U ρU ? ? δ∞ ≤ Q f N ≤1? 1 + δ∞ N 2? 2 ? (i) ρ ? U ρU ? ? δ1 ≤ Q f N ≤2? 2 + δ1 N

1

∞

17Note that this is not a good assumption for errors that operate locally on only one qubit in a larger set of qubits, leaving the others una?ected. This important case is a topic for further study.

36

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

where we have assumed implicitly that N ? 1 and δp ? 1. Since these expressions hold for any value of i, (116) is a reasonable approximation with either choice of norm under the conditions that (1) (118) holds for some δp ? 1, and (2) the initial state of the computation is a pure state.

7. Conclusions In this paper we have presented a fundamental, unifying framework for describing physically-realizable quantum computing machines. This is concisely stated in the form of the Quantum Computer Condition (QCC), an inequality that incorporates a complete speci?cation of the full dissipative, decohering dynamics of the actual, practical device used as the quantum computing machine, a speci?cation of the ideally-de?ned quantum computation intended to be performed by the machine, and a quantitative criterion for the accuracy with which the computation must be executed. With the QCC we prove the fundamental Encoding No-Go Theorem that identi?es the amount of damping (including dissipative and decohering e?ects) for which physically-realizable fault-tolerant quantum computing is not possible. We provide a rigorous de?nition of damping, and explicitly calculate a universal critical damping value for fault-tolerant quantum computation. This theorem can be used in principle to solve practical problems involving quantum computer design. In this paper we have also presented an existence proof for fundamental solutions to useful classes of time-dependent generalizations of the Lindblad equation. This can provide a useful tool in analyzing a wide variety of open quantum mechanical systems. We have demonstrated that the entire formalism of operator quantum error correction (OQEC) can be obtained from the QCC as a special case. By allowing for the possibility of residual errors, the general formalism of the QCC enables us to generalize OQEC to “operator quantum fault tolerance” (OQFT). Since we have demonstrated that OQEC is in fact a particular reduction of the QCC, and since standard quantum error correction (QECC), decoherence-free subspaces (DFS) and noiseless subsystems are all special cases of OQEC, we have discovered that QCC applies in general across all these approaches. As an initial application of the OQFT concept, we have begun the exploration of the application of QCC to the problem of establishing thresholds for fault-tolerant quantum computation by showing that the standard approaches to this problem can be motivated within the framework of the QCC. Research in quantum information science has resulted in the discovery of seemingly di?erent paradigms for quantum computation, including the circuit-based paradigm, graph state-based paradigm and adiabatic quantum computing paradigm. In this paper we have explicitly demonstrated that these paradigms are not in fact distinct at a fundamental level, but are all describable within the unifying framework provided by the QCC. In the particular case of the graph state-based paradigm (which includes cluster state-based models), we not only show that the paradigm is a manifestation of the unifying picture provided by the QCC, but also introduce a de?nition of graph state-based quantum computers that generalizes the graph state models previously de?ned in the literature.

A THEORY OF PHYSICAL QUANTUM COMPUTATION

37

Future work motivated by our results should include applications of the Encoding No-Go Theorem to diverse problems pertaining to practical quantum computer design and implementation. It would also be of interest to further explore the physics of the operator quantum fault tolerance (OQFT) generalization of OQEC presented in this paper. Speci?c work along theses lines should include further application of the QCC to obtaining error thresholds for fault-tolerant implementations of quantum computers. It would also be fruitful to explore applications of the quantum computer condition to situations in which quantum process tomography techniques are used to experimentally characterize the quantum component described by the completely positive map that appears in the QCC. Acknowledgements We wish to thank Anthony Donadio and Yaakov Weinstein for helpful comments. This work was supported by MITRE under the MITRE Technology Program. Appendix A. Banach Spaces of Operators A linear map T on a Banach space is a contraction i? its norm is ≤ 1. Let H be a separable Hilbert space. L(H ) denotes the space of bounded operators on H with the operator norm, K(H ) denotes the normed closed subspace of compact operators of L(H ). In case H is ?nite dimensional, these spaces are identical. Assume now H is in?nite dimensional; we consider other Banach spaces of compact operators de?ned by eigenvalue decay conditions and whose norms √ re?ect the rate of decay of the eigenvalues. Speci?cally, let T ∈ K(H ), then |T | = T ? T is a non-negative compact operator and so by the spectral theorem, has a complete set of eigenvectors with eigenvalues that can be ordered in a sequence (124) s0 (T ) ≥ s1 (T ) ≥ · · · ≥ sn (T ) ≥ 0 which converges to 0. The following properties are well-known (see [12]; also [7] on which this discussion is based). T(H ) is the Banach space of trace-class operators T on H with the norm

∞

(125)

T

1

=

k=0

|sk (T )|

More generally, the Schatten p-class Tp (H ) is de?ned by the condition

∞

(126)

T

p

=

k=0

sk (T )

p

1 p

<∞

with the norm given by · p . The operator norm for any T ∈ L(H ), denoted by T ∞, is de?ned as the supremum of T x for x ∈ H of norm ≤ 1. If T ∈ K(H ), the operator norm is also the supremum of the eigenvalues of |T |. Appendix B. Completely Positive Maps and Fundamental Solutions In the following, H denotes a complex Hilbert space. We will consider various Banach spaces of bounded operators on H : these are discussed in Appendix A above. We will consider completely positive maps on both L(H ) on the Schatten classes Tp (H ) and especially on the trace-class operators T(H ) = T1 (H ).

38

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

The basic fact about completely positive maps we use is the Kraus representation. Proposition B.1. A P : T(H ) → T(H ) is a completely positive contraction if and only if it is of the form (127) where Xi ∈ L(H ) with (128)

i

P (ρ) =

i∈I

Xi ρXi?

Xi? Xi ≤ 1

We will consider only trace preserving completely positive maps P , that is which satisfy (129) tr(P (ρ)) = tr(ρ)

Proposition B.2. Suppose P is a completely positive map given by the Krauss form (127). (1) A necessary and su?cient condition P be trace-preserving is that (130)

i∈I

Xi? Xi = 1. (2) A necessary and su?cient condition that P be bounded in the operator norm is that

(131)

i∈I

Xi Xi? ∈ L(H ).

Note that if T is a completely positive trace-preserving and operator norm continuous map, then by interpolation T is also norm continuous on the Schatten p-classes. Proposition B.3. If P is a completely positive trace-preserving map, then the adjoint of P on L(H ) de?ned by (132) tr(P t (T )ρ) = tr(T P (ρ)) is a unit preserving completely positive map L(H ) → L(H ). Its Kraus representation is (133) P t (T ) =

i∈I

Xi? T Xi

Note that the completely positive unit preserving maps L(H ) → L(H ) which are adjoints of completely positive trace-preserving maps on T(H ) → T(H ) can be characterized precisely as those which are continuous mappings L(H ) → L(H ), where L(H ) has the ultraweak topology. B.1. Completely Positive Semigroups on T(H ). We need to ?rst establish that each generalized Lindblad-type operator A(t) (cf eqs.(58) and (60)) generates a semigroup of completely positive contractions on T(H ) with respect to the trace-class norm · 1 . We will also consider boundedness properties relative to the operator norm · ∞ , although in general the corresponding semigroups may not be contraction semigroups in this norm.

A THEORY OF PHYSICAL QUANTUM COMPUTATION

39

We begin with a general result characterizing in?nitesimal generators of strongly continuous positive (or completely positive) semigroups on the Banach space T(H ). Recall that a one-parameter semigroup {Tt }t≥0 on a Banach space E is said to be of class C0 i? for every x ∈ E , limt→s Tt (x) = Ts (x). If {Tt }t≥0 is a C0 -semigroup, then there are positive constants M and β such that (134) Moreover, (135) Ax = lim h?1 (Th x ? x)

h→0

Tt ≤ M etβ .

is a densely-de?ned operator called the in?nitesimal generator of {Tt }t≥0 Theorem B.4. Suppose A is a densely-de?ned operator on T(H ) which generates a contractive semigroup {Tt }t≥0 on T(H ). A necessary and su?cient condition the operators {Tt }t>0 be positive (respectively completely positive) is that for each λ>0 (136) R(λ, A) = (λI ? A)?1 (which is de?ned by the Hille-Yosida Theorem) be positive (respectively completely positive). The operators Tt are trace-preserving i? in addition for all λ > 0, (137) tr(R(λ, A)ρ) = λ?1 tr(ρ) for every ρ ∈ T(H ). The family of operators {Tt }t>0 extends to a C0 -semigroup on L(H ) i? there are constants M ′ and β ′ such that for all λ > β ′ and for all ρ ∈ T(H ) and nonnegative integers m: (138) R(λ, A)m ρ

∞

≤ M ′ (λ ? β ′ )?m ρ

′

∞.

In this case, we have the explicit bound (139) Tt

∞

≤ M ′ etβ

?t > 0.

Remark B.5. It su?ces that the property (137) hold for density states ρ. Proof. To avoid duplication, we refer only to the assertions for complete positivity. By the general Hille-Yosida theory, if A is an in?nitesimal generator of a contractive semigroup on T(H ), the resolvents (140) R(λ, A) = (λ ? A)?1

∞

are de?ned for all λ > 0 and by Theorem 3.1.3 of [30], (141) R(λ, A) =

0

e?λt Tt dt.

i.e., the resolvent is the Laplace transform of {Tt }t≥0 . In particular, if Tt consist of completely positive operators, then the resolvent operators are all completely positive. Conversely, let (142) Then for each t ≥ 0, (143) Aλ = λ(λ R(λ, A) ? I ) exp(tAλ ) = e?λt exp tλ2 R(λ, A)

40

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

which is clearly completely positive and it is known that for each t ≥ 0, (144) Tt = lim exp(tAλ )

λ→∞

in the strong operator topology. Thus Tt is completely positive. To deal with the trace preservation properties of Tt , note that if S is a bounded operator on T(H ) for which (145) then

∞

tr(Sρ) = α tr(ρ) Sk ρ k!

∞

(146) Thus, (147)

tr(eS ρ) =

k=0

tr

=

k=0

αk tr(ρ) = eα tr(ρ). k!

tr(exp tAλ ρ) = e?λt etλ

2

1/λ

tr(ρ) = tr(ρ).

By (144), it follows that Tt is also trace preserving. Conversely, if Tt is trace preserving,

∞

(148)

tr(R(λ, A)ρ) =

0

e?λt tr(Tt ρ)dt =

0

∞

e?λt tr(ρ)dt = λ?1 tr(ρ).

B.1.1. Examples of Completely Positive Semigroups. Our analysis of the generalized Lindblad equation will reduce to an analysis of the solution in two important cases: (Case 1) Unitary Evolution. In particular, if H is a self-adjoint operator on a Hilbert space H , then the family of completely positive mappings (149) PtH (ρ) = eitH ρe?itH

is a one-parameter group of completely positive maps. Its generator on the traceclass operators is formally given by the operator (150) ρ → i[H, ρ].

This expression is only formal, because it is not de?ned for all ρ. Nevertheless, the in?nitesimal generator is densely de?ned on the space of trace-class operators and it is an extension of (150) for the ?nite rank operators on the domain of H. (Case 2) Dissipative Operators. Another type of in?nitesimal generator we will consider are operators of the form (151) Lρ = Lj ρL? j ? 1 ? L Lj , ρ 2 j

j

where braces denote the anti-commutator. Lemma B.6. Suppose (152)

j

L? j Lj ∈ L(H ).

A THEORY OF PHYSICAL QUANTUM COMPUTATION

41

Then the operator given by (151) is bounded on T(H ). If in addition (153)

j

Lj L? j ∈ L(H ).

then L is a bounded operator on L(H ). Proof. Let C be the operator norm of

j

de?ned and continuous on T(H ), it su?ces to show L0 : ρ → and continuous on T(H ). However, if ρ ≥ 0, (154) (155) (156) (157) tr(L0 (ρ)) = =

j

L? j Lj . To show the map L is

j

Lj ρL? j is de?ned

tr(Lj ρL? j)

i

tr(ρL? j Lj )

1/2 tr ρ1/2 L? j Lj ρ j

=

= tr ρ1/2 (

j

1/2 L? j Lj )ρ

≤ C tr(ρ) = C ρ

1

thus for arbitrary self-adjoint ρ, (158) (159) (160) L0 (ρ)

1

= L0 (ρ+ ? ρ? ) ≤ L0 (ρ ) ρ+

+ 1 1

1 1

+ L0 (ρ? )

1

≤C 0≤

+ ρ?

= C ρ 1.

If (153), suppose 0 ≤ T ≤ 1: (161) Thus, for arbitrary T , (162) LT

∞ j

L? j T Lj ≤

j

L? j Lj ≤ C 1H

≤

Lj L? j

j

∞

+C T

∞

It was established by Lindblad [21] (and not too hard to show directly) that if (152) holds, the L generates a uniformly continuous a completely positive semigroup (relative to the operator norm on T(H )). In this case the semigroup is given by

∞

(163)

etL =

k=0

tk k L . k!

B.2. Perturbation of Completely Positive Generators. In order to show that the generalized Lindblad operators given in equation (60) are completely positive generators, we need to establish a perturbation result analogous to the KatoRellich theorem. A linear map B on T(H ) is trace annihilating i? (164) tr(Bρ) = 0

42

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

for all ρ ∈ T(H ). For example, an operator of the form (151) is easily seen to be trace annihilating. Using the Trotter-Kato product formula ([31], [5]), we can show that generators of completely positive contractive semigroups have a sum which is also a generator of a contractive semigroup, provided the sum generates a contractive semigroup. Proposition B.7. Suppose B is a bounded operator of the form (151). If A is a generator of a completely positive semigroup then so is A + B . . Corollary B.8. The generalized Lindblad operators given in equation (60) generate a completelty positive semigroup of contractions on T(H ). We now extend the results of Lindblad and Davies to allow for time varying Hamiltonians by relying on results of Kato. The need for this arises since in some circuit-based models the various gates are implemented by varying the Hamiltonian (see for instance [23] §7.7.2). We make the assumption that the dissipative e?ects are bounded which simpli?es the analysis considerably. B.3. Solving the Generalized Lindblad Equation. In some cases it is possible to solve the generalized Lindblad equation [22]. However, by solution we mean an expression for the fundamental solution Pt,s as a limit of product of exponentials. Though this expression will almost never provide a closed form solution, it will provide enough information to obtain an estimate of how well a unitary (or partial isometry) can be implemented by one of the operators Pt,s . The two tools we use are the Trotter-Kato product formula and the explicit form of the solution of a time-dependent equation as a time ordered product of exponentials given in the proof of §4.2 of [30]. A precise formulation of a set of conditions which guarantees the convergence of the products in the next two theorems is given in Theorem B.11. These results comprised by Theorems B.9 and B.10 are restatements of assertions contained in the proofs in §4.2 of [30]. Theorem B.9. Under suitable conditions, the fundamental solution Pt,s for (62) is given by

n?1

(165)

Pt,s = str-lim?→0

k=0

exp (rk+1 ? rk )A(rk ) ,

where s = r0 < r1 < · · · < rn?1 < t and max |rk+1 ? rk | ≤ ?. Each Pt,s is completely positive and trace preserving. Theorem B.10. Under the same assumptions as the previous theorem B.9, (166) exp sA(t) = str-limn→∞ exp s L(t) n exp s H(t) n

B.4. Existence of Solutions. We will restrict our attention to bounded time varying perturbations of a ?xed self-adjoint operator acting on T(H ) via a commutator as in (167) below. The result we state is not the most general possible, and the early results of Kato [14] su?ce for its proof. We follow the treatment in Chapter XIV, §4 of [34] which is a more readily available reference. Theorem B.11. Suppose H is a self-adjoint operator, {B (t)}t∈[0,∞[ , {Lj (t)}t∈[0,∞[ , 1 ≤ j ≤ n are families of bounded operators, all of which are continuously norm

A THEORY OF PHYSICAL QUANTUM COMPUTATION

43

di?erentiable as a functions of t, then there is a fundamental solution Pt,s for (62) where

n

(167)

A(t)ρ = ?i[H + B (t), ρ] +

j =1

Lj (t)ρL? j (t) ?

1 ? L (t)Lj (t), ρ 2 j

.

The solution is a given by a limit of a time-ordered product of exponentials (165). Proof. There are various technical assumptions for a family A(t) of operators that need to be checked in order to apply Kato’s Theorem. The ?rst of these is the independence of dom A(t) of the parameter t. Under our assumptions (168) A(t) = A + C (t)

where C (t) : T(H ) → T(H ) are bounded operators and A is the in?nitesinal generator of a contractive semigroup. Indeed, (169) Aρ = ?i[H, ρ]

n

is the in?nitesimal generator of a group on T(H ) and (170) C (t)ρ = ?i[B (t), ρ] + Lj (t)ρL? j (t) ? 1 ? L (t)Lj (t), ρ 2 j .

j =1

is by assumption a bounded operator on T(H ). In particular, all the operators A(t) have the same domain dom(A). We now address the remaining assumptions in Kato’s theorem. For any λ > 0, (171) λ ? A(t) = λ ? A ? C (t) = (I + C (t) R(λ, A))(λ ? A)

For λ su?ciently large R(λ, A)C (t) has norm < 1, so the Neumann (geometric) series for inverses (see [9], Chapter VIII, §3) I + R(λ, A)C (t) is invertible. Thus we can write, (172) Thus, (173) B (t, s) = (λ ? A(t))(λ ? A(s))?1 = (I + C (t) R(λ, A))(I + C (s) R(λ, A))?1 is well de?ned and by our assumptions B (t, s) is a norm di?erentiable function jointly in the variables t, s. This implies the remaining conditions in the hypothesis of Kato’s theorem. It only remains to observe that presence of the parameter λ, instead of 1 as actually stated in Kato’s theorem is immaterial, since solutions of equations (174) d ρ(t) = A(t)ρ(t) dt (λ ? A(t))?1 = R(λ, A)(I + R(λ, A)C (t))?1

are trivially a?ected by adding a constant scalar to A(t).

44

GERALD GILBERT, MICHAEL HAMRICK AND F. JAVIER THAYER

Appendix C. Solving the Ersatz Quantum Computer Condition Consider the ersatz quantum computer condition (E QCC) given in (3): (175) P · ρ = U ρU ? . Note that this can be obtained by setting the encoding and decoding maps to unity, and setting α = 0 in the QCC given in (12). A simple observation shows that “solving” (175) is completely equivalent to obtaining the noise-free part of a communication channel. Theorem C.1. Suppose H is ?nite-dimensional. If P is given by the Kraus representation (127), given a unitary U , the set of ρ ∈ L(H ) satisfying (175) is the ?-subalgebra of L(H ) given by (176) AP,U = {ρ ∈ L(H ) : ?i ∈ I, [ρ, U ? Xi ] = 0} Proof. The solutions of (175) are the ?xed points of the completely positive map Q de?ned by the equation (177) Q·ρ= U ? Xi ρXi? U.

i∈I

Now apply [17], Theorem 2.1. In the above theorem, the assumption H is ?nite-dimensional is essential, see [3]. Since H is ?nite dimensional A is an algebraic direct sum of algebras isomorphic to full matrix algebras. Proposition C.2. Let {Eκ }κ∈I be the set of ?nite-dimensional minimal central projections of A. Then (178) Aκ = Eκ AEκ is an algebra of operators on the range Hκ of Eκ (which is a ?nite dimensional space). It is isomorphic to a full matrix-algebra of ?nite multiplicity. References

[1] D. Aharonov and M. Ben-Or, “Fault-tolerant quantum computation with constant error,” Proc. 29th Ann. ACM Symp. on Theory of Computing, p. 176 (New York, ACM, 1998), arXiv:quant-ph/9611025. [2] P. Aliferis, D. Gottesman, J. Preskill, “Quantum Accuracy Threshold for Concatenated Distance-3 Codes,” arXiv:quant-ph/0504218 (2005). [3] A. Arias, A. Gheondea, and S. Gudder. Fixed points of quantum operations. J. Mathematical Physics, 43(12):5872–5881, 2002. [4] S.C. Benjamin, J. Eisert, and andT.M. Stace4. Optical generation of matter qubit graph states. arXiv:quant-ph/0506110. [5] P. R. Cherno?. Note on product formulas for operator semigroups. Journal of Functional Analysis, 2:238–243, 1968. [6] M. D. Choi. Positive Linear Maps on C? -algebras. Can. J. Math, XXIV (3): 520-529, 1972. [7] A. Connes. Noncommutative Geometry. Academic Press, 1994. [8] D. Deutsch. Quantum computational networks. Proc. Roy. Soc. London, A425:73–90, 1989. [9] J. Dieudonn? e Foundations of Modern Analysis. Academic Press, 1960. [10] J. Dixmier. Les alg` ebres d’op? erateurs dans l’espace hilbertien. Gauthier Villars, Paris, 1969. [11] M. H. Freedman, A. Kitaev, M. J. Larsen, and Z. Wang. Topological quantum computation. Bulletin of the American Mathematical Society, 40(1):216, 2003. [12] I. C. Gohberg and M. G. Krein. Introduction to the theory of linear nonselfadjoint operators. American Mathematical Society, Providence, R. I., 1969.

A THEORY OF PHYSICAL QUANTUM COMPUTATION

45

[13] D. Gottesman, “Stabilizer codes and quantum error correction,” Caltech Ph.D. thesis, 1997, arXiv:quant-ph/9705052. [14] T. Kato. Integration of the equation of evolution in a Banach space. J. Math. Soc. of Japan, 5:208–234, 1953. [15] A. Kitaev. Quantum computations: Algorithms and error correction. Russian Mathematical Surveys, 52(6):1191–1249, 1997. [16] E. Knill, R. La?amme, W. H. Zurek, “Resilient quantum computation: error models and thresholds,” Proc. Roy. Soc. London A 454, 365 (1998), arXiv:quant-ph/9702058. [17] D. W. Kribs. Quantum channels, wavelets, dilations and representations of On . arXiv:math.OA/0309390. [18] D. Kribs, R. La?amme, D. Poulin, “A Uni?ed and Generalized Approach to Quantum Error Correction,” Phys. Rev. Lett. 94: 180501, 2005, arXiv:quant-ph/0412076. [19] D. Kribs, R. La?amme, D. Poulin, M. Lesosky “Operator Quantum Error Correction,” arXiv:quant-ph/0504189 (2005). [20] D. A. Lidar, D. Bacon, K. B. Whaley, “Concatenating Decoherence Free Subspaces with Quantum Error Correcting Codes,” Phys. Rev. Lett., 82:4556, 1999, arXiv:quant-ph/9809081. [21] G. Lindblad. On the generators of quantum dynamical semigroups. Communications in Mathematical Physics, 48(119), 1976. [22] H. X. Lu, J. Yang, Y.D. Zang, and Z. B. Chen. Algebraic approach to master equations with superoperator generators of su(1,1) and su(2) lie algebras. Phys. Rev. A, 67(12), 2003. [23] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, 2000. [24] J. Preskill, “Reliable quantum computers,” Proc. Roy. Soc. Lond. A 454, 385-410 (1998), arXiv:quant-ph/9705031. [25] R. Raussendorf and H. J. Briegel. Computational model for the one-way quantum computer: Concepts and summary. arXiv:quant-ph/0207183. [26] R. Raussendorf and H. J. Briegel. A one-way quantum computer. Physical Review Letters, 86(22):5188, 2001. [27] R. Raussendorf, D.E. Browne, and H.J. Briegel. Measurement-based quantum computation with cluster states. Phys. Rev. A, 68: 022312, 2003. [28] P.W. Shor, “Fault-tolerant quantum computation,” in Proceedings, 37th Annual Symposium on Foundations of Computer Science, pp. 56-65 (Los Alamitos, CA, IEEE Press, 1996), arXiv:quant-ph/9605011. [29] W. F. Stinespring. Positive Functions on C? -algebras. Proc. Amer. Math. Soc., 6: 211-216, 1955. [30] H. Tanabe. Equations of Evolution. Pitman, London,, 1975. [31] H. F. Trotter. On the products of semi-groups of operators. Proc. Amer. Math. Soc., 10:554– 551, 1959. [32] J. von Neumann. Mathematical Foundations of Quantum Mechanics. Princeton University Press, Princeton, New Jersey, 1955. [33] Y.S. Weinstein, T. Havel, J. Emerson, N. Boulant, M. Saraceno, S. Lloyd, D. Cory. “Quantum Process Tomography of the Quantum Fourier Transform,” J. Chem. Phys, 121, 6117, 2004. [34] K. Yosida Functional Analysis. Springer-Verlag, New York, 1968. [35] C. Zalka, Threshold estimate for fault tolerant quantum computing, arXiv:quant-ph/9612028, 1996.

- A Theory of Computation Based on Quantum Logic (I)
- The Physical Implementation of Quantum Computation
- Quantum theory of the origin of the theory on h
- The Study of Entangled States in Quantum Computation and Quantum Information Science
- The problem of equilibration and the computation of correlation functions on a quantum comp
- On the power of quantum computation
- Topological field theory and the quantum double of SU(2)
- A theory of quantum gravity based on quantum computation
- Hooft Computation Of The Quantum Effects Due To A Four-Dimensional Pseudoparticle - Physica D 1976
- A Theory of Fault-Tolerant Quantum Computation

更多相关文章：
**
***Quantum* *Computation* and *Quantum* Information【M.*A*.Ni....pdf

*Quantum* *Computation* and *Quantum* Information【M.*A*....*quantum* *computer* 7.3.1 *Physical* apparatus 189 ...*Theory* *of* *quantum* error-correction 10.3.1 ...**
***Quantum* *Computation* for *Physical* Modeling.pdf

*Quantum* *Computation* for *Physical* Modeling_专业资料。...*the* *quantum* *computer* and for only for *a* short ... *A* *Theory* *of* *Physical* Q... 暂无评价 45页 ...**
Progress in Post-***Quantum* *Theory*.pdf

Progress in Post-*Quantum* *Theory*_IT/计算机_专业...*The* *quantum* action *of* intent *of* mind on matter ...However, my *physical* interpretation *of* this is ...**
Base ***of* *Quantum* *theory*(final)_图文.ppt

Base*of* *Quantum* *theory*(final)_生产/经营管理_经管... showed that *a* *theory* based on *the* *quantum* ...(2) Bohr *condition* *of* frequency *The* electron ...**
***Quantum* *computation* and *physical* law.pdf

*A* successful *quantum* *computer* would verify as-yet untested predictions *of* *quantum* mechanics. Such verification is no *Quantum* *computation* and *physical* law ...**
...requirements for ***a* scalable *quantum* *computer*_免....pdf

*A* *Theory* *of* *Physical* Qua... 暂无评价 45页 ... requirements for *a* scalable *quantum* *computer*... *The* primary resource for *quantum* *computation* is ...**
***QUANTUM* COMPUTING AND JOSEPHSON JUNCTION CIRCUITS.pdf

*Theory* *of* *quantum* information processing has ...*quantum* *computer* *a* *physical* system needs to ...(1995) *Quantum* *computation*, Science 269, 255{261...**
***A* *Theory* *of* Bulk *Quantum* *Computation* (Extended Abstract).pdf

*A* *Theory* *of* Bulk *Quantum* *Computation* (Extended ...For example, this *condition* holds in *the* case ...*quantum* *computer*", quant-ph/9807050, 1998. [4]...**
Classical and ***Quantum* *Computation* (2002).pdf

*The* *theory* *of* *quantum* *computation* can be ...Implementation *of* *a* *quantum* *computer* It is not ...“encode” *a* logical qubit into *a* *physical* ...**
***Quantum* *Computation* Beyond *the* Standard Circuit Model.pdf

Keywords.*Quantum* Gates, *Quantum* *Computation*, *Quantum* Control *Theory*. submitted...*physical* system to act as *a* *quantum* *computer* using only its natural ...**
***Quantum*-*Computation*_图文.ppt

Fault-tolerant Graph-state*Quantum*-*Computation* Panos Aliferis & Debbie Leung Institute *of* *Quantum* Information, Caltech Starting September 1st, 2005: Dept *of* ...**
Requirement for ***quantum* *computation*.pdf

As*quantum* mechanics underpins all *physical* *theories*, it is important to ...ne *the* *quantum* *computer*. *A* *quantum* *computer* is one whose processes obey ...**
1 On ***the* Power *of* *Quantum* *Computation*.pdf

1 On*the* Power *of* *Quantum* *Computation*_专业资料。...on *Theory* *of* Computing, pages 151{158, 1971. ...*quantum* *computer*", Proceedings *of* *the* Royal ...**
Integrable ***quantum* *computation*.pdf

Integrable*quantum* *computation*_信息与通信_工程科技_...*the* *quantum* circuit model *Computers* are *physical* ...ciently simulated on *a* classical *computer*, whereas...**
...demands for scalable ***quantum* *computation*_免费下....pdf

*Physical*-resource demands for scalable *quantum* *computation* *The* primary resource...We argue that *a* *quantum* *computer*’s power stems from *the* murky region ...**
...***Physical* Implementation *of* *Quantum* *Computation*_....pdf

*Physical* implementation ... 暂无评价 4页 免费 *A* *Theory* *of* *Physical* Qua.... *The* *Physical* Implementation *of* *Quantum* *Computation* After *a* brief introduction ...**
...for ***the* One-Way *Quantum* *Computer* Concepts and Su....pdf

Computational Model for*the* One-Way *Quantum* *Computer* Concepts and Summary ... speci?c *physical* systems that are suitable [7] for *quantum* *computation*. ...**
***The* Signals and Systems Approach to *Quantum* *Computation*.pdf

*quantum* *computation* is *the* *theory* *of* Linear Time ...*physical* manifestations *of* *the* same underlying ...*A* *quantum* *computer* too has *the* bit as its ...**
Oxide-Semiconductor Materials for ***Quantum* *Computation*.pdf

Oxide-Semiconductor Materials for*Quantum* *Computation*...*the* *quantum* *computer*, and for providing *a* source...*The* *theory* *of* fault-tolerant error correction3 ...**
Spin ***quantum* *computation* in silicon nanostructures_免费 ....pdf

cation in*the* fabrication *of* scalable solid state *quantum* *computer* ...eld *of* *quantum* *computation* and *quantum* information. Many *physical* systems have... 更多相关标签：

Progress in Post-

Base

Keywords.

Fault-tolerant Graph-state

As

1 On

Integrable

Computational Model for

Oxide-Semiconductor Materials for

cation in