Guesswork with Quantum Side Information

What is the minimum number of guesses needed on average to correctly guess a realization of a random variable? The answer to this question led to the introduction of the notion of a quantity called guesswork by Massey in 1994, which can be viewed as an alternate security criterion to entropy. In this paper, we consider the guesswork in the presence of quantum side information, and show that a general sequential guessing strategy is equivalent to performing a single measurement and choosing a guessing strategy from the outcome. We use this result to deduce entropic one-shot and asymptotic bounds on the guesswork in the presence of quantum side information, and to formulate a semi-definite program (SDP) to calculate the quantity. We evaluate the guesswork for a simple example involving the BB84 states, both numerically and analytically, and prove a continuity result that certifies the security of slightly imperfect key states when the guesswork is used as the security criterion.


I. INTRODUCTION
Information theory, among other things, concerns the security of messages against attacks by malicious agents. Conventionally, it is accepted that that the more unpredictable a message is, and the higher the (Shannon) entropy of the distribution from which it is drawn, the more secure it is to brute force attacks. Therefore, when establishing a secret key or a cipher, the gold standard is to choose a key whose elements are picked uniformly at random from some alphabet.
Entropy, however, is not the only such criterion for security. Another relevant quantity, which is also maximized by messages drawn uniformly, is the guesswork. First put forth by Massey [1], the quantity is operationally described by the following guessing game. Consider the problem of guessing a realization of a random variable X, taking values in a finite alphabet X , by asking questions of the form "Is X = x?". The guesswork G(X) is defined as the minimum value of the average number of questions of this form that needs to be asked until the answer is "yes". That is, where p G (k) is the probability of the kth guess being correct.
In the real world, questions of this form arise from query § This paper was presented in part at ISIT 2020. § Copyright (c) 2017 IEEE. Personal use of this material is permitted. However, permission to use this material for any other purposes must be obtained from the IEEE by sending a request to pubs-permissions@ieee.org.
x 1 x 2 x 3 x 4 x 5 x 1 x 2 x 3 x 4 x 5 The search tree for finding the correct value of X when asking questions of the form (a) "Is X ∈X ?" or of the form (b) "Is X = x?" The former search tree, similar to that in binary search, has fewer branches and the relevant operational quantity is the entropy of the prior distribution. The specific question we ask in this tree is as follows: "Is X ∈X = {x 1 , x 2 }?" The latter tree, similar to that of linear search, characterizes the scenario of guesswork. The tree encapsulates a strategy in which one sequentially guesses x 1 , x 2 , and so on, until x 5 . access to a resource; for example, if a hacker is attempting to guess a user's password on an online portal, he or she can only ask this kind of question (as opposed to, say, "Is X ≥ x?") and is allowed a limited number of guesses before being locked out. Therefore, for someone setting up a password, the number of guesses allowed by the portal provides the operational security criterion against which his or her password must compare.
In contrast, the entropy of a distribution is approximately the minimum value of the average number of guesses required to obtain the correct guess when one is allowed to ask questions of the form, "Is X ∈ X ?", where each X is some subset of the alphabet X [2, Theorem 5.4.1]. Qualitatively speaking, entropy can be considered to be the query complexity of a binary search-type algorithm, whereas guesswork corresponds to the query complexity of a linear search-type algorithm [3]. Figure 1 illustrates this difference. It is well known that binary search has a smaller complexity than linear search, which leads to the simple claim that the entropy of a distribution is always less than the guesswork. Massey [1] proved the following stronger lower bound on the guesswork in terms of the Shannon entropy of the random variable X: provided that H(X) ≥ 2 bits.

