Improvements in Quantum SDP-Solving with Applications

1.1 Semidefinite programs

• A normalized positive semidefinite matrix can be represented as a quantum state, motivating quantum algorithms for faster SDP-solving [BS17].The paper also assumes a trace bound on primal solutions and a bounded-norm optimal dual solution.Source: §1.1 · p. 2

1.2 Input models & Subroutines

• The solver uses approximate Gibbs states and a trace estimator to estimate Tr(A_jρ).The introduction identifies Gibbs sampling and trace estimation as subroutines for the input models.Source: §1.2 · pp. 5–6

1.3 Previous work

• Earlier quantum SDP solvers used sparse-matrix or quantum-state inputs, and the Fast Quantum OR Lemma improved bounds by separating search from initial Gibbs-state preparation [BS17] [BKL+17] [BKL+18].Brandão et al. also applied a quantum SDP-solver to shadow tomography [BKL+17].Source: §1.3 · pp. 6–7, §1.4 · p. 7

1.4 Our results

• Two-Phase Quantum Minimum Finding improves general SDP-solving and primal-oracle upper bounds, building on the Fast Quantum OR Lemma and prior bounds [BS17] [AGGW17].The method extends the Gentle Quantum Search Lemma [Aar17] using the Fast Quantum OR Lemma [BKL+18]; γ = Θ(Rr/ε).Source: §1.4 · pp. 7–8
• The quantum operator model represents input matrices with block-encoding unitaries and generalizes the sparse and quantum state models through reductions with α = s and α = B, respectively.The reductions have constant overhead.Source: §1.2 · p. 4, §1.4 · p. 8
• The quantum-state Gibbs sampler avoids dependence on input-matrix rank, so the resulting SDP-solving complexity also avoids rank dependence.For this method, the text says n ≤ (KB)^2.5; otherwise reducing to the quantum operator model with α = B gives a better algorithm.Source: §1.4 · p. 8
• For operator-input SDP solving, the improved upper bound is matched up to polylogarithmic factors in n and m when γ and α are constant; the primal-oracle bound uses γ = R/ε.The text also states that the sparse-input results extend to the quantum operator model by replacing s with α.Source: §1.4 · pp. 8–9, Table 1 · p. 9
• For shadow tomography, the authors improve both Aaronson’s sample-complexity result [Aar17] and the best known implementation time [Aar17] [BKL+18] across input models.If the measurements can be efficiently implemented on a quantum computer, they can also be efficiently represented using the quantum operator input model.Source: §1.4 · p. 9
• For minimum-total-error quantum state discrimination, the authors give a sparse-input algorithm and extend the solver to states supplied as quantum states rather than classical density-operator descriptions.The problem is to find the best POVM for discriminating a set of states; k is the number of states and d their dimension.Source: §1.4 · pp. 9–10
• For E-optimal design, the sparse-input solver selects a distribution over k experiments to minimize variance for a d-dimensional system, with the final bound depending on P and experimental standard deviation.Source: §1.4 · p. 10
• The paper proves new lower bounds for quantum state and operator input models, showing that the √m factor and polynomial dependence on B, α, and 1/ε are necessary.The proofs use Gilyén et al.’s hybrid-method techniques [GAW17] and reductions based on smooth-functions-of-Hamiltonians techniques [AGGW17].Source: §1.4 · p. 10

2 SDP-solving frameworks

• Together, the Arora–Kale framework and a primal oracle implement a full SDP-solver.The first framework approximates the optimal value and finds an almost feasible dual solution.Source: §2 · p. 10

2.1 The Arora-Kale framework

• The Arora–Kale route searches for a θ-feasible y; if none exists, it concludes OPT > g, and the framework assumes y-updates cost less than a θ-oracle call.Source: §2.1 · p. 11

2.2 An SDP primal oracle

• The primal oracle rescales constraints and adds ω to work with density operators, then outputs y and z = R Tr(X′) when no violated constraint is found.The reduction preserves equivalence with only constant-factor complexity overhead.Source: §2.2 · pp. 11–12

3.1 Fast Quantum OR Lemma and Two-Phase Minimum Finding

• The Fast Quantum OR Lemma [BKL+18] yields Two-Phase Quantum Search from Aaronson’s Gentle Quantum Search [Aar17], and the authors use it to construct a two-phase minimum-finding algorithm.The minimum-finding procedure accommodates different additive error bars for the candidate values.Source: §3.1 · pp. 12–13
• Theorem 8 gives a quantum SDP-solver and a primal oracle with the same complexity, using γ = 6Rr/ε for the solver and γ = 6R/ε for the primal oracle.The theorem assumes that updating an entry of the y data structure takes at most the stated number of elementary operations.Source: §3.1 · p. 13

3.2.1 Block-encodings of operators

