GuessworkQuantumSideInfo

guesswork(
    p::AbstractVector{T},
    ρBs::AbstractVector{<:AbstractMatrix};
    solver,
    K::Integer = length(p),
    c = T[1:K..., 5_000],
    dual::Bool = false,
    remove_repetition::Bool = true,
    povm_outcomes = make_povm_outcomes(length(p), K, remove_repetition),
    verbose::Bool = true,
)

Computes the guesswork for the c-q state specified by a probability vector p, giving the distribution X, and ρBs, giving the associated quantum states.

The keyword arguments are as follows:

• solver is the only required keyword argument; an SDP solver such as SCS or MOSEK must be passed.
• K corresponds to the maximum number of allowed guesses. The number of variables in the primal SDP (and the number of constraints in the dual SDP) scales as length(p)^K.
• c may be given a custom cost vector. If K < length(p), then c should be of length K+1. The last entry, c[K+1], corresponds to the cost of not guessing the correct answer within K guesses.
• dual is a boolean variable indicating whether the primal or dual optimization problem should be solved.
• remove_repetition is a boolean variable defaulting to true, indicating whether repeated guesses of the same value should be removed; as long as c is increasing, this decreases the size of the SDP without affecting the optimal value.
• povm_outcomes should be an iterator (or vector) corresponding to the possible guessing orders. This defaults to all subsets of length K of 1:length(p) without repetition.
• verbose is a boolean which indicates if warnings should be printed when the problem is not solved optimally.

guesswork_lower_bound(
    p::AbstractVector{T},
    ρBs::AbstractVector{<:AbstractMatrix};
    solver,
    c = T[1:length(p)..., 10_000],
    verbose::Bool = false,
)

See guesswork for the meaning of the arguments. Computes a lower bound to the optimal expected number of guesses by solving a relaxed version of the primal SDP. For J states, only needs J^2 PSD variables subject to two linear constraints.

guesswork_upper_bound(
    p::AbstractVector{T},
    ρBs::AbstractVector{<:AbstractMatrix};
    make_solver,
    c::AbstractVector = T.(1:length(p)),
    max_retries = 50,
    max_time = Inf,
    num_constraints = Inf,
    verbose::Bool = false,
    num_steps_per_SA_run::Integer = length(p)^2 * 500,
) where {T<:Number} -> NamedTuple

Computes an upper bound to the guesswork problem associated to the c-q state specified by p and ρBs, as in guesswork. A custom cost vector c may be optionally passed. If the keyword argument verbose is set to true, information is printed about each iteration of the algorithm.

The keyword argument make_solver is required, and must pass a function that creates a solver instances. For example, instead of passing SCSSolver(), pass () -> SCSSolver(). This is needed because the algorithm used in guesswork_upper_bound solves a sequence of SDPs, not just one.

The algorithm has three termination criteria which are controlled by keyword arguments. The algorithm stops when any of the following occur:

• max_retries simulated annealing attempts fail to find a violated constraint.
• num_constraints constraints have been added to the dual SDP
• The total runtime of the algorithm is projected to exceed max_time on the next iteration.

By default, max_retries is set to 50, while num_constraints and max_time are set to infinity.

Lastly, the keyword argument num_steps_per_SA_run controls the runtime of the simulated annealing algorithm. Increase num_steps_per_SA_run to search longer for a violated constraint within a given simulated annealing run.

ket([T = Float64], i::Integer, d::Integer) -> SparseVector{Complex{T}}

Create a vector representing the ith computational basis vector in dimension d.

Example

julia> ket(1,2)
2-element SparseVector{Complex{Float64},Int64} with 1 stored entry:
  [1]  =  1.0+0.0im

julia> collect(ans)
2-element Array{Complex{Float64},1}:
 1.0 + 0.0im
 0.0 + 0.0im

bra([T = Float64], i::Integer, d::Integer) -> SparseVector{Complex{T}}'

Create a dual vector representing the bra associated to ith computational basis vector in dimension d.

Example

julia> bra(1,2)
1×2 LinearAlgebra.Adjoint{Complex{Float64},SparseVector{Complex{Float64},Int64}}:
 1.0-0.0im  0.0-0.0im

julia> collect(ans)
1×2 Array{Complex{Float64},2}:
 1.0-0.0im  0.0-0.0im

BB84_states([T::Type = Float64])

Generates the BB84 states |0⟩, |1⟩, |-⟩, and |+⟩, for use in guesswork or other functions. The numeric type can be optionally specified by the argument.

iid_copies(ρBs::AbstractVector{<:AbstractMatrix}, n::Integer) -> Vector{Matrix}

Create a vector of all states of the form $ρ_1 \otimes \dotsm \otimes ρ_n$ where the $ρ_i$ range over the set ρBs.

randdm([rng, T = Float64], d)

Generates a density matrix with numeric type Complex{T}, of dimension d at random.

Example

julia> randdm(2)
2×2 Array{Complex{Float64},2}:
 0.477118+0.0im        0.119848-0.0371569im
 0.119848+0.0371569im  0.522882+0.0im      

randprobvec([rng, T=Float64], d)

Generates points of type T, uniformly at random on the standard d-1 dimensional simplex using an algorithm by Smith and Tromble.

Example

julia> randprobvec(3)
3-element Array{Float64,1}:
 0.24815974900033688
 0.17199716455672287
 0.5798430864429402 

pmfN(data; tol = 1e-5) -> Vector

Compute the probability mass function for the number of guesses N, given a strategy. The nth entry of the output vector gives the probability for guessing the correct answer on the nth try, for n = 1 : K. If the number of allowed guesses, K, is smaller than length(p), then there is an additional last entry which gives the probability of never guessing the correct answer.

• data should be a NamedTuple with entries for p, ρBs, Es, K, and povm_outcomes
• tol provides a tolerance above which to warn about imaginary or negative probabilities.