arXiv:2001.03598v3 [quant-ph] 24 Dec 2021
Massey [1] also showed that the optimal algorithm to minimize the guesswork, and even the positive moments of the number of guesses, consists of the intuitive strategy of simply guessing elements in decreasing order of their probability of occurrence. Guesswork can also be considered in the presence of classical side information given in the form of a random variable Y that is correlated with X. In this case, the guesswork is the minimal number of questions of the form "Is X = x?" that is required on average to obtain the correct answer, given the value of Y . The average is taken over the number of guesses, with each guess number weighted by its probability of being correct. That is, where in this case, p G (k) is the probability of the kth guess being correct, given that Y = y. The optimal guessing strategy is simply to guess in decreasing order of conditional probability p X|Y (x|y). Arikan [4] obtained upper and lower bounds on the guesswork and its positive moments, in this scenario as well as in the case without side information.
Further work on guesswork in the classical setting has been done in [5]- [12].
In this paper, we consider a natural generalization of the above guessing problem to the case in which the classical side information is replaced by quantum side information. This generalization was first considered in [13]. In this case, the guesser (say, Bob) holds a quantum system B, instead of a classical random variable (or equivalently, a classical system) Y . Here, the joint state of X and B is given by a classicalquantum (c-q) state, which we denote as ρ XB (see Section II for details). Suppose that Alice possesses the classical system X containing the value of the letter x, which is to be guessed by Bob. We define guesswork in the presence of quantum side information to be the minimum number of guesses needed, on average, for Bob to correctly guess Alice's choice, by performing a general sequential protocol, as follows. Bob acts on his system B with a quantum instrument, yielding a classical outcomex which he guesses, as well as a postmeasurement state on system B. If his guess is incorrect, he performs another instrument on his system B (possibly adapted based on his previous guess), and repeats the protocol until he either guesses correctly or runs out of guesses (which might be the case if he is allowed a limited number of guesses K < |X |).
While the case of classical side information admits a very simple optimal strategy (which amounts to simply sorting the conditional probabilities p X|Y (·|y) in non-increasing order and guessing accordingly), the quantum case requires measurement on the quantum system B, which potentially disturbs the state of B, a priori complicating the analysis of the sequence of guesses in the optimal strategy. We show in Section III-B, however, that a general sequential strategy is in fact equivalent to performing a single generalized measurement yielding a classical random variable Y of outcomes and then doing the optimal strategy using this Y as the classical side information. The earlier work [13] instead defined guesswork with quantum side information as the latter quantity, i.e., a measured version of the guesswork in the presence of classical side information. We prove here that these definitions are equivalent, and thus there is ultimately no difference between them, but we consider the definition in terms of a sequential protocol to be a more natural one. Moreover, the above-mentioned equivalence is proved via an explicit construction, allowing such a guessing strategy to be implemented sequentially. The single-measurement protocol could in general involve making a measurement with exponentially (in |X |) many outcomes. Hence it may be more efficient to implement it instead as a sequence of (linearly-many) measurements with linearly-many outcomes, as allowed by the above construction.
Moreover, we consider a slight generalization of the guesswork in which Bob may make only K ≤ |X | guesses in total, and in which the "cost" of needing to make k guesses is given by a vector c = (c 1 , c 2 , . . . , c K ), which could be different from (1, 2, . . . , K), the latter of which corresponds to the expected value. These generalizations can be better models for certain situations; in the password-guessing example, e.g., Bob may be locked out after K guesses and hence is limited to a small number of guesses, or perhaps one has to wait after each guess before making another, and the time that one waits increases with the number of incorrect guesses. We show that this generalized situation (including the guesswork as a special case) admits a semi-definite programming (SDP) representation in which the number of variables scales as |X | K , and hence smaller values of K yield smaller problems and better scaling with |X |. See Section V for more on the computational aspects of the guesswork.
One can consider a related task, in which one wishes to maximize what is known as the "guessing probability" p guess (X|B) [14]. In this case, the guesser is given only one attempt to guess the value of X (and hence is free to perform any arbitrary measurement on his system B). The guessing probability is related to the so-called conditional min-entropy H min (X|B) of the c-q state ρ XB . In some sense, we can consider the guesswork to be an extension of the guessing probability. However, the nature of the optimization being done is different: instead of maximizing the probability of success in one attempt, we minimize the total number of guesses required. Therefore, the operations that a guesser performs to minimize the guesswork may be very different from those needed to maximize the guessing probability. Some of the connections between these two tasks have been investigated in [13]. a) Overview: In Section II, we formally describe the task of guesswork with quantum side information. In Section III, we define classical and quantum guessing strategies in a unified framework, and Theorem 1 states that three classes of quantum strategies are equivalent. In Section IV, we establish one-shot and asymptotic entropic bounds on the guesswork, using analogous bounds developed by Arikan for the case of classical side information [4]. In Section V, we revisit the idea that the guesswork may be formulated as a semi-definite optimization problem (SDP) (originally discussed in [13]), and we use such a representation to prove that the guesswork in a concave function (see Section VII-A) and a Lipschitz continuous function (see Section VII-B). We discuss the dual formulation of the SDP in Section V-A, a resulting algorithm to efficiently compute upper bounds in Section V-B, and we present a mixed-integer SDP representation in Section V-C. Section VIII shows two simple examples of the guesswork involving the BB84 states and the Y states, and Section IX provides a robustness result for using guesswork as a security criterion.

II. STATEMENT OF THE PROBLEM
Alice chooses a letter x ∈ X with some probability p X (x), where X is a finite alphabet. This naturally defines a random variable X ∼ p X (x). She then sends a quantum system B to Bob, prepared in the state ρ x B , which depends on her choice x. Bob knows the set of states {ρ x B : x ∈ X }, and the probability distribution {p X (x) : x ∈ X }, but he does not know which particular state is sent to him by Alice. Bob's task is to guess x correctly with as few guesses as possible. From Bob's perspective, he therefore has access to the B-part of the c-q state In the purely classical case, this task reduces to the following scenario: Alice holds the random variable X ∼ p X (x), and Bob holds a correlated random variable Y and knows the joint distribution of (X, Y ). In this case ρ XB reduces to the state In this case, if Bob's random variable Y has value y, then an optimal guessing strategy is to sort the conditional distribution p X|Y (·|y) in non-increasing order so that and simply guess first x 1 , then x 2 , etc., until he gets it correct [4]. We note that in the absence of side information, Bob simply guesses in non-increasing order of p X (·).
In the case in which Bob's system B is quantum, he is allowed to perform any local operations he wishes on B, and then make a first guess x 1 . He is told by Alice whether or not his guess is correct; then he can perform local operations on B, and make another guess, and so forth. We are interested in determining the minimal number of guesses needed on average for a given ensemble {p X (x), ρ x B } x∈X and the associated optimal strategy.
More generally, we allow Bob to make K guesses, with possibly K < |X |. Formally, we assume that Bob always makes all K guesses; any guess after the correct guess simply does not factor into the calculation of the minimal number of guesses (see Section III for a more detailed definition of the minimal number of guesses). Thus, Bob makes a sequence of guesses, g 1 , . . . , g K ∈ X K = with some probability. We could consider the scenario in which Bob makes a guess x 1 , then learns whether or not the guess was correct, and uses that information to make his second guess x 2 , and so forth. However, if Bob learns that his jth guess x j is correct, then it does not matter what he guesses subsequently (it has no bearing on the minimal number of guesses). If the guess is incorrect, then his subsequent guesses do matter, and he should make his next guess accordingly. Hence, in such a protocol, the feedback about whether or not the jth guess is correct does not help, and Bob might as well assume that each guess is incorrect.

