Using a mixed-integer SDP to find extremal strategies

Let us revisit Example 2: the BB84 states using a mixed-integer SDP. This allows us to specify the number of non-zero POVM elements in the measurement– or, equivalently, the number of possible guessing orders the final strategy chooses among.

We will use the Pajarito.jl solver, which solves mixed-integer SDPs by solving an alternating sequence of mixed-integer linear programs and SDPs; see the Pajarito paper for information on how Pajarito works. Pajarito requires both an SDP solver and a mixed-integer linear solver; we will use the open source solvers SCS and Cbc, respectively.

julia> using GuessworkQuantumSideInfo

julia> using Pajarito, Cbc, SCS # solvers
WARNING: Method definition findnz(AbstractArray{T, 2} where T) in module Pajarito at /home/runner/.julia/packages/Pajarito/PL3Lt/src/Pajarito.jl:42 overwritten in module ConicBenchmarkUtilities at /home/runner/.julia/packages/ConicBenchmarkUtilities/HFwIl/src/ConicBenchmarkUtilities.jl:17.

julia> function misdp_solver(; verbose = false)
           sdp_solver = SCSSolver(verbose=0)
           mip_solver = CbcSolver(loglevel = 0)
           PajaritoSolver(
               cont_solver = sdp_solver,
               mip_solver = mip_solver,
               mip_solver_drives = false,
               use_mip_starts = true,
               solve_relax = false,
               log_level = verbose ? 3 : 0,
           )
       end
misdp_solver (generic function with 1 method)

julia> p = ones(4)/4
4-element Array{Float64,1}:
 0.25
 0.25
 0.25
 0.25

julia> ρBs = BB84_states()
4-element Array{Array{Complex{Float64},2},1}:
 [1.0+0.0im 0.0+0.0im; 0.0+0.0im 0.0+0.0im]
 [0.0+0.0im 0.0+0.0im; 0.0+0.0im 1.0+0.0im]
 [0.5+0.0im -0.5-0.0im; -0.5+0.0im 0.5+0.0im]
 [0.5+0.0im 0.5+0.0im; 0.5+0.0im 0.5+0.0im]

julia> output = guesswork_MISDP(p, ρBs, 2; verbose=false, solver = misdp_solver());
┌ Warning: Repeated integer solution without converging
└ @ Pajarito ~/.julia/packages/Pajarito/PL3Lt/src/conic_algorithm.jl:1687

julia> output.optval
1.7093860519374542

julia> output.Es
2-element Array{Array{Complex{Float64},2},1}:
 [0.658105+3.84045e-11im -0.474345+1.62822e-11im; -0.474339+1.62824e-11im 0.341881+2.86714e-11im]
 [0.341881+2.69118e-11im 0.474345-2.30137e-11im; 0.474339-2.30136e-11im 0.658106+6.49824e-12im]

We see that with only two measurement outcomes we recover the same optimal value as the case without a constraint on the number of measurement outcomes (in Example 2: the BB84 states). We've thus found an extremal strategy (in that the POVM associated to this strategy cannot be written as the convex combination of two other POVMs). Often, the solutions returned by guesswork do not return extremal POVMs, although the details depend on the SDP solver used.

We can see what the associated guessing orders are:

julia> output.povm_outcomes
2-element Array{NTuple{4,Int64},1}:
 (3, 1, 2, 4)
 (4, 2, 1, 3)

To summarize, one optimal strategy for the case of p uniform, and ρBs given by the four BB84 states, is to perform a projective measurement whose operators are given by output.Es above, and then make guesses in one of the two orders given by output.povm_outcomes (depending on which measurement outcome was obtained).