{'fraction_non_alphanumeric': 0.04584515605999189, 'fraction_numerical': 0.015018240778273207, 'mean_word_length': 4.174182046979865, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Quantum State Detector Design: Optimal Worst-Case a posteriori Performance

The problem addressed is to design a detector which is maximally sensitive to specific quantum states. Here we concentrate on quantum state detection using the worst-case a posteriori probability of detection as the design criterion. This objective is equivalent to asking the question: if the detector declares that a specific state is present, what is the probability of that state actually being present? We show that maximizing this worst-case probability (maximizing the smallest possible value of this probability) is a quasiconvex optimization over the matrices of the POVM (positive operator valued measure) which characterize the measurement apparatus. We also show that with a given POVM, the optimization is quasiconvex in the matrix which characterizes the Kraus operator sum representation (OSR) in a fixed basis. We use Lagrange Duality Theory to establish the optimality conditions for both deterministic and randomized detection. We also examine the special case of detecting a single pure state. Numerical aspects of using convex optimization for quantum state detection are also discussed.


Introduction
why Information is extracted from a quantum system by measurement. The most information that it is possible to extract from the quantum system is given by its state, specified by a density operator, and it is impossible to determine this from a single measurement. The problem of detecting information stored in the state of a quantum system is therefore a fundamental problem in quantum information theory. The nature of this problem is essentially the design of measurements such that they yield the optimum information for the specified purpose. That is, the construction of matrices representing positive operator valued measures (POVMs) which give the best performance against a given set of criteria, subject to constraints reflecting the underlying properties of the quantum mechanics, or costs associated with the implementation of certain operations.
The emergence of quantum information processing has raised important new issues, and made more urgent the development of tools for the design of quantum measurements. In this paper we present a general formalism that enables this design across a wide range of applications. In particular we show that the problem may be cast in the form of a convex optimization over the possible POVMs, and that this allows powerful numerical tools to identify the globally optimal measurements to achieve the desired objective. Such optimizations are useful even if they turn out to be difficult to implement in the laboratory, since they provide a benchmark for the performance of experimentally feasible measurements.
The objective of a measurement in quantum information theory depends on the way in which information is encoded into the quantum system to begin with, and this is in turn, depends on the application. In quantum cryptography, for example, the information is encoded by the sender choosing randomly between two non-orthogonal bases, both of which can encode a single bit. The ability of an eavesdropper, who is in principle unable to influence the choice of preparation and measurement bases chosen by the sender and receiver of this information, to extract information from the transmitted quantum bits, depends on her ability to determine which of four non-orthogonal states were sent. In a quantum information processor, the information in the register at the end of a computation often resides in orthogonal states, and the goal of the measurement is simply to read out the register by distinguishing among the sets of such states. However, the operation of such a processor may itself depends on measurements. For example, quantum error correction protocols require the measurement of an ancilla to preserve the quantum state of the register itself. In another example, the cluster computing model [40] and the linear optical quantum computer [29], both rely on measurements of ancillary qubits for the operation of the logic gates themselves.
In these examples of conditional state preparation, it is vital that there is a high degree of correlation between the outcome of the measurement and the quantum state prepared in the register by the measurement. The structure of the measurement should therefore be such that this correlation is maximized. Thus it is vital to consider the case when the detectors have noise, and to develop strategies for optimizing the measurement in the presence of this and inherent inefficiencies. Despite the fundamental inability to determine the quantum state of a system from a single measurement, it is sometimes useful to make such a determination from a set of independent measurements on identically prepared systems. This procedure is called quantum state tomography. Similarly, one may characterize the action of a quantum operation by determining its effect on a known input quantum state from a determination of the output state. In this application, the central questions are: how many measurements are needed to determine the state to within a given precision, and how should these measurements be constructed? That is, it is essentially a problem of experiment design. Optimal experiment for quantum state tomography and quantum process tomography is considered in [30].
In this work, we concentrate on the problem of quantum state detection. That is, the design of POVMs that can determine whether or not a particular component was present in the input state to the detector. The problem is thus equivalent to the design of a quantum channel that optimally transforms the input state distribution (assumed to be given, and including non-orthogonal states) to the output measurement outcomes. The channel may be lossy, and may introduce noise, and thus there may be latency in the measurement, in which certain outcomes are ambiguous.
previous work Several approaches have emerged for distinguishing between a collection of nonorthogonal quantum states. An accessible review can be found in the article by Chefles [8]. In one approach, called quantum hypothesis testing, a measurement is designed to minimize the probability of a detection error [25,23,44,17,6,35,2,15,16,14]. Necessary and sufficient conditions for an optimum measurement maximizing the probability of correct detection have been developed in [17] using a semidefinite programming approach, and earlier in [25] (the drawback of this approach is that it does not readily lend itself to efficient computational algorithms). Closed-form analytical expressions for the optimal measurement have been derived for several special cases [23,6,35,2,15,16]. Iterative procedures maximizing the probability of correct detection have also been developed for cases in which the optimal measurement cannot be found explicitly [24,17]. A specific design for achieving the optimal discrimination between non-orthogonal coherent states has been given in [3], and for non-orthogonal polarization states of a single photon by [4]. Optimal discrimination amongst more than two non-orthogonal states has also been analyzed [39] and demonstrated experimentally [10].
A more recent approach, referred to as unambiguous detection [27,11,36,28,38,7,9,13,12,18], is to design a measurement that with a certain probability returns an inconclusive result, but such that if the measurement returns an answer, then the answer is correct with probability 1. Chefles [7] showed that a necessary and sufficient condition for the existence of unambiguous measurements for distinguishing between a collection of pure quantum states is that the states are linearly independent. Necessary and sufficient conditions on the optimal measurement minimizing the probability of an inconclusive result for pure states were derived in [13]. The optimal measurement when distinguishing between a broad class of symmetric pure-state sets was also considered in [13]. The problem of unambiguous detection between mixed state ensembles was first considered in [41]. Necessary and sufficient optimality conditions for unambiguous mixed state detection were developed in [18].
Experimental configurations may not allow the ideal measurements to be made, and thus the performance of feasible apparatuses have been analyzed. For example, an apparatus for the unambiguous discrimination between two orthogonal states of a single photon using homodyne detection, rather than photon counting, which has higher losses and more noise, has been examined in [22] and [33]. An experimental implementation of the process for discriminating unambiguously between two non-orthogonal states of polarization of a single photon has been demonstrated in [26].
An interesting alternative approach for distinguishing between a collection of quantum states, which is a combination of the previous two approaches, is to allow for a certain probability of an inconclusive result, and then maximize the probability of correct detection [12,45,20].
what's new here Prior work has considered optimal detector design only for an average measure of the probability of detection, such as the average joint probability of detection. For example, in [17,13] it is shown that using this criterion, detector design can be formulated as a convex optimization over the matrices in the POVM, specifically a semidefinite program (SDP). Here we concentrate on quantum state detection using the worst-case a posteriori probability of detection as the design criterion. This objective is equivalent to asking the question: if the detector declares that a specific state is present, what is the probability of that state actually being present? We show that maximizing the smallest possible value of this probability is a quasiconvex optimization over the POVM matrices, or over the Krause operator-sumrepresentation (OSR) in a fixed basis. Issues relating to conditions of optimality and numerical aspects of convex optimization of state detection are also discussed.
We will show that many of the standard measures of detector performance (including those previously considered) are also convex functions of the detector design parameters. In addition, we will see that the design parameters, either POVM or OSR, are in a convex set. As a result we can cast a number of detector design problems as a convex optimization. Details and underlying theory about convex optimization are in the text by Boyd and Vandenberghe [5]. As stated there, the great advantage of convex optimization is a globally optimal solution can be found efficiently and reliably, and perhaps most importantly, can be computed to within any desired accuracy using an interior-point method.
Another advantage to being able to obtain a globally optimal solution is that the resulting performance can be used as a benchmark against which the initial detector design can be compared. If the optimal performance is significantly better, then there is compelling reason to try and implement the optimal solution or to try and modify the initial design in the "direction" of the optimal solution, if that is clear from the physical implementation.
In a few instances we use Lagrange Duality Theory to derive formulas for direct calculation of the optimal objective value and the associated POVM matrices. These calculations only involve singular value decomposition of the problem data.

Detector
A quantum state detector is considered here as an input/output device mapping a state (density matrix) ρ ∈ C n×n at the input into one of a number of discrete outcomes at the output as illustrated in Figure 1. Specifically, the input state is drawn randomly from where p i is the occurence probability of ρ i , that is, The set of detector outcomes is, The problem addressed is to design the detector to be able to determine the presence of some or all of the specified set of input states given knowledge of the input set D in and the associated occurrence probabilities. Although the principal focus is on an equal number of state inputs and detector outcomes, this is not always the case , e.g., noisy measurements can result in unequal inputs and outcomes as briefly discussed in Section 5.1.

Performance probabilities
Detector performance is usually assessed by examination of one or more of the following probability matrices: joint probability matrix p joint (i, j) = Prob {detect i AND input j} conditional probability matrix p out|in (i|j) = Prob {detect i GIVEN input j} a posteriori probability matrix p in|out (j|i) = Prob {input j GIVEN detect i} As shown in any standard text [21] these probabilities are related as follows: Without loss of generality we can order the input and output events so that detector event 1 corresponds to input event 1, detector event 2 to input event 2, and so on. With this ordering, detector performance can be assessed by the error probabilities: Observe that each of these is the sum of the off-diagonal elements of the corresponding probability matrices (4). Being error probabilities, they all range from zero to one: e joint (i), e cond (i), e post (i) ∈ [0, 1], i = 1, . . . , m As we will see shortly, it is convenient to express each of the error probabilities in terms of p out|in (i|j) and p i . Using (5) gives, The expression for e post (i) is valid only if p out (i) = 0 which is assumed.

Perfect and unambiguous detection
Perfect detection occurs when the detector reads i only if the ith input is present. Thus the detector is correct all the time. In this case the a posteriori probability matrix is identity which can only occur when the conditional probability matrix is identity, i.e., Under this condition, all the error probabilities in (8) are simultaneously identically zero. As might also be expected, perfect performance is independent of the input distribution {p j }. For quantum systems, this is possible if and only if the input states are orthogonal [37].
A weaker condition, referred to as unambiguous detection, occurs when the detector either provides the correct answer or one that is inconclusive with some probability (see, e.g., [12,13]. This detector requires an additional outcome corresponding to the inconclusive result. There are now m + 1 detector outcomes, D out = { i | i = 0, . . . , m }, where outcome 0 means the result is inconclusive. As before, for i = 1, . . . , m, outcome i means that input i is declared to be present. For the detector to be correct when i, i = 1, . . . , m is declared, the a posteriori probability of input i given outcome i must be 1. Equivalently, the submatrix of the conditional probability matrix corresponding to the m states is diagonal but not necessarily identity, as in perfect detection. Thus (9) now becomes, Under this condition, the a posteriori error probability is, for all i = 1, . . . , m, and the probability of an inconclusive result is, If the probability of an inconclusive result is non-zero, then this detector is a type of randomized detector.
A detector designed without this feature will be referred to as a deterministic detector. We will return to the problem of designing an unambiguous and/or randomized detector in Section 5.2.

Partial state detection
It is often the case that not all the input states are to be detected. We will show that it is not necessary to have a detector outcome for all the states. Consider the input set, Suppose only the states ρ 1 , . . . , ρ k , k < ℓ are to be detected. The ℓ − k states that are not being detected can be lumped into one state, the statistical mixture, with occurrence probability ℓ i=k+1 p i . Thus the set (13) of ℓ states can be replaced with the statistically equivalent set of k + 1 < ℓ states The detector then only requires k + 1 outcomes, not ℓ outcomes. To adhere to the previous notation, e.g., (1), define m = k + 1. An important application of the above procedure is detection of a single pure state. In this case the input state set, in the form of (15), becomes, with the pure state ψ ∈ C n , ψ * ψ = 1 occurring with probability 1 − β and the remaining states represented by the mixed state r ∈ C n×n , r > 0, Tr r = 1 occurring with probability β. We use this example to illustrate the structure of the optimal detector in some cases.

Measures of performance
The goal is to design the detector to minimize the size of an error probability. The size of the error is set by selecting a norm. Here we will consider two common norms referred to as average and worstcase. Since (7) holds -the errors are always non-negative -we can define the average error norm by e avg = m i=1 w i e(i) and the worst-case norm by e wc = max i=1,...,m w i e(i). These norms are weighted error probabilities: the weights, w i ≥ 0, are selected to emphasize specific outcomes -a larger weight emphasizes the desire to detect a particular state. Table 1 shows these norms for the specific error probabilities (8). Table 1: Norms of error probabilities.
In Table 1, the performance measures e joint avg , e cond avg , e joint wc , e cond wc are convex functions of the elements of the conditional probability matrix. In the next section we will show that the conditional probabilities are affine functions of the design parameters, specifically, the elements of the POVM characterizing the detector. Hence, these are convex functions of the design parameters. Of these measures of performance, only e joint avg , e cond avg , or slight variations thereof, have been addressed in the literature. Section 4 briefly describes the convex optimization problem associated with the performance measure e joint avg and is to some extent a partial review of known results, e.g., [17].
The performance measure e post wc , which is the focus of this paper, is a quasiconvex function of the conditional probabilities, and hence, a quasiconvex function of the design parameters, e.g., the POVM elements. As we will show in Section 5, the optimal design can be obtained by solving a convex optimization problem.
The performance measure e post avg is neither a convex nor quasiconvex function, hence, only local solutions are guaranteed to be found numerically.

Detector as a POVM
We start with the assumption that the detector can be completely described by a POVM (positive operator valued measure) with matrix elements In consequence, designing an optimal detector means selecting the matrices that form the POVM to minimize a selected performance measure from Table 1. To this end we express the error probabilities in terms of the problem data {ρ i , p i } and the design variables {O i }. First, the conditional probability of detecting i given state j is, From (5), the total probability of detector event i is then, where ρ is the statistical mixture of all the possible input states, Throughout we make the assumption that, This is a not a limiting condition; it is easily satisfied in most practical situations and if necessary can be overcome by restricting attention to the range space of ρ. The error probabilities in (8) can now be expressed as follows for i = 1, . . . , m Observe that e post (i) is meaningful only if (17), it follows that if the mixed state ρ > 0, then Tr O i ρ = 0 only when O i = 0 which is a pathological case. Using (22), the entries in Table 1 are given explicitly as shown in Table 2. The first observation to make is that the POVM matrices {O i } form a convex set (17). As already stated, since e joint (i) and e cond (i) are affine functions of O i , it follows that these errors are both convex functions of the O i matrices. Further, since all norms are convex functions, the performance measures e joint avg , e joint wc and e cond avg , e cond wc are all convex functions of the POVM matrices. Again, we note that e post wc is a quasiconvex function of {O i } and e post avg is not convex. Therefore, minimizing any of these (quaisi)convex measures over the POVM matrices can be cast as a convex optimization problem.

Optimality conditions
Lagrange Duality Theory [5, Ch.5] provides a means for establishing a lower bound on the optimal objective value, establishing conditions of optimality, and providing, in some cases, a more efficient means to numerically solve the original problem. In the sections to follow we will present the optimality conditions in a form which involves only the problem data, ρ i , p i , i = 1, . . . , m, and the design variables, the POVM matrices, O i , i = 1, . . . , m. The details are presented in the Appendix. The optimality conditions can also be used for determining if a known POVM set is optimal, what the authors in [1] call: "testing an Ansatz." Such a POVM could be obtained from some analytic means, from data, or from imagination.  Table 2: Norms of error probabilities as functions of POVM elements.

Implementation of a POVM
As shown in [34, §2.2.8], any POVM can be implemented by a unitary matrix in an expanded space together with rank-one projective measurements in the natural basis on the ancilla outputs. Some general implementations of a POVM are also presented in [32]. Realizing the resulting unitary and rank-one projections with specific physical components is, in general, a more difficult problem.

Optimal average joint performance
In this section we briefly discuss optimal detector design for e joint avg . This problem, with slight variations, has been essentially completely analyzed in [17]. The presentation here is primarily to illustrate a few of the ideas which repeatedly occur. Following this, the main focus of this paper, presented in Section 5, is on detector design for e post wc , the optimal worst-case a posteriori design. A detector which minimizes the objective e joint avg in Table 2 is obtained by solving the following optimization problem for the POVM matrices {O i }: This problem was addressed in [17] for equal weights, w i = 1, where the objective becomes 1 − i p i Tr O i ρ i . As observed in [17], problem (23), with or without equal weights, is a semidefinite program (SDP) [5, §4.6.2]. An SDP is a generalization of linear programming where the linear inequalities are replaced with matrix inequalities. Although it does not make any physical sense, if the {O i } are constrained to be diagonal, then the problem reduces to a linear programming problem.

Optimality conditions
As derived in Appendix A.1, any feasible POVM, i.e., any set of O i ∈ C n×n , i = 1, . . . , m which satisfy (17), is optimal for problem (23) if and only if, with all the problem data in the matrices,

Two state detection
As an application consider the two state detection problem using the state set (16). For equal weights w 1 = w 2 = 1, the data matrices are, Using O 1 + O 2 = I, the optimality conditions become, Since A is Hermitian it can be decomposed as, This is a feasible POVM set because U is unitary. This choice also satisfies the optimality conditions (27). Specifically, After some algebra, the optimal objective value is found to be, e opt joint avg As a further illustration, assume that r is completely randomized, that is, r = I n /n. In this case U can be chosen such that the pure state in refeqomin pure has the decomposition ψψ * = U diag(0, . . . , 0, 1) U * . It then follows that: Observe that Ω − ≤ 0 if and only if β ≤ n/(1 + n). In general, as we show below, the assumption that A has both positive and negative eigenvalues places a limit on the size of β.
Since Ω + is n − 1 × n − 1, we get Tr Ω + = β(n − 1)/n, and hence the objective value becomes For this detector the corresponding a posteriori probabilities are This result shows that as n → ∞, e joint avg → 0, p in|out (1|1) → 1, and p in|out (2|2) → β. Thus, if the state dimension is large and the statistical mixture of the residual states tends to average out to a random distribution over all states, then the probability of detecting a single pure state is very high.
Restrictions on β From (28), A has non-negative eigenvalues ( Hence, for β < β 0 , A will have both positive and negative eigenvalues. If as in the above example, r = I n /n, then ψ * r −1 ψ = n and thus β 0 = n/(1 + n).
Suppose that A > 0 (β > β 0 ). Then the only way to satisfy the optimality conditions (27) is to set The optimal objective value is now This is just the occurrence probability of the pure state ψ; essentially the detector does nothing. Observe that similar remarks can be made when A < 0.

Optimal worst-case a posteriori design
In this section the detector is designed to minimize the objective e post wc in Table 2. This requires solving the following optimization problem for the POVM matrices {O i }: As shown in [5, §4.3.2], the objective function, e post wc , is a maximum over a set of quasiconvex functions each with domain Tr O i ρ > 0, ∀i, and hence, is a quasiconvex function over the domain (38) is a quasiconvex optimization problem in the POVM matrices. Technically this means that for any positive scalar δ, the sublevel sets of POVMs are convex. To see that these sets are convex in this case, observe that for POVMs in the domain Tr O i ρ > 0, ∀i, the sublevel sets are equivalently, with The sets defined by (40) are affine in the POVM elements, and hence, are convex sets. We will refer to the matrices A i (δ) as the data matrices.
This effectively shows (see also Appendix A.2) that (38) is equivalent to, The optimization variables for (42) are now the real positive scalar δ as well as the POVM matrices {O i }.
Observe that (42) does not include the constraint set Tr O i ρ > 0, i = 1, . . . , m. Since ρ > 0, the only way this constraint can be violated is if a POVM element is zero. If this occurs then the problem is illposed and most likely that POVM element can be eliminated. Hence, from now on we do not explicitly state this constraint.
As shown in [5, §4.2.5] and described in Appendix A.2, a solution to the quasiconvex optimization problem (38) or (42) can be obtained by solving a series of convex feasibility problems together with a bisection method.

Optimality conditions
As derived in Appendix A.2, any feasible POVM (17) is optimal if and only if there exist real constants δ opt and λ i , i = 1, . . . , m such that, The index set S consists only of those indices where the optimal δ opt in (42) is achieved. Thus S is equivalently expressed by, Some special cases follow.

Equal weights: one active linear constraint
For equal weights, w i = 1, ∀i, (38) can be expressed equivalently by, Clearly γ = 1 − δ with δ from (42). Let γ opt denote the optimal objective value in (45). Suppose only one linear constraint is active, that is, for i = k, Tr O k A k (γ opt ) = 0 and for i = k, Then, as shown in Appendix A.2, the optimality conditions (43) become, with γ opt given by, where σ max (·) is the maximum singular value of the matrix argument. (Note that ρ −1/2 exists because ρ > 0 is assumed (21)). Since only one constraint is assumed active, (47) is equivalent to, If the input states are pure, that is, with ψ ∈ C n , ψ * ψ = 1, then (47) becomes,

Single pure state detection
Consider again the input set (16) where the goal is to detect ψ. With the weights set to w 1 = 1, w 2 = 0, the data matrices are, Thus, the only active constraint is Tr O 1 A 1 (γ opt ) = 0 which makes the index set S the singleton S = {1}, and hence, (46)-(47) applies. Using the Matrix Inversion Lemma to compute ψ * ρ −1 ψ with ρ = (1 − β)ψψ * + βr gives, Observe that γ opt increases as ψ * r −1 ψ increases. If ψ is close to a singular vector of r which has a very small singular value, then ψ * r −1 ψ will be large, and hence, γ opt ≈ 1. This can be construed as an approximate orthogonality condition. In the special case when r = I n /n, then ψ * r −1 ψ = n, and hence, This is exactly the result in (34), which in general is not to be expected. The (two) POVM elements O 1 and O 2 associated with the two state input set (16) can be directly calculated from the optimality conditions (46). Using the fact that O 1 +O 2 = I, the optimality conditions (46) become: Observe that because λ 2 = 0, the data matrix A 2 (δ opt ) plays no part in the optimality conditions. Using γ opt from (52) makes rank A 1 (γ opt ) = n − 1, and hence has the decomposition, for unitary [U + U 0 ] ∈ C n×n with U + ∈ C n×n−1 and U 0 ∈ C n×1 . Setting, , thus satisfying the optimality conditions (54). Observe also that O 1 is a rank 1 projector, and O 2 is a rank n − 1 projector.
If r = I n /n, then the a posteriori probabilities are exactly the same as given by (34); again, this is not the case in general.

Single state detection with pure residual state
In the previous example, as long as the residual state r > 0, then it it is not possible to make γ opt = 1. To see this, observe that A 1 (γ opt = 1) = ρ − (1 − β)ψψ * = βr > 0, and hence has only positive eigenvalues. Thus, the optimality conditions can only be satisfied with O 1 = 0, O 2 = I. (Effectively U 0 in (55) is null.) This choice of γ opt is therefore infeasible. Now consider the input set, with the pure residual state φ ∈ C n , φ * φ = 1 occurring with probability β and the state to be detected ρ 0 ∈ C n×n , ρ ≥ 0 occurring with probability 1 − β. In this case for γ opt = 1, we get, satisfies the optimality conditions. Hence, perfect deterministic detection of a single state, pure or mixed, is possible if the residual state is pure.

Noisy measurements
The optimal detector design problem can be modified to handle a "noisy" set of measurements. In general there can be more noisy measurements than noise-free measurements. Consider, for example, a photon detection device with two photon-counting detectors. If both are noise-free, meaning, perfect efficiency and no dark count probability, then, provided one photon is always present at the input of the device, there only two possible outcomes: {10, 01}. If, however, each detector is noisy, then either or both detectors can misfire or fire even with a photon always present at the input. Thus in the noisy case there are four possible outcomes: {10, 01, 11, 00}.
As before, let {O i } denote the m noise-free POVM matrices. Now let {O noisy i } denote them noisy measurements withm ≥ m. The noisy measurements can be expressed as, The {ν i } represents the noise in the measurement, specifically, the conditional probability that i is measured given the noise-free outcome j. Since m i=1 ν ij = 1, ∀j, it follows that the noisy set {O noisy i } is also a POVM. Thus,m   Table 2 remain convex or quasiconvex optimization problems over the noise-free POVM matrices {O i }.

Optimal worst-case a posteriori performance with noisy measurements
With noisy measurements, (38) becomes, Under the assumption that Tr O noisy The optimization variables for (62) are now the real positive scalar δ as well as the noise-free POVM matrices {O i }. The data matrices, A i (δ), are given by (41).

Optimality conditions
As derived in the Appendix A.3, any feasible POVM (17) is optimal if and only if there exist real constants λ i , i = 1, . . . , m such that, and the index set S given by, where δ opt is the optimal objective value from (63).

Single pure state detection
Consider again the input set (16) with weights w 1 = 1, w 2 = 0. Suppose the measurement noise matrix is, Assuming the only active constraint to be Tr O noisy 1 A 1 (δ) = 0, then the multipliers are λ 1 = 1, λ 2 = 0 and the optimality conditions become: with A 1 (γ) from (51). Assume further that ν 0 < 1/2. Then the matrix inequalities in (68) are the same as in (54), namely, Now again introduce the decomposition, where (Ω + , Ω − ) are diagonal matrices consisting, respectively, of the positive and negative eigenvalues of A 1 (γ opt noisy ). As in the previous examples, make the choice, The matrix inequalities and equalities in the optimality conditions are satisfied by this choice. The scalar (trace) condition is satisfied provided that, Tr Ω + The noise-free case, ν 0 = 0, requires that Tr Ω − = 0, which means that Ω − = 0. This is the condition for the decomposition in (55) which can only occur for γ opt noisy = γ opt from (52). When noise is present, ν 0 > 0, it is necessary that Ω − < 0, and hence, γ opt noisy < γ opt as might be expected; noise reduces the a posteriori probability of detection.

Unambiguous detection
As discussed briefly in Section 2.3, an unambiguous detector is one that with some probability either detects the correct state or else declares the result inconclusive. This requires an additional POVM element to account for the inconclusive result. Specifically, as before, let O i , i = 1, . . . , m correspond to the m input states ρ i , i = 1, . . . , m and let O 0 correspond to the inconclusive result. Thus there are m + 1 POVM elements, O i , i = 0, . . . , m. The probability of an inconclusive result is therefore, The ideal unambiguous detector is one where the a posteriori probability error is zero, or equivalently p in|out (i|i) = 1, i = 1, . . . , m which can only occur when (10) holds which here becomes, Observe that ifp(i) = 1, i = 1, . . . , m then from (12) p incl = 0, and hence, O 0 = 0, which eliminates the need for the extra (inconclusive) detector outcome and reduces to the condition for perfect detection (9). Allowing for a non-zero probability of an inconclusive result opens the possibility that a detector can be designed to satisfy (11), and thus, e post (i) = 0, i = 1, . . . , m.

Optimal a posteriori performance with an inconclusive outcome
By relaxing the requirement for zero error we can find a randomized detector by solving the following problem.
minimize e post wc = max i=1,...,m If e post wc = 0 then we have found an unambiguous detector, one that either produces the correct result or is inconclusive. Otherwise the detector is randomized, but not unambiguous. However, the extra design freedom in the inconclusive POVM matrix, O 0 , insures that the resulting e post wc will always be smaller than the value obtained for a detector without the additional inconclusive outcome.

Optimality conditions
Observe also that the only difference between problem (78) and problem (38) is the extra POVM element O 0 . As a result the optimality conditions have extra constraints to account for the additional element. Specifically, any feasible POVM is optimal if and only if there exist real constants λ i , i = 1, . . . , m such that, The index set S consists only of those indices where the optimal objective value from (78) is achieved. Thus, If the optimal is achieved at only one constraint, say i = k, then λ k = 1 λ i = 0, i = k, and the optimality conditions become:

Optimal a posteriori performance with an inconclusive outcome and measurement noise
Problem (78) can be modified to account for measurement noise.
In this case because of the noise, it is doubtful that an unambiguous detector can be found. Nonetheless, the resulting randomized detector will still outperform one without an inconclusive outcome.

Example
Consider the following two (pure) input states and corresponding occurrence probabilities: Throughout this example we place equal weights on each state, Optimizing the worst-case a posteriori probability measure, (38) This is no longer an unambiguous detector but rather a randomized detector. For 76% of the time an inconclusive result will occur. When the detector declares either state 1 or state 2, the probability of being correct is 96% which is better than the deterministic detector with probabilities of 86%. If the situation is such that there is little penalty in waiting, then a higher probability outcome is promised by the randomized detector. We now repeat all the above optimal designs for varying noise levels: The results are plotted in Figure 2 for ν 0 from 0 to 0.20 in 0.02 increments. The solid curves are the two diagonal elements of the a posteriori probability matrix for the optimal randomized detector. Associated with them is the dotted curve showing p incl , the probability of an inconclusive result. The dashed curves are the two diagonal elements of the a posteriori probability matrix for the optimal deterministic detector. As expected, the randomized detector outperforms the deterministic detector as seen by the fact that the lower solid curve is always larger than the lower dashed curve. (The optimal worst-case design maximizes the minimum error, which is equivalent to making the lower of the two curves as large as possible.) In all cases the POVMs were easily approximated by rank-one projectors, but in no case were the projectors in the natural basis. The behavior of p incl (ν 0 ) is quite interesting. The inconclusive probability and the associated POVM matrix become small at a noise level η ≈ 0.12, in effect, turning off the randomized feature. Figure 3 shows the robustness properties of the randomized and deterministic detectors. We fixed the POVMs for the two cases at their optimal settings corresponding to the noise-free case (ν 0 = 0).
The plots show what happens as the noise level increases. The probability levels are not all that different from the optimal noisy results in Figure 2, but are of course not as good.

Uncertain dynamics
The goal is to design the POVM {O i } in the presence of uncertain detector dynamics Q ∈ D dyn as illustrated in Figure 4. Figure 4: Detector with uncertain dynamics.
We will assume that D dyn consists of a finite number of unitary operators {U k } with corresponding occurrence probabilities {p dyn (k)}. Thus, The conditional probability (18) now becomes, This clearly shows that the only changes to make is to replace ρ j withρ j everywhere, specifically, in the error probabilities (22) and in the output state ρ as defined by (20). The above representation of Q is an example of a the more generic Kraus operator sum representation (OSR). Specifically, the Kraus matrices, { K k ∈ C n×n | k = 1, . . . , ℓ } with ℓ ≤ n 2 , can characterize a large class of possibilities for the Q-system as follows: Comparing this with (96) gives K k = p dyn (k)U k and K 0 = I n , which clearly is just one possibility. For example, when K 0 < I n , additional measurement operations within Q are included. The OSR also accounts for many forms of error sources as well as decoherence, e.g., [34], [31].

Detector with fixed POVM
In this section we consider designing the detector for a fixed POVM set. We will show that the detector dynamics when represented as an OSR (Operator-Sum-Representation) can also be designed by solving a quasiconvex optimization problem. Suppose we are given the POVM, {O i }, and wish to design Q for optimal detection as shown in Figure 5. The POVM would be most likely selected as rank-one projectors in the natural basis. For example, for i = 1, . . . , m, fix b i ∈ C m and O i = I ℓ ⊗ b i b * i with ℓ + m = n, the dimension of the input state. The input state might also consist of prepared ancilla states. In the natural basis b T 1 = [1 0 · · · 0], b 2 = [0 1 0 · · · 0], . . . , b T m = [0 · · · 0 1]. As noted in Section 6.1, a very general form to characterize Q is the Krause OSR. Using (98), the a posteriori performance probability is now, which is quadratic (fractional) in the Kraus matrices. It can be transformed into a quasiconvex function by expanding the Kraus matrices in a fixed basis. The procedure, described in [34, §8.4.2], is as follows: since any matrix in C n×n can be represented by n 2 complex numbers, let be a basis for matrices in C n×n . The Kraus matrices can thus be expressed as, where the n 2 coefficients {a kµ } are complex scalars. As shown in [34] the representation (98) now becomes, with X µν = ℓ k=1 a * kµ a kν , µ, ν = 1, . . . , n 2 (103) The matrix X ∈ C n 2 ×n 2 with the above coefficients must also be non-negative in order to maintain probabilities. The number of free (real) variables in X is thus n 4 − n 2 . In addition, we can write, where the matrix R i (ρ) ∈ C n 2 ×n 2 has elements given by, The problem of optimally designing the "system" part of the detector, the Q-system, is equivalent to the following optimization problem over the positive semidefinite matrix X ∈ C n 2 ×n 2 .
This problem, like (38), is also a quasiconvex optimization problem with the optimization variables being the elements of the matrix X.

Implementation of OSR
An OSR can be implemented using unitary operations (and if necessary projection measurements) and the X-matrix can be transformed to Kraus operators via the singular value decomposition [34]. Specifically, let X = V SV * with unitary V ∈ C n 2 ×n 2 and S = diag(s 1 · · · s n 2 ) with the singular values ordered so that s 1 ≥ s 2 ≥ · · · ≥ s n 2 ≥ 0. Then the coefficients in the basis representation of the Kraus matrices (101) are, Theoretically there can be fewer then n 2 Kraus operators. For example, if the Q system is unitary, then, In effect, there is one Kraus operator, U , which is unitary and of the same dimension as the input state ρ. The corresponding X matrix is a dyad, hence rank X = 1. Adding a rank constraint would thus force a simplification of the implementation. Unfortunately, a rank constraint is not convex. However, the X matrix is symmetric and positive semidefinite, hence the heuristic from [19] applies where the rank constraint is replaced by the trace constraint, From the singular value decomposition of X, Tr X = k s k . Adding the constraint (109) to (106) will force some (or many) of the s k to be small which can be eliminated (post-optimization) thereby reducing the rank. The auxiliary parameter η can be used to find a tradeoff between simpler realizations and performance.

A Optimality Conditions
Optimality conditions are derived from Lagrange Duality Theory for the following detection criteria: (i) average joint performance, (ii) worst-case a posteriori performance with noise-free measurements, and (iii) worst-case a posteriori performance with noisy measurements. Caveat emptor The material in this section is meant to be a "scaffold" to what can be found in some of the recent texts on convex optimization, e.g., see [5] and the references therein. More specifically, we refer principally to the sections in [5] where detailed information and proofs can be found for any axiomatic statements made here. The same caution applies to our references to computational methods: interested readers should refer directly to the available convex solvers which can be downloaded from the web, e.g., SDPSOL [43] or SEDUMI [42].

A.1 Optimality conditions for average joint performance
We will apply Lagrange Duality Theory [5,Ch.5] to the optimization problem (23) referred to in this context as the primal problem. The Lagrange function associated with the primal problem (23) is, with Lagrange multipliers Z i ∈ C n×n , Z i ≥ 0 for the inequality constraint O i ≥ 0, and Y ∈ R n×n , Y = Y T for the equality constraint m i=1 O i = I n . The first term in L(O, Z, Y ) is the objective function in (23) expressed in terms of the data matrices A i from (25). The Lagrange dual function is defined as,, One of the important properties of the dual function is that for any Z i ≥ 0 and any Y , we get the lower bound, where δ opt is the optimal objective value from solving (23). The Lagrange dual problem establishes the largest lower bound from, where the optimization variables are (Z, Y ). Using (111) we can eliminate the Z i variables and write the dual problem explicitly in terms of the Y variables as, A solution, Y opt , the dual optimal multiplier, also returns the maximum objective value, d opt = Tr Y opt , the dual optimal value. From (112) we get d opt ≤ δ opt . A numerical solution of the primal problem (23) always returnsδ ≥ δ opt , and likewise numerically solving the dual problem (114) will always return d ≤ d opt . Thus, the optimal solution is always contained in the known intervald ≤ d opt ≤ s opt ≤ŝ . For this primal-dual pair we also have strong duality, that is, d opt = s opt . This follows because the primal problem satisfies Slater's condition The last line uses This can be used in to eliminate Y opt in (114) and (116) yielding the constraints, These are the conditions stated in (24) as being necessary and sufficient for optimality of any feasible POVM set {O i }. The proof of this statement relies on the fact that if strong duality holds and the primal problem is convex -both true for this problem -then the above conditions (118)  A.2 Optimality conditions for worst-case a posteriori performance As shown in [5, §4.2.5], a solution to the quasiconvex optimization problem (38) can be obtained by solving a series of convex feasibility problems together with a bisection method. We start with the equivalence, Problem (38) is then equivalent to, where the variables are now the real scalar δ as well as the POVM matrices {O i ∈ C n×n }. The algorithm below requires knowing an upper and lower bound on the optimal δ opt . Without loss of generality we can normalize the weights so that 0 ≤ w i ≤ 1. Since the objective is a weighted error probability, the feasible range is 0 ≤ δ opt ≤ 1. The bisection algorithm as presented in [5, §4.2.5] now becomes:
The feasibility step is equivalent to solving the following SDP in the variables (s, O i ): It follows that if s opt > 0 then δ is feasible, and hence, δ opt < δ. If s opt < 0 then δ is infeasible, i.e., δ opt > δ. The optimal value δ opt is clearly the solution to s opt (δ opt ) = 0. The bisection algorithm together with using an interior-point method to solve the SDP (122) will return a value of δ to within any desired, but finite, accuracy of the optimal.
The key computational step is solving the feasibility problem (122). High quality code which uses an interior-point method is recommended such as those found in SDPSOL [43] or SEDUMI [42]. In many cases the optimal POVM matrices are rank deficient which may result in a large condition number in the linear equations to be solved in the Newton step. This should not be a problem for well conceived code.
To obtain the optimality conditions we will now apply Lagrange Duality Theory to the feasibility problem (122) in the Bisection-Feasibility method. Problem (122) is the primal problem. As previously noted, the primal optimal value, s opt (δ), determines if δ is feasible, Specifically, The Lagrange function associated with the primal problem (122) is, with Lagrange multipliers λ i ∈ R, λ i ≥ 0 for the inequality constraint The Lagrange dual function is then, The Lagrange dual problem establishes the largest lower bound from, maximize g(λ, Z, Y ) subject to λ i ≥ 0, Z i ≥ 0, i = 1, . . . , m where the optimization variables are (λ, Z, Y ). Using (126) we can eliminate the Z i variables and write the dual problem explicitly in terms of the λ i and Y variables as, The dual optimal solution is (λ opt , Y opt ). Strong duality also holds for this problem because Slater's condition holds [ We now put all the primal and dual equality and inequality constraints together at the optimal δ = δ opt , s opt = Tr Y opt = 0, and use (131) to eliminate Y opt . To simplify notation we drop the superscript (·) opt from all the variables (O, λ, Y, Z, δ). This gives: These can also be established directly from the KKT conditions for optimality which in this case are both necessary and sufficient [5, §5.5.3]. For the linear constraints, either the constraint is active, Combining this with (132) gives the optimality conditions in (43). Suppose the weights are all equal with w i = 1, ∀i. Then, with γ = 1 − δ. From now on we will use A i (γ) or A i (δ) as appropriate to the context. Suppose the optimal is achieved by only one constraint, that is, for i = k, Tr O k A k (γ) = 0 and for i = k, Tr O i A i (γ) < 0. Then, λ k = 1, λ i =k = 0 and the optimality conditions (132) reduce to, Since ρ > 0 by assumption (21), det A k (γ) = det ρ 1/2 γI − p k ρ −1/2 ρ k ρ −1/2 ρ 1/2 = (det ρ) n j=1 (γ − p k ω kj ) with ω kj , j = 1, . . . , n the eigenvalues of ρ −1/2 ρ k ρ −1/2 . Because ρ > 0, ρ k ≥ 0, they are all nonnegative and max j ω kj > 0. Let γ = p k max j ω kj , or equivalently, where σ max (·) is the maximum singular value of the matrix argument. With this choice det A k (γ) = 0 and hence A k (γ) = 0 has the decomposition: k0 Ω k+ = diag(ω 1 , . . . , ω n−1 ), ω 1 ≥ ω 2 ≥ · · · ≥ ω n−1 ≥ 0, ω 1 > 0 for unitary [U k+ U k0 ] with U k+ ∈ C n×n−1 and U k0 ∈ C n×1 . Setting, gives A k (γ)O k = U k+ Ω k+ U * k+ ≥ 0, A k (γ)(I − O k ) = 0, O k (I − O k ) = 0, thus satisfying the optimality conditions. Observe also that O k is a rank 1 projector, and I − O k is a rank n − 1 projector. Also, I − O k = i =k O i , and hence is the sum of the remaining m − 1 POVM elements. These are thus arbitrary except for satisfying (137) with each O i ≥ 0, i = k.

A.3 Optimality conditions for worst-case a posteriori performance with noisy measurements
To apply the Bisection- Tr with Lagrange multipliers λ i ∈ R, λ i ≥ 0 for the inequality constraint Tr O noisy i A i (δ) ≤ s, Z i ∈ C n×n , Z i ≥ 0 for the inequality constraint O i ≥ 0, and Y ∈ R n×n , Y = Y T for the equality constraint with the A i (δ, ν) given by (65). Although not shown, the optimality conditions (64) can be established by repeating, mutadis mutandis, all the steps in the previous section, i.e., formulate the dual problem, show that strong duality holds, and so on.