III. GUESSING STRATEGIES
When Alice chooses x * ∈ X , a guessing strategy for Bob outputs a sequence of guesses g = (g 1 , . . . , g K ) ∈ X K with some probability p G|X ( g|x * ). Hence, formally, a guessing strategy for X with K guesses is a random variable G on X K that is correlated with X, such that the joint random variable (X, G) has marginal X ∼ p X . Note that the definition of a guessing strategy has no reference to the side information (if any) to which Bob has access; instead, the side information dictates the set of guessing strategies to which Bob has access. This allows various types of side information to be analyzed within a uniform framework; in particular, the set of strategies available when Bob has access to some classical side information Y is described in Section III-A, while the case of quantum side information is described in Section III-B.
We are interested in the minimal number of guesses required to guess x * correctly with a fixed sequence of guesses g. This is defined as follows: where the outcome ∞ occurs when none of the K guesses are correct. We can view N as a random variable taking values in {1, 2, . . . , K, ∞}. Given a guessing strategy G, the quantity of interest is N ( G, X), the corresponding random variable. We define S K (X) := N ( G, X) : X G ∼ p X G (8) to be the set of all possible random variables N associated to all guessing strategies G with K guesses. We say two guessing strategies G and G for X with K guesses are equivalent if N ( G , X) = N ( G, X). Note that if G and G are two strategies with K guesses for X that differ only in guesses made after guessing the correct answer, then they are equivalent. This formalizes the notion introduced at the end of the previous section: since guesses made after the correct answer do not change the value of N ( g, x * ), feedback of whether or not g j = x * can only lead to equivalent strategies.

A. Classical strategies
Consider a pair of random variables (X, Y ) where X has a finite alphabet X and Y has a countable alphabet Y. Alice chooses x * ∈ X (with probability p X (x * )) and Bob is given y ∈ Y (with probability p Y |X (y|x * )). Bob's task is to guess x * . Since Bob's sequence of guesses (g 1 , . . . , g K ) can only depend on x * via y, a classical guessing strategy G is any random variable G such that the ordered triple (X, Y, G) of random variables forms a Markov chain, which we denote as X − Y − G. Hence, given a joint probability distribution p XY , we define the set of random variables N associated to classical guessing strategies as follows: B. Equivalence of quantum strategies Let us consider three classes of quantum strategies: 1) Measured strategy: Bob performs an arbitrary POVM {E y } y∈Y on the B system. Let Y be the random variable with outcomes in a finite alphabet Y corresponding to his measurement outcomes, i.e.
Bob then employs a classical guessing strategy on (X, Y ). The set of random variables corresponding to the possible number of guesses under such a strategy is given by We then observe that 2) Ordered strategy: Bob performs a measurement with outcomes in X K , which are identified with guessing orders; i.e., if the outcome is (x 1 , . . . , x K ) ∈ X K , Bob first guesses x 1 , then x 2 , and so forth. In this case, Bob performs a POVM {E g } g∈X K and the guessing strategy G is distributed according to As above, we define It is evident that because any such ordered strategy is a special type of measured strategy (with Y = G). However, any measured strategy can in fact be simulated by an ordered strategy. Suppose we have a measured strategy with alphabet Y, POVM {E y } y∈Y , and G satisfying X−Y − G. Then where we have used the Markov property for the first equality and (10) for the second equality.
using again that {E y } y∈Y is a POVM. Then substituting the definition ofẼ g into (16) yields and hence (13) is satisfied with E =Ẽ. Therefore, 3) Sequential quantum strategy: Suppose that Alice chooses x (which occurs with probability p X (x)), and hence Bob has the state ρ x B . To make his first guess, Bob chooses a set of generalized measurement operators {M (1) x } x∈X and reports the measurement outcome as his guess. He gets outcome x 1 with probability and his post-measurement state is Note: in general, Bob could perform a unitary operation U 1 on his state before measuring it. However, this would simply correspond to measuring with {M (1) x U 1 } x∈X instead. Hence, it suffices to simply consider a generalized measurement {M (1) x } x∈X . Then, after learning the outcome x 1 , Bob chooses a new set of generalized measurement operators {M (2|x1) x } x∈X . Note that this set of measurement operators can depend on x 1 . Without loss of generality, we can keep the same outcome set X , since Bob could set, e.g. M (2|x1) x1 = 0 to avoid guessing the same number twice. Bob measures his state and gets the outcome x 2 with probability Multiplying by p G1|X (x 1 |x) we see the joint distribution is given by To make his jth guess, we allow Bob to choose a new set of generalized measurement operators {M (j|x1,...,xj−1) x } x∈X , which may depend on the previous j − 1 outcomes. Repeating the previous logic, in the end we find that Under such a strategy, the possible random variables giving the number of guesses is given by Theorem 1: Let ρ XB be a c-q state as defined in (4) and K a natural number with K ≤ |X |. Then We see that all three sets of random variables of the number of guesses obtained from various classes of strategies all coincide. Hence, we call the single class that of quantum strategies, denoted as S Quantum Proof. The second equality was already stated in (21) and proven before that, and so it remains to prove the first equality. Consider a sequential strategy, with the notation of point 3 above. Define as can be seen by first summing (29) over x K , using } x∈X is a set of generalized measurement operators, and then similarly summing over x K−1 , x K−2 ,. . . , and finally Hence, Bob's strategy is equivalent to simply performing the single POVM {E x } x∈X K once, obtaining an outcome x = (x 1 , . . . , x K ), and then making x 1 his first guess, x 2 his second guess, and so forth. That is, any such strategy can be recast as an ordered strategy. On the other hand, any such ordered strategy can be reformulated as an adaptive strategy, by the following recursive approach. Suppose that we are given {E y } y∈X K . For each where we have chosen the positive semi-definite square root. We have that and so M forms a set of generalized measurement operators with outcomes in X . Next, for each x 1 ∈ X , corresponding to obtaining outcome x 1 on the first measurement, we define measurement operators {M Likewise, we define Repeating this process, we define to obtain a generalized measurement operator for step (to use when having obtained outcomes x 1 , . . . , x −1 during the previous steps). At the last step, = K, there is no sum, namely Lastly, we check that by design, (29) holds. Thus, we can work backwards from that equation and see that our newly created adaptive strategy yields the same outcomes with the same probabilities as the initial ordered strategy.