• Block-encodings enable Hamiltonian simulation and trace estimation, and the quantum operator input model encompasses sparse-matrix and purified-state inputs by choosing α = s or B, respectively.A block-encoding represents a matrix as a unitary’s top-left block, scaled by α.Source: §3.2.1 · pp. 15–16

3.2.2 Implementing a linear combination of block-encodings

• Linear combinations of block-encodings enable Gibbs-sampling without entrywise summation of input matrices, bypassing a major bottleneck in earlier sparse-input SDP solvers [AGGW17].The resulting Gibbs-sampler has query complexity Õ_θ(αK√n) in the quantum operator input model.Source: §3.2.2 · pp. 16–17
• Theorem 17 gives a quantum SDP-solver with γ = Rr/ε and a primal oracle with γ = R/ε, extending its bound to sparse-matrix and quantum-state models by setting α = s or B.The extension uses O(1) input-oracle queries and Õ(mnα γ) elementary operations to construct the operator-model input oracle.Source: §3.2.2 · p. 17
• Standard quantum minimum finding [DH96], instead of Two-Phase Minimum Finding, gives a slightly better dependence on γ.The passage refers to equation (6) for the comparison but does not provide its expression.Source: §3.2.2 · p. 17
• Corollary 18 gives a quantum-operator-input result, with γ=Rr/ε for a full SDP solver and γ=R/ε for a primal oracle.The supplied passage does not include the complexity expression.Source: §3.2.2 · p. 17

3.3 Exponentially improved Gibbs-sampling in the quantum state input model

• Lemma 21 constructs the Gibbs state by splitting the spectrum at a threshold, preparing Gibbs states on each part, and merging them; the above-threshold projector has rank at most 1/q.This avoids applying the same search procedure to the uniform distribution over all n dimensions.Source: §3.3 · p. 19
• The new quantum-state-input Gibbs sampler removes explicit dependence on input-matrix rank and improves precision dependence from polynomial to logarithmic, compared with Brandão et al. [BKL+18].Its success-probability dependence is worse, but SDP-solving needs success for only a constant fraction of random seeds.Source: §3.3 · pp. 18, 22
• Theorem 22 uses a random seed of O(log(β/δ)) bits and guarantees its stated result for at least a (1−δ) fraction of seeds.The result passage identifies a quantum-state preparation algorithm but its full complexity expression is not present in the supplied text.Source: §3.3 · p. 22
• Theorem 24 gives a quantum-state-input SDP-solver result with γ=Rr/ε, or γ=R/ε for a primal oracle.The supplied passages identify the theorem and parameter definitions but omit its complexity expression.Source: §3.3 · pp. 22–23

4 Applications

• The applications extend quantum SDP-solving to shadow tomography, quantum state discrimination, and E-optimal design, with speedups over classical methods in some parameters but heavy dependence on others.Source: §4 · p. 23

4.1 Improved shadow tomography

• Controlled implementations of the shadow-tomography measurements can be converted to block-encodings at essentially the same cost, enabling descriptive shadow tomography using controlled measurements.Source: §4.1 · p. 25

4.2 Quantum state discrimination

• The authors target a quantum speedup in the number of states k at the expense of slower dependence on dimension d, and also consider access through state-preparation unitaries.Source: §4.2 · p. 26
• The discrimination algorithm returns a classical dual solution and a concise primal description encoding k POVM operators using a single d × d matrix Y′ and the input states.Source: §4.2 · p. 27

4.3 Optimal design

• The E-optimal design algorithm finds a distribution maximizing the smallest eigenvalue of the Fisher information matrix using quantum queries to sparse experiment vectors and their precision values.Source: §4.3 · p. 28

• The paper’s improved upper bounds make the dependence on n and m tight up to logarithmic factors, while an interesting lower bound depending on s and Rr/ε remains open.Source: §5 · p. 30
• The lower-bound results establish necessary query dependence on m, precision ε, and input normalization, including B for the quantum state model.Source: §5 · pp. 30, 32
• A Hamiltonian-discrimination reduction gives an LP, and hence an SDP, with R,r=O(1) whose ε-approximate solution distinguishes the oracle cases.Source: §5 · pp. 30–31
• For the quantum state input model, the lower-bound reduction is given only for LPs, where all input matrices are diagonal.Source: §5 · p. 32

• The appendix uses controlled Hamiltonian simulation to implement smooth functions of a Hamiltonian as block-encodings, following the method of [AGGW17].Source: A Implementing smooth functions of… · p. 35
• The smooth-function result also applies to negative powers of a Hamiltonian.Source: A Implementing smooth functions of… · p. 35
• For −I ⪯ A ⪯ I, the trace estimator has bias at most θ and standard deviation at most 6, using one controlled simulation circuit and additional two-qubit gates.Source: A Implementing smooth functions of… · p. 35
• A block-encoding of H can be used to implement its controlled (M, τ)-simulation, with the required number of controlled-unitary uses depending on the lemma’s parameters.Source: A Implementing smooth functions of… · p. 36