1. Introduction

For classical channels, Shannon's theorem [1] gives the information-carrying capacity of a channel. When one tries to generalize this to quantum channels, there are several ways to do so, giving rise to several different capacities. In this paper, we consider the capacity of quantum channels to carry classical information, with various restrictions on how the channel may be used. Several such capacities have already been defined for quantum channels. In particular, the C_1,1 capacity, where only tensor product inputs and tensor product measurements are allowed [2–5], and the C_1,∞ capacity, where tensor product inputs and joint measurements are allowed [6–8], have both been studied extensively. We investigate these capacities in connection with a specific example; namely, we analyze how these capacities behave on a symmetric set of three quantum states in three dimensions which we call the lifted trine states. A quantum channel of the type that Holevo [8] classifies as c-q (classical-quantum) can be constructed from these states by allowing the sender to choose one of these three pure states, which is then conveyed to the receiver. This channel is simple enough that we can analyze the behavior of various capacities for it, but it is also complicated enough to exhibit interesting behaviors which have not been observed before. In particular, we define a new, natural, classical capacity for a quantum channel, the C_1,A capacity, which we also call the adaptive one-shot capacity, and show that it lies strictly between the C_1,1 capacity (also called the one-shot quantum capacity) and the C_1,∞ capacity (also called the Holevo capacity).

The three states we consider, the lifted trine states, are obtained by starting with the two-dimensional quantum trine states, (1, 0), (–1/2, /2), (–1/2, –/2), introduced by Holevo [9] and later studied by Peres and Wootters [10]. We add a third dimension to the Hilbert space of the trine states and lift all of the trine states out of the plane into this dimension by an angle of arcsin , so the states become , 0, ), and so forth. We deal with small (roughly, < 0.1), so that they are close to being planar. This is one of the interesting regimes. When the trine states are lifted farther out of the plane, they behave in less interesting ways until they are close to being vertical; then they begin to become interesting again, but we do not investigate this second regime.

To put this channel into the formulation of completely positive trace-preserving operators, we let the sender start with a quantum state in a three-dimensional input state space, measure this state using a von Neumann measurement with three outcomes, and send one of the lifted trines T₀, T₁, or T₂, depending on the outcome of this measurement. This process turns any quantum state into a probability distribution over T₀, T₁, and T₂.

The first section of the paper deals with the accessible information for the lifted trine states when the probability of all three states is equal. The accessible information of an ensemble is the maximum mutual information obtainable between the input states of the ensemble and the outcomes of a positive operator valued measure (POVM) measurement on these states. The substance of this section has already appeared in [11]. Combined with Appendix C, this shows that the number of projectors required to achieve the C_1,1 capacity for the ensemble of lifted trines can be as large as 6, the maximum possible by the real version of Davies' theorem. The second section deals with the C_1,1 channel capacity (or the one-shot capacity), which is the maximum of the accessible information over all probability distributions on the trine states. This has often been called the C₁ capacity because it is the classical capacity obtained when one is allowed to process (i.e., encode/measure) only one signal at a time. We call it C_1,1 to emphasize that one is allowed to input only tensor product states (the first 1), and allowed to make quantum measurements on only one signal at a time (the second 1). The third section deals with the new capacity C_1,A, the “adaptive one-shot capacity.” This is the capacity for sending classical information attainable if one is allowed to send codewords composed of tensor products of lifted trine states, one is not allowed to make joint measurements involving more than one trine state, but one is allowed to make a measurement on one signal which only partially reduces the quantum state, use the outcome of this measurement to determine which measurement to make on a different signal, return to refine the measurement on the first signal, and so forth. In Section 5, we give an upper bound on the C_1,1 capacity of the lifted trine states, letting us show that for the lifted trine states with sufficiently small , this adaptive capacity is strictly larger than the C_1,1 channel capacity. In Section 6, we show that for two pure non-orthogonal states, C_1,A is equal to C_1,1, and thus strictly less than the Holevo capacity C_1,∞. These two results show that C_1,A is different from previously defined capacities for quantum channels. To obtain a capacity larger than C_1,1, it is necessary to make measurements that only partially reduce the state of some of the signals, and then later return to refine the measurement of these signals depending on the results of intervening measurement. In Section 7, we show that if one uses “sequential measurement” (i.e., measures only one signal at a time and never returns to a previously measured signal), it is impossible to achieve a capacity larger than C_1,1.

We take the lifted trine states to be

(1)

When it is clear what is, we may drop it from the notation and use T₀, T₁, or T₂.

2. The accessible information

In this section, we find the accessible information for the ensemble of lifted trine states, given equal probabilities. This is defined as the maximal mutual information between the trine states (with probabilities each) and the elements of a POVM measuring these states. Because the trine states are vectors over the reals, it follows from the generalization of Davies' theorem to real states (see, e.g., [12]) that there is an optimal POVM with at most six elements, all of the components of which are real. The lifted trine states are threefold symmetric, so by symmetrizing we can assume that the optimal POVM is threefold symmetric (possibly at the cost of introducing extra POVM elements). Also, the optimal POVM can be taken to have one-dimensional elements E, so the elements can be described as vectors |v_i>, where E_i = |v_i> <v_i|. This means that there is an optimal POVM whose vectors come in triples of the form
P₀(, ), P₁(, ), P₂(, ), where p is a scalar probability and

(2)

The optimal POVM may have several such triples, which we label
P_b(₁, ₁), P_b(₂, ₂), …, P_b(_m, _m). It is easily seen that the conditions for this set of vectors to be a POVM are that

(3)

One way to compute the accessible information I_A is to break the formula for accessible information into pieces so as to keep track of the amount of information contributed to it by each triple. That is, I_A will be the weighted average (weighted by p_i) of the contribution I(, ) from each (, ). To see this, recall that I_A is the mutual information between the input and the output, and that this can be expressed as the entropy of the input less the entropy of the input given the output, H(X_in) – H(X_in|X_out). The term H(X_in|X_out) naturally decomposes into terms corresponding to the various POVM outcomes, and there are several ways of assigning the entropy of the input H(X_in) to these POVM elements in order to complete this decomposition. This is how I first arrived at the formula for I_A. I briefly sketch this analysis, and then go into detail in a second analysis. This second analysis is superior in that it explains the form of the answer obtained, but it is not clear how one could discover the second analysis without first knowing the result.