C. Success metrics
Given a random variable X and a maximal number K of allowed guesses, how do we measure the success of a guessing strategy G? We will focus on expectations of N ( G, X). In particular, we consider the expected number of guesses required to guess correctly: is the probability that, for guessing strategy G, the kth guess is correct. We also consider a general cost Then we define the modified expectation Imposing a maximal number K < |X | of allowed guesses is equivalent to choosing c K+1 = · · · = c |X | = ∞, using the convention ∞ · 0 = 0. Accordingly, we implicitly associate K with c in all the following via the rule that K = |X | if and only if c |X | < ∞, and otherwise K = min{i : c i = ∞}. The case K = |X | therefore corresponds to |X | guesses being allowed, each with finite cost, and the case K < |X | corresponds to a limited number of allowed guesses, with a corresponding infinite cost if the correct answer is not obtained in K guesses. Given a c-q state ρ XB and a cost vector c as in (49), we define the generalized guesswork with quantum side information as Likewise, given a joint distribution p XY , let From the equality of Theorem 1 it follows that where the infimum is over all finite alphabets Y and POVMs In the standard case in which c = (1, 2, . . . , |X |), we define the guesswork with quantum side information as and likewise define G(X|Y ) p = G c (X|Y ) p in the case of classical side information Y . Remark 2: In Ref. [13], guesswork with quantum side information was defined by the right-hand side of (53) (with c = (1, 2, . . . , |X |)). Moreover, Proposition 1 of that work shows that the infimum in (53) in that case may be restricted to POVMs whose elements are all rank one.

IV. ENTROPIC BOUNDS
In this section, we use the results of Section III to obtain one-shot and asymptotic entropic bounds on G(X|B) in terms of measured versions of bounds known in the classical case.

A. One-shot bounds
In the case in which K = |X |, Arikan [4] showed that where the supremum is over probability distributions q Y on Y, and D α is the α-Rényi relative entropy, The second equality of (56) follows from [15,Theorem 4]. Arikan's bound (55) applies to each G c (p XY , K) in (53), and hence by minimizing over the POVMs {E y } y∈Y , we obtain where is the joint probability distribution obtained by measuring the B part of ρ XB via {E y } y∈Y .
Remark 3: We may expand this quantity as where p XY is induced by the measurement of ρ XB . This quantity seems to be different from the conditional entropy induced by the measured Rényi divergence, namely where the supremum is over states on the B system, and for any pair of states (ρ, σ), is the measured α-Rényi divergence. Indeed, the latter quantity may be expanded to obtain From the min-max inequality, and the fact that collective measurements on XB can simulate measurements on B alone, we have

B. Asymptotic analysis
We can consider the asymptotic setting in which Bob receives a sequence of product states ρ x B := ρ x1 B ⊗ · · · ⊗ ρ xn B , with probability p X (x 1 ) · · · p X (x n ) and aims to guess the full sequence x = (x 1 , . . . , x n ). In this case, the problem is characterized by the c-q state ρ ⊗n XB . The 1-shot bounds (59) give us where H ↑,M 1 2 (X n |B n ) ρ ⊗n can involve collective measurements on the system B n . Taking n → ∞, we obtain assuming that the limit on the right-hand side exists.
Note that we can bound where the first inequality follows from the fact that product measurements are a special case of collective measurements, and the first equality follows from the additivity of the classical (X|B) ρ . Moreover, by the data-processing inequality [16], where the conditional Rényi entropy H ↑ α (C|D) σ of a bipartite state σ CD is defined as with the optimization with respect to states ω D and the sandwiched Rényi relative entropy defined as [17], [18]: The equality in (74) follows from the additivity of H ↑ 1 2 under tensor products (see, e.g., [19,Corollary 5.2]). Hence, we obtain where p is the underlying classical distribution of (5). Hence, these bounds recover Proposition 5 of [4].

V. SEMI-DEFINITE OPTIMIZATION REPRESENTATIONS AND THEIR CONSEQUENCES
The task of calculating G c (X|B) ρ as defined in (50) can be written as a semi-definite optimization problem, as was found in [13]. In this section, we present a different derivation of that fact yielding in (87) a representation dual to the one found in [13]. In Section VII-A we use this representation to prove that the guesswork G(X|B) ρ is a concave function of the c-q state ρ XB . In Section VII-B we likewise use this representation to obtain a Lipschitz continuity bound on the guesswork. Then in Section V-A we compute the dual SDP, recovering the one obtained in [13]. In Section V-B we use this dual representation to develop a simple algorithm to obtain upper bounds on the quantity. Lastly, in Section V-C, we formulate a mixed-integer SDP representation of the problem, whose number of variables and constraints scales polynomially with all the relevant quantities (at the cost of adding binary constraints). We also provide implementations of these SDP representations [20], using the Julia programming language [21] and the optimization library Convex.jl [22].
Consider an ordered strategy G with a set of POVMs and hence where we define R g := x∈X p X (x)c N ( g,x) ρ x B for g ∈ X K . Thus, The expression in (84) clarifies that R g has an interpretation as a cost operator corresponding to the guessing outcome g.
is linear in each positive semi-definite (matrix) variable E g , G c (X|B) ρ admits an SDP representation, given in (84). This program has |X | K variables (each d B × d B complex positive semi-definite matrices), subject to one constraint. Note, however, since the cost vector c is increasing, any guess h ∈ X K with repeated elements is a suboptimal guessing order. That is, if {E g } g∈X K is a POVM with E h = 0, and h ∈ X K only differs from h by replacing repeated elements such that h has no repeated elements, then the POVM defined bỹ . Hence, we may restrict to the outcome space Note |X K = | = |X |! (|X |−K)! , and in the case in which K = |X |, the set X K is just the set of permutations of X . Hence, (84) can be re-written as the following smaller problem (with |X |! Note that in the case c ∞ = ∞ and K < |X |, there exists a finite solution if and only if there exists a POVM {E g } g∈X K = such that for all x ∈ X and g ∈ X K = with x ∈ g, we have tr[E g ρ x B ] = 0. Whether or not this holds depends on the particular state ρ XB . However, when c ∞ < ∞ or K = |X |, for any state ρ XB , the problem (87) has a finite solution. Moreover, for any POVM {E g } g∈X K = , the objective is finite. In the following, we restrict to those two cases.
Remark 4: This optimization problem has the same form as that of discriminating quantum states in an ensemble, as described in, e.g., [23, Section 3.2.1]. Note, however, that (1) the R g are positive semi-definite but not normalized, and (2) the case of having two copies of the unknown state in the guessing framework does not correspond to R ⊗2 g . Nevertheless, slight modifications to [23,Theorem 3.9] show that a POVM {E g } g∈X K = is optimal for (87) if and only if satisfies Y ≤ R g for all g ∈ X K = . Remark 5: The set of POVMs is convex and since the objective function is linear, any minimizer for (87) may be decomposed into extremal POVMs which are also minimizers. By [24, Corollary 2.2], any extremal POVM on a Hilbert space of size d B has at most d 2 B non-zero elements. Hence, there exist minimizers of (87) with at most d 2 B non-zero elements (even though |X K = | could be far larger than d 2 B ). Let S ⊆ X K = be a set of d 2 B points such that there exists {Ẽ g } g∈S with E g ≥ 0, g∈SẼ g = 1 B , and Then (87) holds with X K = replaced by S, namely Note the "≤" direction of the equality (90) is trivial, since given a minimizer {E g } g∈S for (90), simply extending it by choosing E g = 0 for g ∈ S gives a feasible point for the optimization problem on the right-hand side of (87). The "≥" direction follows from the existence of the {Ẽ g } g∈S described above. We note here that it is nontrivial to identify the set S. In general, identifying the set S is as difficult as solving the original problem in (87). However, applying a heuristic method inspired by choosing a smaller set of constraints can lead to useful upper bounds on the guesswork, which we describe in Section V-B.

A. The dual problem
Next, we compute the dual problem to (87), in the case K = |X | or c ∞ < ∞. Consider the Lagrangian where we have introduced the Hilbert-Schmidt product A, B = tr[A † B], and where λ g ≥ 0 is the dual variable to the inequality constraint E g ≥ 0, and ν = ν † is the dual variable to the equality constraint g∈X K = E g = 1 B . As shown in, e.g., [25], the primal problem (87) can be expressed as min while the dual problem is given by If R g − λ g + ν = 0 for any g ∈ X K = , then the inner minimization in (95) yields −∞. Hence, The constraint λ g ≥ 0 and R g − λ g + ν = 0 imply the semi-definite inequality −ν ≤ R g . Writing Y = −ν and maximizing over λ g ≥ 0, (95) becomes Since (87) is strictly feasible (e.g., E g = 1 B 1 |X K = | is a strictly feasible point) by Slater's condition, strong duality holds. Hence, (97) obtains the same optimal value as (87). The formulation of the problem as given in (97) was previously found in the work [13,Proposition 3]. In contrast to the primal SDP (90), the dual problem has a single variable Y subject to |X K = | constraints.

B. A simple algorithm to compute upper bounds
The dual form of the SDP can be used to generate upper bounds on G c (X|B) ρ simply by removing constraints. This provides an algorithm to find an upper bound on the objective function: Decide on some number of constraints κ to impose in total. Then, 1) Initialize an empty list L = {} corresponding to constraints to impose. 2) Set Y to be the identity matrix, as a first guess at the optimal dual variable. 3) If Y satisfies Y ≤ R g for all g ∈ X K = , then Y is the maximizer of the dual problem (97), and the optimization is solved. Otherwise, find g ∈ X K = such that Y ≤ R g , and add g to the list L.
and set Y to be its maximizer. 5) Repeat steps 2 and 3 until the list L has length κ. 6) Solve the problem one last time, and return the output. In order to find a constraint that Y violates, a heuristic technique such as simulated annealing can be used. Moreover, in the case that there are too many constraints to fit into memory or check exhaustively, using an iterative technique (such as simulated annealing) is essential. If this algorithm was continued (without imposing a limit on the total number of constraints κ to impose), it would eventually yield the true value G c (ρ XB , K). When a total number of constraints is limited, it provides an upper bound (since it is a relaxation of (97)). However, even with a limit κ on the total number of constraints, this algorithm can in theory yield the true value G c (X|B) ρ . Note that the dual problem to (90) is where S ⊆ X K = has |S| = d 2 B and is described in the remark above. Hence, if L in (98) equals S, then the algorithm finds the true value G c (X|B) ρ , not just an upper bound. Thus, κ = d 2 B suffices if the constraints g can be chosen precisely to obtain L = S. In general, finding S is as difficult as solving the original problem. Nonetheless, this motivates why choosing a relatively small value of κ (such as d 2 B ) can still yield good upper bounds.