For each , and each , there is a that optimizes I(, ). This starts out at /6 for = 0, decreases until it hits 0 at some value of (which depends on ), and stays at 0 until reaches its maximum value of /2. For a fixed , by finding (numerically) the optimal value of for each and using it to obtain the contribution to I_A attributable to that , we get a curve giving the optimal contribution to I_A for each . If this curve is plotted, with the x-value being sin² and the y-value being the contribution to I_A, an optimal POVM can be obtained by finding the set of points on this curve whose average x-value is 1/3 [from Equation (3)], and whose average y-value is as large as possible. A convexity argument shows that we need at most only two points from the curve to obtain this optimum; we need one or two points, depending on whether the relevant part of the curve is concave or convex. For small , it can be seen numerically that the relevant piece of the curve is convex, and we need two s to achieve the maximum. One of the (, ) pairs is (0, /6), and the other is (, 0) for some > arcsin (1/). The formula for this is derived later. Each of these s corresponds to a triple of POVM elements, giving six elements for the optimal POVM.

The analysis in the remainder of this section gives a different way of describing this six-outcome POVM. This analysis unifies the measurements for different , and also introduces some of the methods that appear again in Section 4. Consider the following measurement protocol. For small ( < ₁ for some constant ₁), we first take the trine T_b() and make a partial measurement which either projects it onto the x, y plane or lifts it farther out of this plane so that it becomes the trine T_b(₁). (Here ₁ is independent of .) If the measurement projects the trine into the x, y plane, we make a second measurement using the POVM having outcome vectors (0, 1) and (±/2, –1/2). This is the optimal POVM for trines in the x, y plane. If the measurement lifts the trine farther out of the x, y plane, we use the von Neumann measurement that projects onto the basis consisting of (, 0, ), (–, ±, ). If is larger than ₁ (but smaller than 8/9), we skip the first partial measurement and just use the von Neumann measurement presented above. Here, ₁ is obtained by numerically solving a fairly complicated equation; we suspect that no closed-form expression for it exists. The value of ₁ is 0.061367, which is sin² for ≈ 0.25033 radians (14.343°).

We now give more details on this decomposition of the POVM into a two-step process. We first apply a partial measurement which does not extract all of the quantum information, i.e., it leaves a quantum residual state that is not completely determined by the measurement outcome. Formally, we apply one of a set of matrices A_i satisfying ∑_i A_i^†A_i = I. If we start with a pure state |v>, we observe the ith outcome with probability <v|A_i^†A_i|v>, and in this case the state |v> is taken to the state A_i|v>. We choose as the A_i the matrices M(_i), where

(4)

The M(_i) form a valid partial measurement if and only if

By first applying the above M(_i), and then applying the von Neumann measurement with the three basis vectors

(5)

we obtain the POVM given by the vectors P_b(_i, _i) of Equation (2); checking this is simply a matter of verifying that V_b()M() = P_b(, ). Now, after applying M(_i) to the trine T₀(), we obtain the vector

(6)

This is just the state T₀(_i'), where T₀(_i') is the trine state with

(7)

and where

(8)

is the probability that we observe this trine state, given that we started with T₀(). Similar formulae hold for the trine states T₁ and T₂. We compute that

(9)