C. A mixed-integer reformulation
The problem of computing G c (X|B) ρ can be formulated another way as a mixed-integer SDP, i.e., an SDP that has additional integer or binary constraints. Consider a POVM {F j } M j=1 with M outcomes. When outcome j is obtained, Bob guesses in some order g (j) ∈ X K = . Then consider the problem minimize x∈X ,j=1,...,M subject to F j ≥ 0 j = 1, . . . , M, We note that in the above, the variables to be optimized over are both the POVM {F j } M j=1 and the guessing orders { g (j) } j corresponding to each POVM outcome. This optimization is not an SDP, since the dependence on the optimization variables { g (j) } M j=1 and {F j } is not linear, and g (j) ∈ X K = is a discrete constraint. Consider, however, the case that K = |X |. With this assumption, we will be able to remove the nonlinearity although not the discrete variables. This yields a mixedinteger SDP: an optimization problem such that if all integer constraints were removed, the result would be an SDP. We proceed as follows.
Under the condition K = |X |, we may restrict to considering guessing orders that are permutations without loss of generality; other guessing orders have repeated guesses, which can only increase the value of the objective function. In this case, the outcome ∞ never occurs, and for each g ∈ S |X | , the quantity (c N ( g,x) ) x∈X satisfies where g −1 is the inverse permutation to g, and c = (c k ) K k=1 is the cost vector (without ∞). Here, S n is the set of permutations on {1, . . . , n}. Let P (j) be an |X | × |X | matrix representation of the permutation g (j)−1 . Then (P (j) c) x = y∈X P (j) xy c y = c N ( g,x) . Hence, the optimization (100) can be reformulated as Note that all the constraints are semi-definite or linear, except that each element P (j) xy is a binary variable: P (j) xy ∈ {0, 1}, which is a particularly simple type of discrete constraint. The non-linearity in the objective function, however, persists. To remove this, we take advantage of the fact that the P (j) xy are binary. In particular, [26,Equations (22)- (24)] provide a clever trick to turn objective functions with terms of the form zx where z is a binary variable and x a continuous variable into objective functions of a continuous variable y subject to four affine constraints (in terms of x and z), as long as x is bounded by known constants. We reproduce this argument in the following.
We first write the objective function entirely in terms of scalar quantities: . Then x L := −d B /2 and x U := d B /2 constitute lower and upper bounds to x, respectively. Hence, the following four inequalities hold trivially: Now, let y = xz. Then we have On the other hand, let us remove the constraint y = xz, and consider y as another variable. Then if z = 0, the first equation of (105) implies that y ≥ 0, while the third implies y ≤ 0, so y = 0. On the other hand, if z = 1, then the second equation of (105) implies that y ≥ x while the fourth implies that y ≤ x. Hence, either way, y = xz. Thus, (105) is equivalent to y = xz.
With this transformation, (102) can be reformulated as the following.
(106) where the last four constraints hold for ∀ x, y ∈ X , , k ∈ [d B ], and j ∈ [M ]. This is a mixed-integer SDP, with a number of constraints and variables that is polynomial in , then as follows from the remark below (87), the mixed-integer SDP (106) obtains the same optimal value as (87), namely G c (ρ XB , |X |), using that K = |X |. Note, however, that mixed-integer SDPs are not in general efficiently solvable; they encompass mixed integer linear programs, which are NP-hard. However, in practice they can sometimes be quickly solved. Since the original SDP formulation (87) involves an exponential (in |X |) number of variables (or an exponential number of constraints in its dual formulation (97)), Eq. (106) may provide a more practical approach in some cases because it instead has a polynomial (in |X |) number of variables. Mixed-integer SDPs can be solved in various ways; in the code accompanying this paper [20], the problem (106) is solved using the library Pajarito.jl [27], which proceeds by solving an alternating sequence of mixedinteger linear problems and SDPs.
VI. THE ELLIPSOID ALGORITHM The ellipsoid algorithm (see, e.g., [28]) provides a theoretical proof that under a strict feasibility assumption, semidefinite programs can be solved in time that scales as a polynomial in: the number of scalar variables and constraints, the logarithm of a 2-norm bound on the feasible points, ln(1/ε) where ε is the solution tolerance, and the maximum bit length of the scalar entries of the objective and constraints (see e.g. [29,Theorem 4]).
In fact, the ellipsoid algorithm applies quite generally to the optimization of a linear objective function over a convex feasible region (which could be described by a domain and constraint functions). The ellipsoid algorithm only requires a separation oracle for the feasible region, a subroutine which either asserts that a given point lies within the feasible region, or provides a separating hyperplane between the given point and the feasible region. When the separation oracle can be evaluated in polynomial time, the overall ellipsoid algorithm runs in polynomial time as well (see [28,Corollary 4.2.7]).
In the case of a single positive semi-definite constraint, e.g. Y ≥ 0, a simple separation oracle is given by computing the eigendecomposition of Y and checking if all of its eigenvalues are non-negative. If so, it returns that Y is indeed feasible, and otherwise returns the matrix C : . . , λ d are the eigenvalues, and f (x) = 1 if x < 0 and f (x) = 0 otherwise. This matrix has the properties that C ≥ 0, C ∞ = 1, and tr In the case of the dual problem (97) with K = |X |, we have |X |! positive semi-definite constraints. Thus, we cannot check all of them together in polynomial time.
The feasibility problem Y ≤ R π for each π ∈ S |X | can be written as the following mixed-integer non-linear problem, where η ≥ 0 if and only if Y ≤ R π for all π ∈ S |X | , using that a matrix M satisfies M ≥ 0 if and only if ψ, M ψ ≥ 0 for all ψ ∈ C d B . Since the convex hull of the permutation matrices is given by the doubly stochastic matrices, the discrete constraints can be relaxed, yielding the following reformulation If η ≥ 0, then Y is feasible. Otherwise, the optimal value D * can be decomposed as a convex combination of permutations, D * = i α i P i , and we must have x (P i c) x p X (x)ρ x B ≥ Y for some P i , using that the objective is an affine function of D. The problem (107) can be solved by global non-linear optimization solvers such as EAGO.jl [30] or SCIP [31], but not in general in polynomial time.
At each iteration of the ellipsoid algorithm, one must evaluate the separation oracle for some Hermitian matrix Y . In order to avoid solving (107), one may attempt to prove the feasibility or infeasibility of a point Y by other means. For example, one may search over permutations π heuristically, in order to find R π such that Y ≤ R π . If such a permutation can be identified, then Y is not feasible, and the problem (107) does not need to be solved. Likewise, if one can show that for some k ∈ (1, . . . , |X |), ∀(x 1 , . . . , x k ) ∈ X k = (108) then Y must be feasible, and again (107) does not need to be solved. The number of comparisons required scales as |X | k ; for small choices of k, this provides an efficient check for feasibility (which may, however, be inconclusive).

A. Numerical comparisons
We compare numerical implementations of several of the above algorithms on a set of 12 test problems. The code for these experiments can be found at [20]. Each problem has p ≡ u, the uniform distribution u := (1/|X |, . . . , 1/|X |), for simplicity. The states are chosen as 1) Two random qubit density matrices 2) Two random qutrit density matrices 3) Three pure qubits chosen equidistant within one plane of the Bloch sphere (the qubit trine states), i.e. cos j 2π 3 |0 + sin j 2π 3 |1 , j = 1, 2, 3 4) Three random qubit density matrices 5) Three random qutrit density matrices 6) The four BB84 states, |0 , |1 , and |± = 1 √ 2 (|0 ± |1 ) as well as the "tensor-2" case of for each of the six sets S listed above, corresponding to the guesswork problem with quantum side information associated to ρ ⊗2 XB , where ρ XB is the state associated to the original guesswork problem with quantum side information. The random states were chosen uniformly at random (i.e. according to the Haar measure).
The exponentially-large SDP formulation (and its dual), the mixed-integer SDP algorithm, and the active set method were compared, with several choices of parameters and underlying solvers. The mixed-integer SDP formulation was evaluated with M = d B (yielding an upper bound), M = d 2 B (yielding the optimal value), with the Pajarito mixed-integer SDP solver [27], using Convex.jl (version 0.12.7) [22] to formulate the problem. Pajarito proceeds by solving mixed-integer linear problems (MILP) and SDPs as subproblems, and thus uses both a MILP solver and an SDP solver as subcomponents. Pajarito provides two algorithms: an iterative algorithm, which alternates between solving MILP and SDP subproblems, and solving a single branch-and-cut problem in which SDP subproblems are solved via so-called lazy callbacks to add cuts to the mixed-integer problem. The latter is called "mixed-solver drives" (MSD) in the Pajarito documentation. We tested three configurations of Pajarito (version 0.7.0): Here, 'c' stands for commercial, and 'o' for open-source. In the configuration (c1), Gurobi was set to have a relative optimality gap tolerance of 10 −5 and in (c2), a relative optimality gap tolerance of 0. In both configurations, Gurobi was given an absolute linear-constraint-wise feasibility tolerance of 10 −8 , and an integrality tolerance of 10 −9 . These choices of parameters match those made in [27]. Cbc was given an integrality tolerance of 10 −8 , and SCS's (normalized) primal, dual residual and relative gap were set to 10 −6 for each problem. The default parameters were used otherwise. Note the MSD option was not used with Cbc, since the solver does not support lazy callbacks.
For the (exponentially large) SDP primal and dual formulations, the problems were solved with both MOSEK and SCS, and likewise with the active-set upper bound.
The active set method uses simulated annealing to iteratively add violated constraints to the problem to find an upper bound, as described in Section V-B, and uses a maximumtime parameter t max to stop iterating when the estimated time of finding another constraint to add would cause the running time to exceed the maximum-time 1 . This provides a way to compare the improvement (or lack thereof) of running the algorithm for more iterations. The algorithm also terminates when a violated constraint cannot be found after 50 runs of simulated annealing (started each time with different random initial conditions). Here, the problems were solved with three choices of t max , 20 s, 60 s, and 240 s.
The exact answer was not known analytically for most of these problems, and so the average relative error was calculated by comparing to the mean of the solutions (excluding the active-set method and the MISDP with M = d B , which only give an upper bound in general). For the cases of the BB84 states and the Y-states, where the solution is known exactly (see Section VIII), the solutions obtained here match the analytic value to a relative tolerance of at least 10 −7 .
The problems were run sequentially on a four-core desktop computer (Intel i7-6700K 4.00GHz CPU, with 16 GB of RAM, on Ubuntu-20.04 via Windows Subsystem for Linux, version 2), via the programming language Julia [21] (version 1.5.1), with a 5 minute time limit. The results are summarized in Table I, and presented in more detail in Table II and  Table III. 1 The maximum time can still be exceeded, since at least one iteration must be performed and the estimate can be wrong.
One can see that the MISDP problems were harder to solve than the corresponding SDPs for these relatively small problem instances. The MISDPs have the advantage of finding extremal solutions, however, in the case M = d B , and may scale better to large instances. Additionally, the active-set upper bound performed fairly well, finding feasible points within 20 % of the optimum in all cases, with only t max = 20 s, and often finding near-optimal solutions. It was also the only method able to scale to the largest instances tested, such as two copies of the BB84 states (which involves 16 quantum states in dimension four, and for which the SDP formulation has 16! variables.). In general, the commercial solvers performed better than the open source solvers, with the notable exception of the active-set upper bound with MOSEK, in which two more problems timed out than with SCS. This could be due to SCS being a first-order solver which can therefore possibly scale to larger problem instances than MOSEK, which is a second-order solver.