The first stage of this process, the partial measurement which applies the matrices M(_i), reveals no information about which of T₀, T₁, T₂ we started with. Thus, by the chain rule for classical Shannon information [13], the accessible information obtained by our two-stage measurement is just the weighted average (the weights being p_i') of the maximum over of the Shannon mutual information I_i'() between the outcome of the von Neumann measurement V() and the trine T(_i'). By convexity, it suffices to use only two values of _i' to obtain this maximum. In fact, the optimum is obtained using either one or two values of _i' depending on whether the function

is concave or convex over the appropriate region. In the remainder of this section, we give the results of computing (numerically) the values of this function I_'. For small enough it is convex, so that we need two values of ', corresponding to a POVM with six outcomes.

We need to calculate the Shannon capacity of the classical channel whose input is one of the three trine states T(') and whose output is determined by the von Neumann measurement V(). Because of the symmetry, we can calculate this using only the first projector V₀. The Shannon mutual information between the input and the output is H(X_in) – H(X_in|X_out), which is

(10)

The giving the maximum I_' is /6 for ' = 0, decreases continuously to 0 at ' = 0.056651, and remains 0 for larger '. (See Figure 1.) This value 0.056651 corresponds to an angle of 0.24032 radians (13.769°). This was determined by using the computer package Maple** to numerically find the point at which dI()/d = 0.

Figure 1

By plugging the optimum into the formula for I_', we obtain the optimum von Neumann measurement of the form V above. We believe this is also the optimal generic von Neumann measurement, but have not proved this. The maximum of I_'() over , and curves that show the behavior of I_'() for constant , are plotted in Figure 2. We can now observe that the leftmost piece of the curve is convex, and thus that for small the best POVM will have six projectors, corresponding to two values of '. For trine states with 0 < < 0.061367, the two values of ' giving the maximum accessible information are 0 and 0.061367; we call this second value ₁. The trine states T(₁) make an angle of 0.25033 radians (14.343°) with the x–y plane.

Figure 2

We can now invert the formula for ' [Equation (7)] to obtain a formula for sin² , and substitute the value of ' = ₁ back into the formula to obtain the optimal POVM. We find

(11)

where ₁ ≈ 0.061367 as above. Thus, the elements in the optimal POVM we have found for the trines T(), when < ₁, are the six vectors P_b(, 0) and P_b(0, /6), where is given by Equation (11) and b = 0, 1, 2. Figure 3 shows the accessible information given by this six-outcome POVM and compares it to the accessible information obtained by the best-known von Neumann measurement.

Figure 3

We also prove there are no other POVMs which attain the same accessible information. The argument above shows that any optimal POVM must contain only projectors chosen from these six vectors: Only those two values of ' can appear in the measurement giving maximum capacity, and for each of these values of ' there are only three projectors in V() which can maximize I_' for these '. It is easy to check that there is only one set of probabilities p_i which make the above six vectors into a POVM, and that none of these probabilities are 0 for 0 <  < ₁. Thus, for the lifted trine states with 0 < < ₁, there is only one POVM maximizing accessible information, and it contains six elements, the maximum possible for real states by a generalization of Davies' theorem [12].

3. The C_1,1 capacity

In this section, we discuss the C_1,1 capacity (or one-shot capacity) of the lifted trine states. This is the maximum of the accessible information over all probability distributions of the lifted trine states. Because the trine states are real vectors, it follows from a version of Davies' theorem that there is an optimal POVM with at most six elements, all of the components of which are real. Since the lifted trine states are threefold symmetric, one might expect that the solution maximizing C_1,1 capacity is also threefold symmetric. However, unlike accessible information, for C_1,1 capacity a symmetric problem does not mean that the optimal probabilities and the optimal measurement can be made symmetric. Indeed, for the planar trine states, it is known that they cannot. The optimal C_1,1 capacity for the planar trine states T(0) is obtained by assigning probability 1/2 to two of the three states and not using the third one at all. (See Appendix A.) This gives a channel capacity of 1 – H(1/2 – /4) = 0.64542 bits, where H(x) = –x log₂x – (1 – x) log₂(1 – x) is the binary Shannon entropy. As discussed in the previous section, the accessible information when all three trine states have equal probability is log₂ 3 – 1 = 0.58496 bits.

In this section, we first discuss the best measurement we have found to date. We believe this is likely to be the optimal measurement, but do not have a proof of this. Later, we discuss what we can actually prove; namely, that as approaches 0 (i.e., for nearly planar trine states), the actual C_1,1 capacity becomes exponentially close to the value given by our conjectured optimal measurement. We postpone this proof to Section 5 so that in Section 4 we can complete our presentation of the various channel capacities of the lifted trine states by giving an adaptive protocol that improves on our conjectured C_1,1 capacity. Together with the bounds in Section 5, this lets us prove that the adaptive capacity C_1,A is strictly larger than C_1,1.

Our starting point is the C_1,1 capacity for planar trines. The optimum probability distribution uses just two of the three trines. For two pure states, |v₁> and |v₂>, the optimum measurement for C_1,1 is known. Let the states have an angle between them, so that |<v₁|v₂>|² = cos² . We can then take the two states to be and The optimal measurement is the von Neumann measurement with projectors P± = (1/, ±1/). This measurement induces a classical binary symmetric channel with error probability

and the C_1,1 capacity is thus 1 – H(½ – ½ sin ). Thus, for the planar trines, the C_1,1 capacity is 1 – H(1/2 – /4) = 0.64542. To obtain our best guess for the C_1,1 capacity of the lifted trines with small, we will give three successively better guesses at the optimal probability distribution and measurement. For small , we know of nothing better than the third guess, which we conjecture to be optimal when < 0.018073. Smolin tried searching for solutions using a hill-climbing optimization program; he failed to find any better measurement for C_1,1, although the program did converge to the best-known value a significant fraction of the time.¹

For the trines T(0), the optimum probability distribution is (½, ½, 0). Our first guess is to continue to use the same probability distribution for > 0. For the trines T(), this probability distribution, (½, ½, 0), the optimum measurement is a von Neumann measurement with projectors

(12)

where β = 4/(3 + 1). The C_1,1 capacity in this case is 1 – H(p), where p = ½(3 – 1)²/(3 + 1). This function is plotted in Figure 4. We call this the two-trine capacity.

Figure 4

The second guess comes from using the same measurement, Q(β), as the first guess, but varying the probabilities of the three trine states so as to maximize the C_1,1 capacity obtained using this measurement. To do this, we need to consider the classical channel shown in Figure 5. Because of the symmetry of this channel, the optimal probability distribution is guaranteed to give equal probabilities to trines T₁ and T₂. Remarkably, this channel has a closed form for the probability p for the third trine, which maximizes the mutual information. Expressing the mutual information as H(X_out) – H(X_out|X_in), we find that this simplifies to

(13)

where = <Q₀|T₀>² and q = <Q₂|T₁>² = <Q₁|T₂>². Taking the derivative of this function with respect to p, setting it to 0, and moving the terms with p in them to the left side of the equality gives

(14)

Dividing by and exponentiating both sides gives

(15)

which has the solution

(16)

Using this value of p, and the measurement of Equation (12) with β = 4/(3 + 1), we obtain a curve that is plotted in Figure 4. Note that as goes to 0, goes to 0 and the exponential on the right side goes to 2^[1-H(q)]/, so p becomes exponentially small. It follows that this function differs from the two-trine capacity by an exponentially small amount as approaches 0. Note also that no matter how small is, the above value of p is non-zero, so even though the two-trine capacity is exponentially close to the above capacity, it is not equal.

Figure 5

For our third guess, we refine the above solution slightly. It turns out that the β used to determine the measurement Q(β) is no longer optimal after we have given a non-zero probability to the third trine state. What we do is vary both p and β to find the optimal measurement for a given . This leads to the classical channel shown in Figure 6. Here, q and take the same values as above, and = <Q₀|T₁>² = <Q₀|T₂>². As we did for the case with = 0, we can write down the channel capacity, differentiate with respect to p, and solve the resulting equation. In this case, the solution turns out to be

(17)

where

(18)

Here

is the Shannon entropy of the probability distribution {p₁, p₂, …, p_k}. We have numerically found the optimum β for the measurement Q(β), and used this result to obtain the C_1,1 capacity achieved by optimizing over both p and Q(β). This capacity function is shown in Figure 4. This capacity, and the capacities obtained using various specific values of β in Q(β), are shown in Figure 7. For ≥ 0.040491, the optimum β, is ; note that the measurement Q() is the same as the measurement V(0) introduced in Section 2, Equation (5). The measurement Q(β) appears to give the C_1,1 capacity for ≤ 0.018073 [and for ≥ 0.061367, where the optimum measurement is Q()].

Figure 6   Figure 7

Now, suppose that in the above expression for p [Equations (17) and (18)], and both approach 0, while q is bounded away from ½. If > , then 2^Z is exponentially large in 1/( – ), and the equation either gives a negative p (in which case the optimum value of p is actually 0) or a p that is exponentially small. If > , and both and are sufficiently small, then 2^Z is exponentially small in 1/( – ) and the value of p in the above equation is negative, so that the optimum value of p is 0. There are solutions to the above equation which have > and positive p, but this is not the case when is sufficiently close to 0.

It follows from the above argument that, as approaches 0, the optimum probability p for the third trine state approaches 0 exponentially fast in 1/, and so the C_1,1 capacity obtained from this measurement grows exponentially close to that for the two-trine capacity, since the two probability distributions differ by an exponentially small amount.

We have now described our conjectured C_1,1 for the lifted trine states, and the measurements and probability distributions that achieve it. In the next section, we show that there is an adaptive protocol which achieves a capacity C_1,A considerably better than our conjectured C_1,1 capacity. When approaches 0, it is better by an amount linear in . To rigorously prove that it is better, we need to find an upper bound on the capacity C_1,1 which is less than C_1,A. We have already noted that, as approaches 0, all three of our guesses for C_1,1 become exponentially close. In Section 5 we prove that the true C_1,1 capacity must become exponentially close to these guesses.

Because these three guesses for C_1,1 become exponentially close near = 0, they all have the same derivative with respect to at = 0. Our first guess, which used only two of the three trines, is simple enough that we can compute this derivative analytically, and we find that its value is

This contrasts with our best adaptive protocol, which we introduce in Section 4. This protocol has the same capacity at = 0, but between = 0 and = 0.087247 it has slope 4.42238 bits. Thus, for small enough , the adaptive capacity C_1,A is strictly larger than C_1,1.

4. The adaptive capacity C_1,A

As can be seen from Figure 4, the C_1,1 capacity is not concave in . That is, there are two values of such that the average of their C_1,1 capacities is larger than the C_1,1 capacity of their average. This is analogous to the situation we found while studying the accessible information for the probability distribution (, , ), where the curve giving the information attainable by von Neumann measurements was also not concave. In that case, we were able to obtain the convex hull of this curve by using a POVM to linearly interpolate between the two von Neumann measurements. We find, remarkably, that for the lifted-trine example, the relationship between C_1,1 capacity and C_1,A capacity is similar: Protocols using adaptive measurement can attain the convex hull of the C_1,1 capacity with respect to .

We now introduce the adaptive measurement model leading to the C_1,A capacity. If we assume that each of the signals that Bob receives is held by a separate party, this is the same as the LOCC model used in [14, 15], where several parties share a quantum state and are allowed to use local quantum operations and classical communication among the parties. In our model, Alice sends Bob a tensor product codeword using the channel many times. We call the output from a single use of the channel a signal. Bob is not allowed to make joint quantum measurements on more than one signal, but he is allowed to make measurements sequentially on different signals. He is further allowed to use the classical outcomes of his measurements to determine which signal to measure next, and to determine which measurement to make on that signal. In particular, he is allowed to make a measurement which only partially reduces the quantum state of one signal, make intervening measurements on other signals, and return to make a further measurement on the reduced state of the original signal (which measurement may depend on the outcomes of intervening measurements). The information rate for a given encoding and measurement strategy is the mutual information between Alice's codewords and Bob's measurement outcomes, divided by the number of signals (channel uses) in the codeword. The adaptive one-shot capacity C_1,A is defined to be the supremum of this information rate over all encodings and all measurement strategies that use quantum operations local to the separate signals (and classical computation to coordinate them). As we show in Section 7, to exceed C_1,1 it is crucial to be able to refine a measurement made on a given signal after making intervening measurements on other signals.

In our adaptive protocol for lifted trines, we use two rounds of measurements. We first make one measurement on each of the signals received; this measurement only partially reduces the quantum state of some of the signals. We then make a second measurement (on some of the signals) which depends on the outcomes of the first round of measurements.

A precursor to this type of adaptive strategy appeared in an influential paper of Peres and Wootters [10] which was a source of inspiration for this paper. In their paper, Peres and Wootters studied strategies of adaptive measurement on the tensor product of two trine states, in which joint measurements on both copies were not allowed. They showed that for a specific encoding of block length 2, adaptive strategies could extract strictly more information than sequential strategies, but not as much as was extractable through joint measurements. However, the adaptive strategies they considered extracted less information than the C_1,1 capacity of the trine states, and so could have been improved on by using a different encoding and a sequential strategy. We show that for some values of , C_1,A is strictly greater than C_1,1 for the lifted  trines T(), where these capacities are defined using arbitrarily large block lengths and arbitrary encodings. It is open whether C_1,1 = C_1,A for the planar trine states.

Before we describe our measurement strategy, we describe the codewords we use for information transmission. The reason we choose these codewords will not become clear until after we have given the strategy. Alice will send one of these codewords to Bob, who with high probability will be able to deduce which codeword was sent from the outcomes of his measurements. These codewords are constructed using a two-stage scheme corresponding to the two rounds of our measurement protocol. Effectively, we are applying Shannon's classical channel coding theorem twice.

To construct a codeword, we take two error-correcting codes each of block length n and add them letterwise (mod 3). The first code is over a ternary alphabet (which we take to be {0, 1, 2}); it contains 2^₁n-o(n) codewords, and is a good classical error-correcting code for a classical channel we describe later. The second code contains 2^₂n-o(n) codewords, is over the binary alphabet {0, 1}, and is a good classical error-correcting code for a different classical channel. Such classical error-correcting codes can be constructed by taking the appropriate number of random codewords; for the proof that our decoding strategy works, we assume that the codes were indeed constructed this way. To obtain our code, we simply add these two codes bitwise (mod 3). For example, if a codeword in the first (ternary) code is 0212 and a codeword in the second (binary) code is 1110, the codeword obtained by adding them bitwise is 1022. This new code contains 2^{(₁+₂)n-o(n)} codewords (since we choose the two codes randomly, and we make sure that ₁ + ₂ < log₂ 3).

To show how our construction works, we first consider the following measurement strategy. This is not the best protocol we have found, but it provides a good illustration of how our protocols work. This uses the two-level codeword scheme described above. In this protocol, the first measurement we make uses a POVM which contains four elements. One of them is a scalar times the matrix

which projects the lifted trine states onto the planar trine states. The other three elements correspond to the three vectors which are each perpendicular to two of the trine states; these vectors are

Note that <D_b1|T_b2> = 0 if and only if b₁ ≠ b₂.

We now scale _xy and D_i so as to make a valid POVM. For this, we require that the POVM elements sum to the identity, i.e., that ∑³_i=0 A_i^†A_i = I. This is done by choosing

When we apply this POVM, the state |v> is taken to the state A_i|v> with probability <v|A_i^†A_i|v>. When this operator is applied to a trine state T_b(), the chance of obtaining D_b is 3, and the chance of obtaining _xy is 1 – 3. If the outcome is D_b, we know we started with the trine T_b, since the other two trines are perpendicular to D_b. If we obtain the fourth outcome, _xy, we gain no information about which of the three trine states we started with, since all three states are equally likely to produce _xy.

We now consider how this measurement combines with our two-stage coding scheme introduced above. We first show that with high probability we can decode our first code correctly. We then show that if we apply a further measurement to each of the signals which had the outcome _xy, with high probability we can decode our second code correctly.

In our first measurement, for each outcome of the type D_b obtained, we know that the trine sent was T_b. However, this does not uniquely identify the letter a in the corresponding position of the first-stage code, as the trine T_b sent was obtained by adding either 0 or 1 to a (mod 3) to obtain b. Thus, if we obtained the outcome D_b, the corresponding symbol of our first-stage codeword is either b or b – 1 (mod 3), and because the second code is a random code, these two cases occur with equal probability. This is illustrated in Figure 8; if the codeword for the first-stage code is a, the outcome of the first measurement will be D_a with probability 3/2, D_a+1(mod3) with probability 3/2, and _xy with probability 1 – 3. This is a classical channel with capacity 3(log₂ 3 – 1): With probability 3, we obtain an outcome D_x for some x, and in this case we obtain (log₂ 3 – 1) bits of information about the first-stage codeword; with probability 1 – 3, we obtain _xy, which gives us no information about this codeword. By Shannon's classical channel coding theorem, we can now take ₁ = 3(log₂ 3 – 1), and choose a first-stage code with 2^₁n-o(n) codewords that is an error-correcting code for the classical channel shown in Figure 8. Note that in this calculation, we are using the fact that the second-stage code is a random code to say that measurement outcomes D_a and D_a+1(mod3) are equally likely.

Figure 8

Once we have decoded the first-stage code, the uncertainty about which codeword we sent is reduced to decoding the second-stage code. Because the second code is binary, the decoding of the first-stage code leaves in each position only two possible trines consistent with this decoding. This means that in the approximately (1 – 3)n positions where the trines are projected into the plane, we now need only distinguish between two of the three possible trines. In these positions, we can use the optimal measurement for distinguishing between two planar trine states; recall that this is a von Neumann measurement which gives 1 – H(1/2 + /4) = 0.64542 bits of information per position. In the approximately 3n remaining positions, we still know which outcome D_b was obtained in the first round of measurements, and this outcome tells us exactly which trine was sent. Decoding the first-stage code left us with two equally likely possibilities in the second-stage code for each of these positions. We thus obtain one bit of information about the second-stage code for each of these approximately 3 positions. This analysis shows that the second-stage code must be a good classical error-correcting code for the channel shown in Figure 9. This channel has capacity 0.64542(1 – 3) + 3 bits. Thus, by Shannon's theorem, if we set ₂ = 0.64542(1 – 3) + 3 bits, there is a classical error-correcting code which can be used for the second stage and which can almost certainly be decoded uniquely. Adding ₁ and ₂, we obtain a channel capacity of 0.64542(1 – 3) + (log₂ 3)(3) bits; this is the line interpolating between the points = 0 and = 1/3 on the curve for C_1,1. As can be seen from Figure 10, for small this strategy indeed does better than our best protocol for C_1,1.

Figure 9   Figure 10

The above strategy can be viewed in a slightly different way, this time as a three-step process. In the first step, our measurement either lifts the three trine states up until they are all orthogonal, or projects them into the plane. This first step lifts approximately 3n trines up and projects approximately (1 – 3)n trines into the plane. After this first step, we first measure the trines that are lifted farther out of the plane, yielding log₂ 3 bits of information for each of these approximately 3n positions. The rest of the strategy then proceeds exactly as above. Note that this reinterpretation of the strategy is reminiscent of the two-stage description of the six-outcome POVM for accessible information in Section 2.

We now modify the above protocol to give the best protocol we currently know for the adaptive capacity C_1,A. We first make a measurement which either projects the trines T() to the planar trines T(0) or lifts them out of the plane to some fixed height, yielding the trines T(₂); this measurement requires < ₂. (Our first strategy is obtained by setting ₂ = .) We choose ₂ = 0.087247; this is the point where the convex hull of the curve representing the C_1,1 capacity meets this curve [see Figure 10(b)]; at this point C_1,1 is 1.03126 bits. It is easy to verify that with probability 1 – /₂, the lifted trine T_b() is projected onto a planar trine T_b(0), and with probability /₂, it is lifted up to T_b(₂). We next use the optimum von Neumann measurement V(0) = Q(2/3) on the trine states that were lifted out of the plane.

We now analyze this protocol in more detail. Let

(19)

The first-stage code gives an information gain of

for each of the approximately (/₂)n signals which were lifted out of the plane. This is because the symbol a in the first-stage code is first taken to T_a or T_a+1(mod3) with a probability of ½ each (depending on the value of the corresponding letter in the second-stage code). We thus obtain each of the two outcomes V_a, V_a+1(mod3) with probabilities ½p + ½(1 – p)/2 = ¼(1 + p), and obtain the outcome V_a+2(mod3) with probability ½(1 – p). Thus, if we start with the symbol a in the first-stage code, the entropy of the outcome of the measurement [i.e., H(X_out|X_in)] is it is easy to see that H(X_out) is log₂ 3. From classical Shannon theory, we find that we can take ₁ = 0.35453(/₂).

The design of our codewords ensures that knowledge of the first codeword eliminates one of the three signal states for each of the trines projected into the plane. This allows us to use the optimal C_1,1 measurement on the planar trines, resulting in an information gain of 0.64542 bits for each of these approximately (1 – /₂)n signals. We obtain

for each of the approximately /₂ signals that were lifted out of the plane; this is explained in more detail later. In combination, this results in a capacity of

(20)

bits per signal; this formula linearly interpolates between the C_1,1 capacity for T(0) and the C_1,1 capacity for T(₂).

Why do we obtain the weighted average of C_1,1 for T(0) and C_1,1 for T(₂) as the C_1,1 for T(), 0 < < ₂? This happens because we use all of the information that was extracted by both of the measurements. The measurements on the trines that were projected onto the plane give information about only the second code, and provide 0.64542 bits of information per trine. For the trines T(₂) that were lifted out of the plane, we use part of the information extracted by their measurements to decode the first code, and part to decode the second code. For these trines, in the first step, we start with the symbols {0, 1, 2} of the first-stage code with equal probabilities. A 0 symbol gives measurement outcome V₀ with probability , V₁ with probability , and V₂ with probability and similarly for the other signals. The information gain from this step is thus

(21)

per signal. At the start of the second step, we have narrowed the possible states for each signal down to two equally likely possibilities. This information gain for this step comes from the case where the outcome of the measurement was V_b, and where one of the two possible states (consistent with the first-stage code) is T_b. This occurs with probability ½(1 + p). In this case, we obtain a binary symmetric channel with crossover probability 2p/(1 + p). In the other case, where the measurement was V_b and neither of the two possible states consistent with the first-stage code is b, we gain no additional information, since both possible states remain equally likely. The information gain from the second step is thus

(22)

per signal. Adding the information gains from the first two stages [Equations (21) and (22)] together gives

(23)

which is the full information gain from the measurement on the trine states that were lifted farther out of the plane; that this happens is, in some sense, an application of the chain rule for classical entropy [13].

5. The upper bound on C_1,1

In this section, we show that for the lifted trines T(), if is small, the C_1,A capacity is exponentially close to the accessible information obtainable using just two of our trines, showing that the three red curves in Figure 4 are exponentially close when is close to 0.

First, we need to prove that in a classical channel, changing the transition probabilities by can only change the Shannon information by O(– log₂ ). The Shannon capacity of a classical channel with input distribution p_i and transition probabilities q_ij is the entropy of the output less the entropy of the output given the input, or

(24)

Suppose we change all the q_ij by at most . I claim that the above expression changes by at most –2N_out log₂ . Each of the terms q_ijlog₂ q_ij in the second term changes by at most – log₂ , and adding these changes (with weights p_i) gives a total change of at most –N_out log₂ . Similarly, each of the terms ∑_i p_iq_ij in the first term of (24) changes by at most , and there are at most N_out of them, so we see easily that the first term also contributes at most –N_out log₂ to the change. For N_out ≤ 6, which by the real version of Davies' theorem is sufficient for the optimum measurement on the lifted trines, we have that the change is at most –12 log₂ .

Next, we need to know that the C_1,1 capacity for the planar trines is maximized using the probability distribution (0, ½, ½) We discuss this at more length in Appendix A, where we sketch a proof that the point (0, ½, ½) is a local maximum for the accessible information. This proof must be supplemented by numerical calculation showing that this local maximum is indeed a global maximum; the results of this calculation are given in Appendix C. (However, it should be noted that we have not made this a mathematically rigorous demonstration; we believe that this is possible, but to do so would require computing rigorous error bounds and possibly substantially more computer time.) The proof in Appendix A also shows that to achieve a capacity close to C_1,1 one must use a probability distribution and measurement close to those achieving the optimal, a fact we use in this section.

We can now deal with lifted trines. We consider the trine states T() for small . By moving each of the trines T() by an angle of = arcsin < 2, we can obtain the planar trines T(0). We now have that the difference between the transition probabilities for T() and T(0) for any rank-1 element in a POVM is at most , since the transition probability for a fixed POVM element r|v><v| is a constant multiple (with the constant being r ≤ 1) of the square of the cosine of the angle between the vectors |v> and |T_b>, and this angle changes by at most . Thus, by the lemma above, the C_1,1 capacity for the lifted trines T() differs by no more than = –12 log₂ from the capacity obtained when the same probabilities (and measurement) are used for the planar trine states T(0).

For the lifted trine states T(), we know (from Section 3) that the C_1,1 capacity C_1,1() is greater than C_1,1(0), the capacity for the planar trine states. If we apply to the planar trine states T(0) the same measurements and the same probability distribution that give the optimum C_1,1 capacity for the lifted trine states T(), we know that we have changed the capacity by at most = –12 log₂ . We thus have that C_1,1(0) < C_1,1() < C_1,1(0) + , and that the measurements and probability distribution that yield the optimum capacity C_1,1() for the lifted trines T() must give a capacity of at most C_1,1(0) – when applied to the planar trines. This limits the probability distribution and measurement giving the optimum capacity C_1,1 for the lifted trines. For sufficiently small , the optimum probability distribution on the trines must be close to (0, ½, ½), and when the optimum projectors are projected onto the plane, nearly all of the mass must be contained in projectors within a small angle of the optimum projectors for C_1,1(0), namely (1, ±1).

We now consider the derivative of the information capacity obtained when the measurement is held fixed, and p₀ is increased at a rate of 1 while p₁ and p₂ are decreased, each at a rate of 1/2. Taking the derivative of (24), we obtain

(25)

where p₀' = 1 and p₁' = p₂' = –1/2. This derivative can be broken into terms associated with each of the projectors in the measurement. Namely, if the jth POVM element is r_j|v><v|, the associated term is

where q_iv = |<T_i|v>|², p₀' = 1, and p₁' = p₂' = -1/2. The r_j can be factored out, and this term can be written as r_jI_v', where we define

(26)

It is easy to see that for the planar trines, a projector v = (cos , sin ) with sufficiently close to ±/4 and a probability distribution sufficiently close to (0, ½, ½), the term I_v' is approximately –0.3227 bits, the value of I_v' at = ±/4, and the probability distribution (0, ½, ½). Similarly, for the planar trines, if the probability distribution is close to (0, ½, ½), I_v' can never be much greater than 2 bits, which is the maximum value for the probability distribution (0, ½, ½) (occurring at = 0). These facts show that if is sufficiently small, the formula (25) for the derivative of the accessible information is negative and bounded above by (say) –0.64 bits when the planar trines are measured with the optimum POVM for C_1,1(). This is true because ∑_j r_j = 2, and all but a 1 – fraction of the mass must be in projectors v for near ±/4; each of these projectors contributes at least 0.321r_j (say) to the derivative, and   the projectors  with not  near ±/4 cannot change this result by more than 4. For the optimum measurement and probability distribution for C_1,1() to have a non-zero value of p₀ (as we know it does from Section 3), this negative derivative must be balanced by a positive derivative acquired by some projectors when the trines are lifted out of the plane. We show that this can happen only when p₀ is exponentially small in 1/; for larger values of p₀, the positive component acquired when the trines are lifted out of the plane is dwarfed by the negative component retained from the planar trines.

We have shown that I_S' < –0.64 bits near the probability distribution (0, ½, ½) when the optimal measurement for T() is applied to the planar trines, assuming sufficiently small . We also know from the concavity of the mutual information that for the lifted trines T() with > 0, the derivative I_S' is positive for any probability distribution (p₀ – t, p₁ + t/2 p₂ + t/2) where (p₀, p₁, p₂) is the optimal probability for C_1,1 capacity and 0 < t ≤ p₀. Thus, we know that the negative derivative for the planar trines must be balanced by a positive derivative acquired by some projectors when one considers the difference between the planar trines and the lifted trines. We show that this can happen only when the probability p₀ is exponentially small in the lifting angle . This shows that at the probability distribution achieving C_1,1, p₀ is exponentially small in 1/ = 1/arcsin .

Consider the change in the derivative I_vj' for a given projector v_j when the trines T(0) are lifted out of the plane to become the trines T(). To make I_vj' positive, this change must be at least 0.64 bits. Let the transition probabilities with the optimal measurement for C_1,1() be r_jq_ivj and the transition probabilities for the same measurement applied to the planar trines be r_jivj. Since the constant factors r_j multiplying the projectors sum to 3, we have that the value I_v' for one projector v must change by at least 0.21 bits, that is,

where _iv = |<T_i(0)|v>|² and q_iv = |<T_i()|v>|², as before. We know that |_iv – q_iv| ≤ .

We first consider the last term of (27),

This is easily seen to be bounded by –6 log₂ , which approaches 0 as approaches 0.

Next, consider the first terms of (27),

(27)

Bounding this is a little more complicated. First, we derive a relation among the values of _iv for different i. We use the fact that for the planar trines

Taking the inner product with <v_j|, we obtain

And now, using the fact that _iv = |<v_j|T_i(0)>|², we see that

(28)

Using (28), and the fact that p₁, p₂ are close to ½, we have that

(29)

for sufficiently small . We also need a relation among the q_iv. We have

(30)

where the second step follows because the minimum eigenvalue of |T₀><T₀| + |T₂><T₂| + |T₂><T₂| is > ²/4.

We now are ready to bound the formula (27). We break it into two pieces; if this expression is at least 0.2 bits, one of these two pieces must be at least 0.1 bits. The two pieces are as follows:

(31)

and

(32)

We first consider the case of (31). Assume that it is larger than 0.1 bits. Then

(33)

(34)

where the first step follows from the facts that |q_iv – _iv| < and p₀ is the smallest of the p_i, and the second step follows from (30). Thus, if the quantity (31) is at least 0.1, we have that

showing that p₀ is exponentially small in 1/.

We next consider the case (32). Assume that

is larger than 0.1 bits. We know that

Thus, for (32) to be larger than 0.1, we must have that

We know that the numerator and denominator inside the logarithm differ by at most . It is easy to check that if |log₂(x/y)| > 0.05, and x – y ≤ , both x and y are at most 15. Thus,

(35)

Further,

(36)

where the second inequality follows by (29) and the third by (35).

Since the two terms in (32) are of opposite signs, if they add up to at least 0.1 bits, at least one of them must exceed 0.1 bits by itself. We treat these two cases separately. First, assume that the first term exceeds 0.1. Then

where the last inequality follows from (30) and (36). If this is at least 0.1, we again have that p₀ is exponentially small in 1/.

Finally, we consider the case of the term

We have by (29) that

which, since ∑²_i=0iv < 120, can never exceed 0.1 for small , as it is of the form -8x log x for a small x.

Since p₀ is exponentially small in 1/, we have that the difference between the C_1,1 capacity using only two trines and the one using all three trines is exponentially small in 1/, showing that our guesses in Section 3 are exponentially close to the correct C_1,1 capacity as goes to 0, and thus showing that C_1,A is strictly larger than C_1,1 in a region near = 0.

6. C_1,1 = C_1,A for two pure states

In this section, we prove that for two pure states, C_1,1 = C_1,A. We do this by giving a general upper bound on C_1,A based on a tree construction. We then use the fact that for two pure states, accessible information is concave in the probabilities of the states (proved in Appendix B) to show that this upper bound is equal to C_1,1 for ensembles containing only two pure states.

For the upper bound, we consider a class of trees, with an ensemble of states associated with each node. The action of Bob's measurement protocol on a specific signal will generate such a tree, and analyzing this tree will bound the amount of information Bob can on average extract from that signal. Associated with each tree will be a capacity, and the supremum over all trees will give an upper bound for C_1,A.

We now describe our tree construction in general. Let us suppose that Alice can convey to Bob one of m possible signal states. Let these states be _i, where 1 ≤i ≤ m. To each tree node we assign m density matrices and m associated probabilities (these will not be normalized, and so may sum to less than 1). For node x of the tree, we associate some POVM element E_x, and the m density matrices E_x^1/2_iE_x^1/2/Tr E_xi, where _i are the original signal states. (We may omit the normalization factor of Tr E_xi in this discussion when it is clear from context.) For the root node r, the POVM element E_r is the identity matrix I, and the probability p_r,i is the probability that this signal is _i. A probability p_x can be associated with node x by summing p_x = ∑_i=1^m p_x,i. For the root, p_r = 1. For any node x, its associated probability p_x will be equal to the sum of the probabilities p_yj associated with its children yj. There are two classes of nodes, distinguished by the means of obtaining its children from the node. The first class we call measurement nodes and the second we call probability-refinement (or refinement) nodes. For a measurement node x, we assign to each of the children yj a POVM element E_yj, where ∑_j E_yj = E_x. The density matrices associated with a child of x will be E_yj^1/2_iE_yj^1/2/Tr E_yji, and the probability associated with the density matrix E_yj^1/2_iE_yj^1/2/Tr E_yji will be p_yj,_i = p_x,iTr (E_yji)/Tr (E_xi). Finally, we define the information gain associated with a node x. This is 0 for nodes which are not measurement nodes, and

where H({q_i}) is the Shannon information ∑_i q_i log₂q_i of the probability distribution {q_i}.

We now explain why we chose this formula. We consider applying a measurement to the ensemble associated with node x. This ensemble contains the state E_x^1/2_iE_x^1/2/Tr (_iE_x) with probability p_x,i /p_x. Let us apply the measurement that takes to A_kA_k^† with probability
Tr A_k^†A_ki, where ∑_k A_k^†A_k = I. Each child yk of x is associated with one of the matrices A_k. Let E_yk = E_x^1/2A_k^†A_kE_x^1/2. Then ∑_k E_yk = E_x. Now, after we apply A_k to E_x^1/2_iE_x^1/2, we obtain the state A_kE_xiE_xA_k^†. This happens with probability

The state we obtain, A_kE_x^1/2_iE_x^1/2A_k^†, is unitarily equivalent to E_yk^1/2_iE_yk^1/2, so this latter state can be obtained by an equivalent measurement. The information I_x associated with the node x is the probability of reaching the node times the Shannon information gained by this measurement if the node is reached. Summing I_x over all the nodes x of the tree gives the expected information gain by measurement steps.

The second class of nodes are probability-refinement nodes (which we often shorten to refinement nodes). Here, for all the children {yk} of x, E_x = E_yk. We assign probabilities p_yk,i to the children yk so that ∑_k p_yk,i = p_x,i. For this class of nodes, we define I_x to be 0. These nodes correspond to steps in the protocol where additional information is gained about one signal state in the codeword by measuring different signal states in the codeword.

To find the upper bound on the C_1,1 capacity for a set of states {_i}, we take the supremum over the information gain associated with all trees of the above form. That is, we try to maximize ∑_x I_x over all probability distributions p_r,i on the root node r, all ways of splitting E_x = ∑_k E_yk for measurement nodes x, and all ways of splitting probabilities p_x,i = ∑_k p_yk,i for refinement nodes x and signal states i. (And if this maximum is not attained, we take the supremum.)

To prove that this is the correct upper bound, we track the information obtained from a single signal (i.e., channel output) S in the protocol used by Alice and Bob, assuming that Alice sends Bob a set of states and Bob performs measurements on them one at a time. We keep track at all times t (i.e., for all nodes x of the tree) of the probability that signal S is in state E_x^1/2_iE_x^1/2. There are two cases, depending on which signal Bob measures. In the first case, when Bob measures signal S, we perform a measurement on the current tree node x that splits each of the possible values of _t,i for this signal S into several different values. This case corresponds to a measurement node of the tree. We can assume without loss of generality that for his measurement Bob uses the canonical type of operators discussed above, so that E_x^1/2_iE_x^1/2 goes to E_yk^1/2_iE_yk^1/2 with probability Tr E_yki /TrE_xi. Thus, we now have several different ensembles of density matrices, the kth of which contains E_yk^1/2_iE_yk^1/2/TrE_yki with (unnormalized) probability p_x,iTrE_yki /TrE_xi = py_k,_i. In this step Bob can extract some information about the original codeword, and the amount of this information is at most I_x.

The second case comes when Bob measures signals other than S. These steps can provide additional information about the signal S, so if the probability distribution before this step contained E_x^1/2_iE_x^1/2 with probability p_x,i, we now have several distributions, each assigned to a child of x; the jth distribution contains E_x^1/2_iE_x^1/2 with (unnormalized) probability p_yj,_i. Here, we must have ∑_j p_yj,i = p_x,i. This kind of step corresponds to a probability-refinement node in the tree. The information gained by these measurement steps can be attributed to the signals that are actually measured in these steps, so we need not attach any information gain to the refinement steps in the tree formulation. Averaging the information gain over the trees associated with all of the signals gives the capacity of the protocol, which is the expected information gain per signal sent.

There are several simplifying assumptions we can make about the trees. First, we can assume that nodes just above leaves are measurement nodes that contain only rank-1 projectors, since any refinement node having no measurement nodes below it can be eliminated without reducing the information content of the tree, and since the last measurement might as well extract as much information as possible. We could assume that the types of the nodes are alternating, since two nodes of the same type, one a child of the other, can be collapsed into one node. In the sequel, we perform this collapse on the measurement nodes, so we assume that all children of measurement nodes are refinement nodes. We could also (but not simultaneously) assume that every node has degree two, since any measurement with more than two outcomes can be replaced with an equivalent sequence of measurements, each having only two outcomes, and any split in probabilities can be replaced by an equivalent sequence of splits. In the sequel we assume that all probability-refinement nodes are of degree two.

One interesting question is whether any tree of this form has an associated protocol. The upper bound will hold whether or not this is the case, but if there are trees with no associated protocols, the bound may not be tight. We do not know the answer to this, but suspect that there are trees with no associated protocols. Our (vague) intuition is that if the root node is a measurement node with no associated information gain, and all children of this node are refinement nodes, there appears to be no way to obtain the information needed to perform one of these refinement steps without also obtaining the information needed to perform all of the other refinement steps of the root node. However, making this much information available at the top node would reduce the information that could be obtained using later measurement nodes. It is possible that this difficulty can be overcome if there is a feedback channel available from the receiver to the sender. We thus boldly conjecture the following.

If arbitrary use of a classical feedback channel from the sender to the receiver is available for free, then the adaptive capacity with feedback C_1,AF is given by the supremum over all trees of the above type of the information associated with that tree.

As mentioned above, the supremum of the extractable information over all trees is an upper bound on C_1,A, since it is at least as large as the information corresponding to any possible adaptive protocol. We now restrict our discussion to the case of ensembles consisting of two pure states, and prove that in this case we have equality, since both of these bounds are equal to the C_1,1 capacity. Consider a tree which gives a good information gain for this ensemble (we would say maximum, but have no proof that the supremum is obtainable). There must be a deepest refinement node, so all of its descendants are measurement nodes. We may without loss of generality assume that this deepest refinement node has only two children. Each of these two children has an associated ensemble consisting of two pure states with some probabilities. The maximum information tree will clearly assign the optimum measurement to these nodes. However, an explicit expression for this optimum measurement is known [2–5], and as is proved in Appendix B, the accessible information for ensembles of two given pure states is concave in the probabilities of the states. Thus, if we replace this refinement node with a measurement node, we obtain a tree with a higher associated information value. Using induction, we can perform a series of such steps which do not decrease the information gain associated with the tree while collapsing everything to a single measurement. Thus, for two pure states, we have C_1,1 = C_1,A.

The above argument would work to show that C_1,1 = C_1,A for ensembles consisting of two arbitrary density matrices if we could show that the accessible information for two arbitrary density matrices is concave in the probabilities of these two density matrices. It would seem intuitively that this should be true, but we have not been able to prove it. It may be related to the conjecture² [4] that the optimal accessible information for two arbitrary density matrices can always be achieved by a von Neumann measurement. This has been proved in two dimensions [4] and is supported by numerical studies in higher dimensions.² We thus conjecture the following.

C_1,A = C_1,1 for two mixed states in arbitrary dimensions.

In fact, the proof in this section works for any upper bound on accessible information which has both the concavity property and the property that if a measurement is made on the ensemble, the sum of the information extracted by this measurement and the expected upper bound for the resulting ensemble is at most the original upper bound. The Fuchs–Caves bound [16] (which was Holevo's original bound) may have these properties; we have done some numerical tests and have not found a counterexample. For three planar trine states with equal probabilities, this gives an upper bound of approximately 0.96.

7. Discussion

If we force Bob to measure his signals sequentially, so that he must complete his measurement on signal k before he starts measuring signal k + 1 (even if he can adaptively choose the order in which he measures the signals and even if a feedback channel is applied from Bob to Alice), Bob can never achieve a capacity greater than C_1,1. This can easily be seen. Without decreasing the capacity, we assume that Bob uses a feedback channel to send all of the information that he has back to Alice. This information consists of the results of the measurement and the measurement that he plans to perform next. The ensemble of signals that Alice now sends Bob can convey no more information than the optimal set of signals for this measurement. However, it now follows from classical information theory that such a protocol can never have a capacity greater than the sum of the optimal information gains for all of these measurements, which is at most C_1,1.

It is thus clear that the advantage of adaptive protocols is obtained from the fact that Bob can adjust subsequent measurements of a signal depending on the outcome of the first round of measurements on the entire codeword. In the information decision tree of Section 6 for our protocol (see Figure 11), the crucial fact is that we first either project each of the trine states into the plane or lift it up. We then arrange to distinguish between only two possible states for those signals that were projected into the plane, and among all three possible states for those signals that were lifted.

Figure 11

As we showed in Section 6, C_1,1 = C_1,A for two pure states, and this proof can be extended to apply to two arbitrary states if a very plausible conjecture on the accessible information for a two-state ensemble holds. For three states, even in two dimensions, the same upper bound proof cannot apply. However, for three states in two dimensions, it may still be that C_1,1 = C_1,A. We have tried unsuccessfully to find strategies that perform better than the C_1,1 capacity for the three planar trine states, and we now suspect that the adaptive capacity is the same as the C_1,1