VII. PROPERTIES OF GUESSWORK WITH QUANTUM SIDE INFORMATION
A. Concavity of the guesswork Proposition 6: For each cost vector c and K ≤ |X |, the function from the set of c-q states of the form (4) to R ≥0 ∪ {∞}, is concave.
Proof. For g ∈ X K = , and ρ XB a c-q state, the quantity R ρ g := x∈X p X (x)c N ( g,x) ρ x B can be expressed as and hence is linear in ρ XB . Then for each POVM (E g ) g∈X K = , is linear in ρ XB . The arbitrary infimum of concave functions, and in particular linear functions, is concave, and hence where the minimum is taken over all POVMs on system B with outcomes in X K = , is concave. Remark 7: Theorem 6 carries over to guesswork without side information, G(X), which simply corresponds to the case that ρ x B ≡ ρ B is independent of x ∈ X . Since G(X) is manifestly symmetric under permutations of the density p X , this proves that G(X) is a Schur concave function of the distribution p X (i.e., decreasing in the majorization preorder; see, e.g., [34] for an overview of majorization and Schur concave functions). Consequently, the work [35] provides an algorithm to calculate local continuity bounds for G(X).  B. Continuity of the guesswork Proposition 8: For each cost vector c and K ≤ |X |, such that either c ∞ < ∞ or K = |X |, the function from the set of c-q states of the form (4) to R ≥0 , is Lipschitz continuous, satisfying the bound  for any c-q states ρ XB and σ XB , where κ = c ∞ if K < |X |, Then, by linearity (as discussed in the proof of Theorem 6), (117) using (111), where C ( g) XB and ∆ XB commute, using the c-q structure of each, we have Set (121) Since c N ( g,x) ≤ κ for each x ∈ X and g ∈ X K = , we have that Performing the sums, we have F XB ≤ κ I X ⊗ I B and hence F XB ∞ ≤ κ. Thus, using Hölder's inequality in the second to last inequality. Swapping ρ XB and σ XB completes the proof.

VIII. SIMPLE EXAMPLES A. BB84 states as side information
As an example, we consider the problem of calculating guesswork when one has four uniformly distributed letters to guess from, each correlated to one of the four BB84 states [36]. That is, with the four |ψ k 's being chosen from {|0 , |1 , |+ , |− }. This example is firmly in the quantum realm of guesswork, as more information about the side information system B can be obtained via a quantum measurement than a classical one (in the computational basis, that is). We establish an analytic upper bound on the guesswork by considering a particular POVM and associated sequences of guesses. We consider the POVM consisting of two orthogonal projectors |θ θ| and |θ ⊥ θ ⊥ | with |θ := sin θ |0 + cos θ |1 .  Fig. 2. The guesswork G(X|B) as a function of the parameter ϕ, when X is uniformly distributed over {1, 2, 3, 4} and the corresponding side information states are {|0 , |1 , |ψ(ϕ) , |ψ(−ϕ) }, where |ψ(ϕ) = cos(ϕ/2) |0 + sin(ϕ/2) |1 . We see that for classical states, i.e., when ϕ = 0 or ϕ = π, we obtain a maximum value of 1.75. For the BB84 states (ϕ = π/2), we achieve a minimum.
If the outcome corresponding to |θ θ| is obtained, then we guess in the order corresponding to (1, +, −, 0). Similarly, the guessing order corresponding to the other outcome θ ⊥ is (0, −, +, 1), which is the reverse order.
Furthermore, we can use this example to delineate the difference, or gap, between guesswork with classical and quantum information. There are two ways of reducing the example of BB84 states to a classical setting: (a) restricting to measurements in the standard basis {|0 , |1 }, or (b) replacing the side information states |+ and |− with the maximally mixed qubit state π 2 . In both of these cases, the side information then takes the form of a random variable Y . The joint probability distribution of variables XY is given as follows: Given either value of Y , one needs an average of 1.75 guesses. Hence in this classical analogue of the BB84 states, the guesswork is 1.75. This is higher than the lower value (≈ 1.709) that can be achieved by quantum measurements.

B. Qubit trine states as side information
In this example, we consider the problem of calculating guesswork with three uniformly distributed letters to guess from, each correlated to one of the three qubit trine states [38]. That is, where |ψ k = cos k 2π 3 |0 + sin k 2π 3 |1 . As in the previous example of the BB84 states, here too we establish an analytic upper bound on the guesswork by considering a particular POVM. Consider that the measurement is characterized by two orthogonal projectors |θ θ| and |θ ⊥ θ ⊥ | with |θ := cos θ |0 + sin θ |1 . For the sake of simplicity, we restrict to θ ∈ [0, π/2]. For the outcome corresponding to θ, we guess in the order corresponding to (ψ 2 , ψ 3 , ψ 1 ), and for the outcome corresponding to θ ⊥ , we guess in the order corresponding to (ψ 1 , ψ 3 , ψ 2 ).
Further, in this example, if we restrict to measuring in the standard basis (mimicking the classical analogue of the side information), then the average number of guesses needed is 1.5, in contrast to ≈ 1.4227 guesses needed using the optimal quantum measurement.

AN IMPERFECT KEY STATE
A primitive in any cryptography scheme is the establishment of a secret key between two communicating parties. Quantum key distribution (QKD) protocols can produce a certifiably secure secret key by using pre-shared entanglement [39].
However, if the protocol is not implemented perfectly, as is the case in realistic scenarios, then some information can leak out to an eavesdropper. How secure is the key obtained in this "imperfect" scenario? In other words, if there is a small deviation from the ideal protocol, how does it affect the security of the key? We address this question considering the guesswork as a security criterion.
Consider two systems K and E, where K denotes the key system and encodes the secret key, and E is the system held by the eavesdropper. An ideal key state is of the form π K ⊗ ρ E where π K refers to the maximally mixed state on the key system. This means that the eavesdropper can learn nothing about the key with access to the E system alone. An imperfect key, generally, is the joint state ρ KE . Consider the promise that the imperfect key state is ε-close to an ideal one in normalized trace distance: For an ideal key state, the expected guesswork for the eavesdropper is where |K| indicates the cardinality of the alphabet associated to system K. We have the following result: Theorem 9: For an imperfect key state satisfying the promise in (131), the following bound on guesswork holds