Algorithms · Optimization · semidefinite programming

Semidefinite programming by quantum Gibbs sampling

Optimization

View frozen graph

Record typeLiterature reference
Speedup class (secondary source)Polynomial (with some exceptions)
Primary source on the speedupStated by the primary source: "This gives a square-root unconditional speed-up over any classical method for solving SDPs both in n and m."
Reported costBrandão and Svore's abstract gives a worst-case running time n^(1/2) m^(1/2) s^2 poly(log(n), log(m), R, r, 1/δ), with n the dimension and s the row-sparsity of the input matrices, m the number of constraints, δ the accuracy of the solution, and R and r upper bounds on the size of the optimal primal and dual solutions — in that paper r is a solution-size bound, not a rank — together with an Ω(n^(1/2) + m^(1/2)) quantum lower bound for constant s, R, r and δ. Their own Corollary 5 instantiates that poly as Õ(n^(1/2) m^(1/2) s^2 R^32/δ^18), and van Apeldoorn, Gilyén, Gribling and de Wolf record that this figure is for multiplicative error 1 ± δ in the special case b_j ≥ 1 and OPT ≥ 1, and that the reduction from a general SDP to that special case significantly worsens the dependence on R, r and δ; the paper's own reduction sends δ to δ/r and R to 2R + 1. Van Apeldoorn et al. keep the same dependence on m, n and s and improve the rest, reporting Õ(√(mn) s^2 (Rr/ε)^8), and Õ(√(mn) (Rr/ε)^5) for the special case of linear programs; in their paper R bounds the trace of an optimal primal X and r the sum of entries of an optimal dual y, and they argue that R, r and 1/ε trade against one another and should be read as the single parameter Rr/ε. Brandão, Kalev, Li, Lin, Svore and Wu report Õ(s^2 (√m ε^(-10) + √n ε^(-12))) in the entry-oracle model, but for their own normalised feasibility problem, which carries tr(X) = 1: they state that converting a general primal with width bound tr(X) ≤ R into that form changes ε to ε/R, and to ε divided by R times their dual bound if a strictly feasible solution is wanted, so the ε in those exponents is not the ε of a general SDP and the bound is not a version in which the size parameters have vanished. The same paper performs exactly that substitution when it restates Brandão and Svore's cost as Õ(√(mn) s^2 (R R-tilde/ε)^32), R-tilde being its name for the bound on the optimal dual solution. Its second bound, Õ(√m + poly(r)) · poly(log m, log n, B, ε^(-1)) with r the rank of the constraint matrices and B an upper bound on their trace norm, belongs to a fully quantum input model in which the matrices are supplied as quantum states. The Zoo's composite figure O(√m log m · poly(log n, r, ε^(-1))), with r read as the rank, is that second bound: it is the paper's Remark D.7, which takes the decomposition of each A_j to be its eigen-decomposition so that under the low-rank assumption B collapses to r, and s is absent because that model does not use sparsity at all. It is therefore not a bound in the entry-oracle model, where the same authors' Ω(√n) lower bound applies.
Papers5

A part this method uses, worked through

This page says Grover search — here is a concrete, runnable instance of it.

Grover's algorithm finds |101⟩

3 qubits, searching for |101⟩ among 8 states, with 2 Grover iterations.

Where it ends up

10195%
0001%
1101%
0011%
4 more outcomes3%

Measuring gives 101, the marked state, with high probability.

One of its steps changes only phase: the outcome probabilities stay put while the state does not.

Open this part in Studio

A part this method uses, worked through

This page says amplitude estimation — here is a concrete, runnable instance of it.

Canonical amplitude estimation

3 counting qubits estimating a = sin²(θ) for the one-qubit state A|0⟩ = RY(π/4)|0⟩, θ = π/8.

Where it ends up

000125%
011125%
100125%
111125%

The counting register reads 001 or 111, each equally likely: these are θ/π = 1/8 and its mirror 1 − 1/8 = 7/8, both exact in 3 bits by construction. Either one gives a = sin²(π/8) = (2 − √2) / 4 exactly, the standard amplitude-estimation formula a = sin²(πλ) applied to the smaller of the two readings.

Open this part in Studio

Given a list of m + 1 Hermitian n × n matrices C, A_1, A_2, …, A_m and m numbers b_1, …, b_m, find the positive semidefinite n × n matrix X that maximizes tr(CX) subject to the constraints tr(A_j X) ≤ b_j for j = 1, 2, …, m, approximately, to within ± ε of the optimum. The Zoo states that semidefinite programming has many applications in operations research, combinatorial optimization, and quantum information, and that it includes linear programming as a special case. All three papers reduce that optimization to a feasibility question by binary search on a guess for the optimal value, but not to the same feasibility question, and the difference carries a parameter that the runtimes below then depend on. Brandão and Svore add the constraint tr(X) ≤ R, with R a measure of the size of the optimal solution, and test the dual: they sample from the distribution y divided by the 1-norm of y for a dual feasible vector y. Van Apeldoorn, Gilyén, Gribling and de Wolf likewise test membership in a dual polytope induced by the current primal candidate, with R bounding the trace of an optimal primal X. Brandão, Kalev, Li, Lin, Svore and Wu instead normalise the primal to tr(X) = 1 and test it directly, deciding whether the constraints tr(A_i X) ≤ a_i + ε admit a positive semidefinite X of unit trace; Chia, Gilyén, Li, Lin, Tang and Wang adopt that same trace-one form for the dequantized version. Brandão and Svore quantize the Arora-Kale matrix multiplicative weights method for SDPs. That classical framework iterates: an oracle turns a primal candidate X into a dual candidate y, y defines a Hermitian matrix H, and the next primal candidate is proportional to e^(-H). The quantum move is that a matrix proportional to e^(-H) is a Gibbs state, so it can be prepared on log(n) qubits by quantum Gibbs sampling in much less time than it takes to compute X as an n × n matrix, and the oracle can then be implemented from copies of that state, since the quantities Tr(A_j X) it needs are expectation values of the constraint matrices in that state. Their abstract states the algorithm is a combination of quantum Gibbs sampling and the multiplicative weight method, and that they modify Arora and Kale's algorithm to eliminate the need for solving an inner linear program. Van Apeldoorn, Gilyén, Gribling and de Wolf quantize the same framework differently and faster: they coherently prepare a purification of the Gibbs state rather than copies of a mixed state, estimate the trace quantities by amplitude estimation, and find an explicit 2-sparse dual vector using a generalization of the Dürr-Høyer minimum-finding algorithm, which is based on Grover search; their purified Gibbs sampler has logarithmic dependence on the error, which they call exponentially better than the Poulin and Wocjan sampler Brandão and Svore invoke. Brandão, Kalev, Li, Lin, Svore and Wu give two solvers rather than one improvement. In the plain entry-oracle model they decouple the dependence on m and n, which used to be √(mn) and becomes √m + √n, an observation they credit jointly with van Apeldoorn and Gilyén to the quantum OR lemma. In a second, fully quantum input model the constraint matrices arrive as quantum states, and there their main technical contribution applies: a Gibbs state sampler for low-rank Hamiltonians, given quantum states encoding those Hamiltonians, whose dependence on the dimension is only poly-logarithmic. That sampler is stated over the same quantum-input oracles as the solver it enables, so it is not a model-free ingredient available to the entry-oracle solvers. The Zoo summarizes the whole line as based on amplitude amplification and quantum Gibbs sampling.

Brandão and Svore quantize the Arora-Kale matrix multiplicative weights method for SDPs. That classical framework iterates: an oracle turns a primal candidate X into a dual candidate y, y defines a Hermitian matrix H, and the next primal candidate is proportional to e^(-H). The quantum move is that a matrix proportional to e^(-H) is a Gibbs state, so it can be prepared on log(n) qubits by quantum Gibbs sampling in much less time than it takes to compute X as an n × n matrix, and the oracle can then be implemented from copies of that state, since the quantities Tr(A_j X) it needs are expectation values of the constraint matrices in that state. Their abstract states the algorithm is a combination of quantum Gibbs sampling and the multiplicative weight method, and that they modify Arora and Kale's algorithm to eliminate the need for solving an inner linear program. Van Apeldoorn, Gilyén, Gribling and de Wolf quantize the same framework differently and faster: they coherently prepare a purification of the Gibbs state rather than copies of a mixed state, estimate the trace quantities by amplitude estimation, and find an explicit 2-sparse dual vector using a generalization of the Dürr-Høyer minimum-finding algorithm, which is based on Grover search; their purified Gibbs sampler has logarithmic dependence on the error, which they call exponentially better than the Poulin and Wocjan sampler Brandão and Svore invoke. Brandão, Kalev, Li, Lin, Svore and Wu give two solvers rather than one improvement. In the plain entry-oracle model they decouple the dependence on m and n, which used to be √(mn) and becomes √m + √n, an observation they credit jointly with van Apeldoorn and Gilyén to the quantum OR lemma. In a second, fully quantum input model the constraint matrices arrive as quantum states, and there their main technical contribution applies: a Gibbs state sampler for low-rank Hamiltonians, given quantum states encoding those Hamiltonians, whose dependence on the dimension is only poly-logarithmic. That sampler is stated over the same quantum-input oracles as the solver it enables, so it is not a model-free ingredient available to the entry-oracle solvers. The Zoo summarizes the whole line as based on amplitude amplification and quantum Gibbs sampling. This record's speedup class, "Polynomial (with some exceptions)", is a secondary source's classification of the optimization, numerics, and machine learning it files this under — not a claim its primary paper makes. Stated by the primary source: "This gives a square-root unconditional speed-up over any classical method for solving SDPs both in n and m.". Reported cost: Brandão and Svore's abstract gives a worst-case running time n^(1/2) m^(1/2) s^2 poly(log(n), log(m), R, r, 1/δ), with n the dimension and s the row-sparsity of the input matrices, m the number of constraints, δ the accuracy of the solution, and R and r upper bounds on the size of the optimal primal and dual solutions — in that paper r is a solution-size bound, not a rank — together with an Ω(n^(1/2) + m^(1/2)) quantum lower bound for constant s, R, r and δ. Their own Corollary 5 instantiates that poly as Õ(n^(1/2) m^(1/2) s^2 R^32/δ^18), and van Apeldoorn, Gilyén, Gribling and de Wolf record that this figure is for multiplicative error 1 ± δ in the special case b_j ≥ 1 and OPT ≥ 1, and that the reduction from a general SDP to that special case significantly worsens the dependence on R, r and δ; the paper's own reduction sends δ to δ/r and R to 2R + 1. Van Apeldoorn et al. keep the same dependence on m, n and s and improve the rest, reporting Õ(√(mn) s^2 (Rr/ε)^8), and Õ(√(mn) (Rr/ε)^5) for the special case of linear programs; in their paper R bounds the trace of an optimal primal X and r the sum of entries of an optimal dual y, and they argue that R, r and 1/ε trade against one another and should be read as the single parameter Rr/ε. Brandão, Kalev, Li, Lin, Svore and Wu report Õ(s^2 (√m ε^(-10) + √n ε^(-12))) in the entry-oracle model, but for their own normalised feasibility problem, which carries tr(X) = 1: they state that converting a general primal with width bound tr(X) ≤ R into that form changes ε to ε/R, and to ε divided by R times their dual bound if a strictly feasible solution is wanted, so the ε in those exponents is not the ε of a general SDP and the bound is not a version in which the size parameters have vanished. The same paper performs exactly that substitution when it restates Brandão and Svore's cost as Õ(√(mn) s^2 (R R-tilde/ε)^32), R-tilde being its name for the bound on the optimal dual solution. Its second bound, Õ(√m + poly(r)) · poly(log m, log n, B, ε^(-1)) with r the rank of the constraint matrices and B an upper bound on their trace norm, belongs to a fully quantum input model in which the matrices are supplied as quantum states. The Zoo's composite figure O(√m log m · poly(log n, r, ε^(-1))), with r read as the rank, is that second bound: it is the paper's Remark D.7, which takes the decomposition of each A_j to be its eigen-decomposition so that under the low-rank assumption B collapses to r, and s is absent because that model does not use sparsity at all. It is therefore not a bound in the entry-oracle model, where the same authors' Ω(√n) lower bound applies..

Record type: Literature reference
Speedup class (secondary source): Polynomial (with some exceptions)
Primary source on the speedup: Stated by the primary source: "This gives a square-root unconditional speed-up over any classical method for solving SDPs both in n and m."
Reported cost: Brandão and Svore's abstract gives a worst-case running time n^(1/2) m^(1/2) s^2 poly(log(n), log(m), R, r, 1/δ), with n the dimension and s the row-sparsity of the input matrices, m the number of constraints, δ the accuracy of the solution, and R and r upper bounds on the size of the optimal primal and dual solutions — in that paper r is a solution-size bound, not a rank — together with an Ω(n^(1/2) + m^(1/2)) quantum lower bound for constant s, R, r and δ. Their own Corollary 5 instantiates that poly as Õ(n^(1/2) m^(1/2) s^2 R^32/δ^18), and van Apeldoorn, Gilyén, Gribling and de Wolf record that this figure is for multiplicative error 1 ± δ in the special case b_j ≥ 1 and OPT ≥ 1, and that the reduction from a general SDP to that special case significantly worsens the dependence on R, r and δ; the paper's own reduction sends δ to δ/r and R to 2R + 1. Van Apeldoorn et al. keep the same dependence on m, n and s and improve the rest, reporting Õ(√(mn) s^2 (Rr/ε)^8), and Õ(√(mn) (Rr/ε)^5) for the special case of linear programs; in their paper R bounds the trace of an optimal primal X and r the sum of entries of an optimal dual y, and they argue that R, r and 1/ε trade against one another and should be read as the single parameter Rr/ε. Brandão, Kalev, Li, Lin, Svore and Wu report Õ(s^2 (√m ε^(-10) + √n ε^(-12))) in the entry-oracle model, but for their own normalised feasibility problem, which carries tr(X) = 1: they state that converting a general primal with width bound tr(X) ≤ R into that form changes ε to ε/R, and to ε divided by R times their dual bound if a strictly feasible solution is wanted, so the ε in those exponents is not the ε of a general SDP and the bound is not a version in which the size parameters have vanished. The same paper performs exactly that substitution when it restates Brandão and Svore's cost as Õ(√(mn) s^2 (R R-tilde/ε)^32), R-tilde being its name for the bound on the optimal dual solution. Its second bound, Õ(√m + poly(r)) · poly(log m, log n, B, ε^(-1)) with r the rank of the constraint matrices and B an upper bound on their trace norm, belongs to a fully quantum input model in which the matrices are supplied as quantum states. The Zoo's composite figure O(√m log m · poly(log n, r, ε^(-1))), with r read as the rank, is that second bound: it is the paper's Remark D.7, which takes the decomposition of each A_j to be its eigen-decomposition so that under the low-rank assumption B collapses to r, and s is absent because that model does not use sparsity at all. It is therefore not a bound in the entry-oracle model, where the same authors' Ω(√n) lower bound applies.
Speedup class: Polynomial (with some exceptions) (checked against the record's own primary paper, which states it)
Complexity basis: Abstract of arXiv:1609.05537 (inline TeX rendered into plain text: the fraction exponents are written n^(1/2) m^(1/2), and "a upper bounds" is the abstract's own wording): "It has worst-case running time n^(1/2) m^(1/2) s^2 poly(log(n), log(m), R, r, 1/δ), with n and s the dimension and row-sparsity of the input matrices, respectively, m the number of constraints, δ the accuracy of the solution, and R, r a upper bounds on the size of the optimal primal and dual solutions", and "We prove the algorithm cannot be substantially improved (in terms of n and m) giving a Ω(n^(1/2)+m^(1/2)) quantum lower bound for solving semidefinite programs with constant s, R, r and δ". The same paper, Corollary 5 (page 8 of v5): "Using the Gibbs Sampler from Ref. [13], Algorithm 3 runs in time Õ(n^(1/2) m^(1/2) s^2 R^32/δ^18)"; its section 2.2: "Our algorithm will only work for SDPs for which b_i ≥ 1 for all i ∈ [m]", "We will also assume that α ≥ 1", and Lemma 2, which supplies "a δ-optimal solution" of the general SDP "given the ability to sample from a (δ/r)-optimal solution" of an SDP "with dimension n + 1, m + 1 variables and size parameter 2R + 1" in which b_i ≥ 1. The scoping of that corollary is arXiv:1705.01843 section 1.3: "Using these ideas, Brandão and Svore obtain a quantum SDP-solver of complexity Õ(√(mn) s^2 R^32/δ^18), with multiplicative error 1 ± δ for the special case where b_j ≥ 1 for all j ∈ [m], and OPT ≥ 1 … They describe a reduction to transform a general SDP of the form (1) to this special case, but that reduction significantly worsens the dependence of the complexity on the parameters R, r, and δ". Section 1.4.1 of arXiv:1705.01843, headed "Improved quantum SDP-solver": "These modifications both simplify and speed up the quantum SDP-solver, resulting in complexity Õ(√(mn) s^2 (Rr/ε)^8)", "The dependence on m, n, and s is the same as in Brandão-Svore, but our dependence on R, r, and 1/ε is substantially better", "These trade-offs suggest we should actually think of Rr/ε as one parameter of the primal-dual pair of SDPs, not three separate parameters", and "For the special case of LPs, we can improve the runtime to Õ(√(mn)(Rr/ε)^5)"; the same paper's section 1.2 defines those parameters — "Let R be an upper bound on the trace of an optimal X of the primal, r be an upper bound on the sum of entries of an optimal y for the dual" — and its footnote 3 states "The Õ(·) notation hides polylogarithmic factors in all parameters". Abstract of arXiv:1710.02581: "We consider SDP instances with m constraint matrices, each of dimension n, rank at most r, and sparsity s", "We show that it has run time Õ(s^2(√m ε^(-10)+√n ε^(-12))), with ε the error of the solution. This gives an optimal dependence in terms of m, n and quadratic improvement over previous quantum algorithms when m≈n", and "We show that its run time is Õ(√m+poly(r))·poly(log m, log n, B, ε^(-1)), with B an upper bound on the trace-norm of all input matrices. In particular the complexity depends only poly-logarithmically in n and polynomially in r". Its problem (1.1) carries "Tr(A_i X) ≤ a_i + ε ∀ i ∈ [m]; X ⪰ 0; Tr[X] = 1", and the conversion is stated in the same section 1: "for general feasible solution X ⪰ 0 with width bound Tr(X) ≤ R, there is a procedure to derive an equivalent SDP feasibility instance with variable X-hat s.t. Tr(X-hat) = 1. Note, however, the change of ε to ε/R in this conversion. Also note one can use an approximate feasibility solver to find a strictly feasible solution, by changing ε to ε/R R-tilde (see Lemma 18 of Ref. [9])" — R-tilde is that paper's R with a tilde and X-hat its X with a hat, both rendered here as plain text. The same section restates the primary paper's cost under that substitution: "giving a quantum algorithm with worst-case running time Õ(√(mn) s^2 (R R-tilde/ε)^32) … and R, R-tilde upper bounds on the norm of the optimal primal and dual solutions". The Zoo's composite figure is that paper's Remark D.7: "If we assume this decomposition to be the eigen-decomposition … then by the low-rank assumption and −I ⪯ A_j ⪯ I, Tr[A_j^+] + Tr[A_j^−] ≤ r. In this case, Corollary 5 takes at most √m · poly(log m, log n, r, ε^(-1)) quantum gates and queries to Oracle D.1, Oracle D.2, and Oracle D.3" — where Corollary 5 is introduced as "the following complexity result for solving SDPs under the quantum input model", and the same paper notes "our quantum SDP solver in Corollary 9 does not assume the sparsity of A_i's, which are crucial for the quantum SDP solvers with the plain model". The Zoo's own wording (LaTeX rendered into plain text) is: "quantum algorithms are now known that can approximately solve semidefinite programs to within ± ε in time O(√m log m · poly(log n, r, ε^(-1))), where r is the rank of the semidefinite program. This constitutes a quadratic speedup over the fastest classical algorithms when r is small compared to n".
Circuit: Not supplied

Quantum vs classical

Classical baseline

Compare Optimization · semidefinite programming with the strongest classical method for the same instance, input budget, and output metric.

Quantum claim

This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.

How to compare

Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.

FrameworkUnsupported

semidefinite-programming.txt

ALGORITHM: Semidefinite programming by quantum Gibbs sampling
PROBLEM: Given a list of m + 1 Hermitian n × n matrices C, A_1, A_2, …, A_m and m numbers b_1, …, b_m, find the positive semidefinite n × n matrix X that maximizes tr(CX) subject to the constraints tr(A_j X) ≤ b_j for j = 1, 2, …, m, approximately, to within ± ε of the optimum. The Zoo states that semidefinite programming has many applications in operations research, combinatorial optimization, and quantum information, and that it includes linear programming as a special case. All three papers reduce that optimization to a feasibility question by binary search on a guess for the optimal value, but not to the same feasibility question, and the difference carries a parameter that the runtimes below then depend on. Brandão and Svore add the constraint tr(X) ≤ R, with R a measure of the size of the optimal solution, and test the dual: they sample from the distribution y divided by the 1-norm of y for a dual feasible vector y. Van Apeldoorn, Gilyén, Gribling and de Wolf likewise test membership in a dual polytope induced by the current primal candidate, with R bounding the trace of an optimal primal X. Brandão, Kalev, Li, Lin, Svore and Wu instead normalise the primal to tr(X) = 1 and test it directly, deciding whether the constraints tr(A_i X) ≤ a_i + ε admit a positive semidefinite X of unit trace; Chia, Gilyén, Li, Lin, Tang and Wang adopt that same trace-one form for the dequantized version.
IDEA: Brandão and Svore quantize the Arora-Kale matrix multiplicative weights method for SDPs. That classical framework iterates: an oracle turns a primal candidate X into a dual candidate y, y defines a Hermitian matrix H, and the next primal candidate is proportional to e^(-H). The quantum move is that a matrix proportional to e^(-H) is a Gibbs state, so it can be prepared on log(n) qubits by quantum Gibbs sampling in much less time than it takes to compute X as an n × n matrix, and the oracle can then be implemented from copies of that state, since the quantities Tr(A_j X) it needs are expectation values of the constraint matrices in that state. Their abstract states the algorithm is a combination of quantum Gibbs sampling and the multiplicative weight method, and that they modify Arora and Kale's algorithm to eliminate the need for solving an inner linear program. Van Apeldoorn, Gilyén, Gribling and de Wolf quantize the same framework differently and faster: they coherently prepare a purification of the Gibbs state rather than copies of a mixed state, estimate the trace quantities by amplitude estimation, and find an explicit 2-sparse dual vector using a generalization of the Dürr-Høyer minimum-finding algorithm, which is based on Grover search; their purified Gibbs sampler has logarithmic dependence on the error, which they call exponentially better than the Poulin and Wocjan sampler Brandão and Svore invoke. Brandão, Kalev, Li, Lin, Svore and Wu give two solvers rather than one improvement. In the plain entry-oracle model they decouple the dependence on m and n, which used to be √(mn) and becomes √m + √n, an observation they credit jointly with van Apeldoorn and Gilyén to the quantum OR lemma. In a second, fully quantum input model the constraint matrices arrive as quantum states, and there their main technical contribution applies: a Gibbs state sampler for low-rank Hamiltonians, given quantum states encoding those Hamiltonians, whose dependence on the dimension is only poly-logarithmic. That sampler is stated over the same quantum-input oracles as the solver it enables, so it is not a model-free ingredient available to the entry-oracle solvers. The Zoo summarizes the whole line as based on amplitude amplification and quantum Gibbs sampling.
REPORTED COST: Brandão and Svore's abstract gives a worst-case running time n^(1/2) m^(1/2) s^2 poly(log(n), log(m), R, r, 1/δ), with n the dimension and s the row-sparsity of the input matrices, m the number of constraints, δ the accuracy of the solution, and R and r upper bounds on the size of the optimal primal and dual solutions — in that paper r is a solution-size bound, not a rank — together with an Ω(n^(1/2) + m^(1/2)) quantum lower bound for constant s, R, r and δ. Their own Corollary 5 instantiates that poly as Õ(n^(1/2) m^(1/2) s^2 R^32/δ^18), and van Apeldoorn, Gilyén, Gribling and de Wolf record that this figure is for multiplicative error 1 ± δ in the special case b_j ≥ 1 and OPT ≥ 1, and that the reduction from a general SDP to that special case significantly worsens the dependence on R, r and δ; the paper's own reduction sends δ to δ/r and R to 2R + 1. Van Apeldoorn et al. keep the same dependence on m, n and s and improve the rest, reporting Õ(√(mn) s^2 (Rr/ε)^8), and Õ(√(mn) (Rr/ε)^5) for the special case of linear programs; in their paper R bounds the trace of an optimal primal X and r the sum of entries of an optimal dual y, and they argue that R, r and 1/ε trade against one another and should be read as the single parameter Rr/ε. Brandão, Kalev, Li, Lin, Svore and Wu report Õ(s^2 (√m ε^(-10) + √n ε^(-12))) in the entry-oracle model, but for their own normalised feasibility problem, which carries tr(X) = 1: they state that converting a general primal with width bound tr(X) ≤ R into that form changes ε to ε/R, and to ε divided by R times their dual bound if a strictly feasible solution is wanted, so the ε in those exponents is not the ε of a general SDP and the bound is not a version in which the size parameters have vanished. The same paper performs exactly that substitution when it restates Brandão and Svore's cost as Õ(√(mn) s^2 (R R-tilde/ε)^32), R-tilde being its name for the bound on the optimal dual solution. Its second bound, Õ(√m + poly(r)) · poly(log m, log n, B, ε^(-1)) with r the rank of the constraint matrices and B an upper bound on their trace norm, belongs to a fully quantum input model in which the matrices are supplied as quantum states. The Zoo's composite figure O(√m log m · poly(log n, r, ε^(-1))), with r read as the rank, is that second bound: it is the paper's Remark D.7, which takes the decomposition of each A_j to be its eigen-decomposition so that under the low-rank assumption B collapses to r, and s is absent because that model does not use sparsity at all. It is therefore not a bound in the entry-oracle model, where the same authors' Ω(√n) lower bound applies.
BASIS: Abstract of arXiv:1609.05537 (inline TeX rendered into plain text: the fraction exponents are written n^(1/2) m^(1/2), and "a upper bounds" is the abstract's own wording): "It has worst-case running time n^(1/2) m^(1/2) s^2 poly(log(n), log(m), R, r, 1/δ), with n and s the dimension and row-sparsity of the input matrices, respectively, m the number of constraints, δ the accuracy of the solution, and R, r a upper bounds on the size of the optimal primal and dual solutions", and "We prove the algorithm cannot be substantially improved (in terms of n and m) giving a Ω(n^(1/2)+m^(1/2)) quantum lower bound for solving semidefinite programs with constant s, R, r and δ". The same paper, Corollary 5 (page 8 of v5): "Using the Gibbs Sampler from Ref. [13], Algorithm 3 runs in time Õ(n^(1/2) m^(1/2) s^2 R^32/δ^18)"; its section 2.2: "Our algorithm will only work for SDPs for which b_i ≥ 1 for all i ∈ [m]", "We will also assume that α ≥ 1", and Lemma 2, which supplies "a δ-optimal solution" of the general SDP "given the ability to sample from a (δ/r)-optimal solution" of an SDP "with dimension n + 1, m + 1 variables and size parameter 2R + 1" in which b_i ≥ 1. The scoping of that corollary is arXiv:1705.01843 section 1.3: "Using these ideas, Brandão and Svore obtain a quantum SDP-solver of complexity Õ(√(mn) s^2 R^32/δ^18), with multiplicative error 1 ± δ for the special case where b_j ≥ 1 for all j ∈ [m], and OPT ≥ 1 … They describe a reduction to transform a general SDP of the form (1) to this special case, but that reduction significantly worsens the dependence of the complexity on the parameters R, r, and δ". Section 1.4.1 of arXiv:1705.01843, headed "Improved quantum SDP-solver": "These modifications both simplify and speed up the quantum SDP-solver, resulting in complexity Õ(√(mn) s^2 (Rr/ε)^8)", "The dependence on m, n, and s is the same as in Brandão-Svore, but our dependence on R, r, and 1/ε is substantially better", "These trade-offs suggest we should actually think of Rr/ε as one parameter of the primal-dual pair of SDPs, not three separate parameters", and "For the special case of LPs, we can improve the runtime to Õ(√(mn)(Rr/ε)^5)"; the same paper's section 1.2 defines those parameters — "Let R be an upper bound on the trace of an optimal X of the primal, r be an upper bound on the sum of entries of an optimal y for the dual" — and its footnote 3 states "The Õ(·) notation hides polylogarithmic factors in all parameters". Abstract of arXiv:1710.02581: "We consider SDP instances with m constraint matrices, each of dimension n, rank at most r, and sparsity s", "We show that it has run time Õ(s^2(√m ε^(-10)+√n ε^(-12))), with ε the error of the solution. This gives an optimal dependence in terms of m, n and quadratic improvement over previous quantum algorithms when m≈n", and "We show that its run time is Õ(√m+poly(r))·poly(log m, log n, B, ε^(-1)), with B an upper bound on the trace-norm of all input matrices. In particular the complexity depends only poly-logarithmically in n and polynomially in r". Its problem (1.1) carries "Tr(A_i X) ≤ a_i + ε ∀ i ∈ [m]; X ⪰ 0; Tr[X] = 1", and the conversion is stated in the same section 1: "for general feasible solution X ⪰ 0 with width bound Tr(X) ≤ R, there is a procedure to derive an equivalent SDP feasibility instance with variable X-hat s.t. Tr(X-hat) = 1. Note, however, the change of ε to ε/R in this conversion. Also note one can use an approximate feasibility solver to find a strictly feasible solution, by changing ε to ε/R R-tilde (see Lemma 18 of Ref. [9])" — R-tilde is that paper's R with a tilde and X-hat its X with a hat, both rendered here as plain text. The same section restates the primary paper's cost under that substitution: "giving a quantum algorithm with worst-case running time Õ(√(mn) s^2 (R R-tilde/ε)^32) … and R, R-tilde upper bounds on the norm of the optimal primal and dual solutions". The Zoo's composite figure is that paper's Remark D.7: "If we assume this decomposition to be the eigen-decomposition … then by the low-rank assumption and −I ⪯ A_j ⪯ I, Tr[A_j^+] + Tr[A_j^−] ≤ r. In this case, Corollary 5 takes at most √m · poly(log m, log n, r, ε^(-1)) quantum gates and queries to Oracle D.1, Oracle D.2, and Oracle D.3" — where Corollary 5 is introduced as "the following complexity result for solving SDPs under the quantum input model", and the same paper notes "our quantum SDP solver in Corollary 9 does not assume the sparsity of A_i's, which are crucial for the quantum SDP solvers with the plain model". The Zoo's own wording (LaTeX rendered into plain text) is: "quantum algorithms are now known that can approximately solve semidefinite programs to within ± ε in time O(√m log m · poly(log n, r, ε^(-1))), where r is the rank of the semidefinite program. This constitutes a quadratic speedup over the fastest classical algorithms when r is small compared to n".
PRIMARY SOURCE: Fernando G. S. L. Brandao, Krysta Svore (2016), Quantum Speed-ups for Semidefinite Programming — https://arxiv.org/abs/1609.05537

This is a literature reference record, not an executable circuit.

A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.

References

Quantum Speed-ups for Semidefinite Programming
Fernando G. S. L. Brandao, Krysta Svore · 2016
Primary reference for semidefinite programming by quantum gibbs sampling; the source of this record's cost claim.
Quantum SDP-Solvers: Better upper and lower bounds
Joran van Apeldoorn, András Gilyén, Sander Gribling, Ronald de Wolf · 2017
One of the two improvements the Zoo cites, and the paper that states the limits of the approach most sharply. It improves the Brandão-Svore dependence on R, r and 1/ε to Õ(√(mn) s^2 (Rr/ε)^8) while keeping the same dependence on m, n and s, using a purified Gibbs sampler with logarithmic error-dependence and a generalized minimum-finding procedure; for linear programs it reports Õ(√(mn) (Rr/ε)^5). Consult it for four things this record depends on: the definitions of R and r as bounds on the trace of an optimal primal solution and on the sum of entries of an optimal dual solution; its restatement of the Brandão-Svore figure Õ(√(mn) s^2 R^32/δ^18) as holding with multiplicative error for the special case b_j ≥ 1 and OPT ≥ 1, with the reduction to that case significantly worsening the dependence on R, r and δ; the worst-case lower bound showing every quantum LP-solver and hence every quantum SDP-solver has to scale linearly with mn when m is about n; and its section 3, which shows that this approach fails for families of SDPs with a lot of symmetry.
Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning
Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, Xiaodi Wu · 2017
The other improvement the Zoo cites, and the source of the Zoo's own headline runtime. It gives two solvers for SDP instances with m constraint matrices of dimension n, rank at most r and sparsity s, both stated for its normalised feasibility problem with tr(X) = 1: one in the entry-oracle model at Õ(s^2(√m ε^(-10) + √n ε^(-12))), which the authors call an optimal dependence in terms of m and n and a quadratic improvement over previous quantum algorithms when m is about n, and one in a fully quantum input model where the matrices are given as quantum states, at Õ(√m + poly(r)) · poly(log m, log n, B, ε^(-1)) with B a bound on the trace norm of all input matrices. Read its section 1 before quoting either: converting a general primal with tr(X) ≤ R into the trace-one form changes ε to ε/R, and to ε divided by R times the dual bound for a strictly feasible solution, which is the substitution the same section applies when it restates Brandão and Svore's cost as Õ(√(mn) s^2 (R R-tilde/ε)^32). Its main technical contribution is a quantum Gibbs state sampler for low-rank Hamiltonians given quantum states encoding those Hamiltonians, with a poly-logarithmic dependence on dimension — the PDF abstract carries the "given quantum states" qualifier that the arXiv metadata abstract drops. Consult it also for Remark D.7, which is where the Zoo's O(√m log m · poly(log n, r, ε^(-1))) comes from, under the quantum-input oracles with B collapsed to r by the eigen-decomposition; for Remark 1.5, where the authors warn that the poly-dependence on 1/ε makes it nontrivial to get speed-ups on combinatorial SDPs such as Max-Cut; and for the input-model caution the Zoo's superpolynomial remark rests on, that the poly-logarithmic dependence on n suggests exponential speed-ups for some SDP instances but that one has to be cautious because the input model is inherently quantum and so incomparable to classical SDP solvers.
Quantum algorithms for Gibbs sampling and hitting-time estimation
Anirban Narayan Chowdhury, Rolando D. Somma · 2016
One of the two Gibbs-sampling references the Zoo names as the ingredient this solver is built on. Its first algorithm prepares the thermal Gibbs state of a quantum system in time almost linear in √(N β / Z) and polynomial in log(1/ε), with N the Hilbert space dimension, β the inverse temperature, Z the partition function and ε the precision of the output state, which the abstract describes as an exponential improvement in the dependence on 1/ε and a quadratic improvement in the dependence on β over known quantum algorithms for the problem. Van Apeldoorn et al. note that this sampler assumes query access to the entries of the square root of the Hamiltonian rather than to the Hamiltonian itself, which is why their own solver does not simply adopt it.
Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, Chunhao Wang · 2019
The dequantization result the Zoo cites as delineating where a superpolynomial speedup is possible. Its Problem 6.24 is the same trace-one SDP feasibility problem Brandão, Kalev et al. solve, and its Corollary 6.25 solves it classically, given sampling and query access to the constraint matrices, at a cost polylogarithmic in n; the authors state their algorithm both solves a more general problem than the previous quantum-inspired SDP solver and greatly improves its runtime. Consult it for the scope of the claim: the framework is presented as compelling evidence that in the corresponding QRAM data structure input model quantum singular value transformation does not yield exponential quantum speedups, and the stated SDP cost is linear in m and carries exponents up to 22 in the Frobenius-norm bound F and up to 46 in 1/ε. Its section 6.8 also names van Apeldoorn and Gilyén, not any of the Zoo's three references, as the paper with the current best runtime for SDP solving.

Verification

Attested & literature

Peer-reviewed paper

Method: Curation only. The problem statement was recorded from the literature; the speedup class is checked against the record's own primary paper, which states it; the primary reference's title, authors and submission year were read from its arXiv abs page; the complexity claim was taken from a clause of that paper's abstract (Abstract of arXiv:1609.05537 (inline TeX rendered into plain text: the fraction exponents are written n^(1/2) m^(1/2), and "a upper bounds" is the abstract's own wording): "It has worst-case running time n^(1/2) m^(1/2) s^2 poly(log(n), log(m), R, r, 1/δ), with n and s the dimension and row-sparsity of the input matrices, respectively, m the number of constraints, δ the accuracy of the solution, and R, r a upper bounds on the size of the optimal primal and dual solutions", and "We prove the algorithm cannot be substantially improved (in terms of n and m) giving a Ω(n^(1/2)+m^(1/2)) quantum lower bound for solving semidefinite programs with constant s, R, r and δ". The same paper, Corollary 5 (page 8 of v5): "Using the Gibbs Sampler from Ref. [13], Algorithm 3 runs in time Õ(n^(1/2) m^(1/2) s^2 R^32/δ^18)"; its section 2.2: "Our algorithm will only work for SDPs for which b_i ≥ 1 for all i ∈ [m]", "We will also assume that α ≥ 1", and Lemma 2, which supplies "a δ-optimal solution" of the general SDP "given the ability to sample from a (δ/r)-optimal solution" of an SDP "with dimension n + 1, m + 1 variables and size parameter 2R + 1" in which b_i ≥ 1. The scoping of that corollary is arXiv:1705.01843 section 1.3: "Using these ideas, Brandão and Svore obtain a quantum SDP-solver of complexity Õ(√(mn) s^2 R^32/δ^18), with multiplicative error 1 ± δ for the special case where b_j ≥ 1 for all j ∈ [m], and OPT ≥ 1 … They describe a reduction to transform a general SDP of the form (1) to this special case, but that reduction significantly worsens the dependence of the complexity on the parameters R, r, and δ". Section 1.4.1 of arXiv:1705.01843, headed "Improved quantum SDP-solver": "These modifications both simplify and speed up the quantum SDP-solver, resulting in complexity Õ(√(mn) s^2 (Rr/ε)^8)", "The dependence on m, n, and s is the same as in Brandão-Svore, but our dependence on R, r, and 1/ε is substantially better", "These trade-offs suggest we should actually think of Rr/ε as one parameter of the primal-dual pair of SDPs, not three separate parameters", and "For the special case of LPs, we can improve the runtime to Õ(√(mn)(Rr/ε)^5)"; the same paper's section 1.2 defines those parameters — "Let R be an upper bound on the trace of an optimal X of the primal, r be an upper bound on the sum of entries of an optimal y for the dual" — and its footnote 3 states "The Õ(·) notation hides polylogarithmic factors in all parameters". Abstract of arXiv:1710.02581: "We consider SDP instances with m constraint matrices, each of dimension n, rank at most r, and sparsity s", "We show that it has run time Õ(s^2(√m ε^(-10)+√n ε^(-12))), with ε the error of the solution. This gives an optimal dependence in terms of m, n and quadratic improvement over previous quantum algorithms when m≈n", and "We show that its run time is Õ(√m+poly(r))·poly(log m, log n, B, ε^(-1)), with B an upper bound on the trace-norm of all input matrices. In particular the complexity depends only poly-logarithmically in n and polynomially in r". Its problem (1.1) carries "Tr(A_i X) ≤ a_i + ε ∀ i ∈ [m]; X ⪰ 0; Tr[X] = 1", and the conversion is stated in the same section 1: "for general feasible solution X ⪰ 0 with width bound Tr(X) ≤ R, there is a procedure to derive an equivalent SDP feasibility instance with variable X-hat s.t. Tr(X-hat) = 1. Note, however, the change of ε to ε/R in this conversion. Also note one can use an approximate feasibility solver to find a strictly feasible solution, by changing ε to ε/R R-tilde (see Lemma 18 of Ref. [9])" — R-tilde is that paper's R with a tilde and X-hat its X with a hat, both rendered here as plain text. The same section restates the primary paper's cost under that substitution: "giving a quantum algorithm with worst-case running time Õ(√(mn) s^2 (R R-tilde/ε)^32) … and R, R-tilde upper bounds on the norm of the optimal primal and dual solutions". The Zoo's composite figure is that paper's Remark D.7: "If we assume this decomposition to be the eigen-decomposition … then by the low-rank assumption and −I ⪯ A_j ⪯ I, Tr[A_j^+] + Tr[A_j^−] ≤ r. In this case, Corollary 5 takes at most √m · poly(log m, log n, r, ε^(-1)) quantum gates and queries to Oracle D.1, Oracle D.2, and Oracle D.3" — where Corollary 5 is introduced as "the following complexity result for solving SDPs under the quantum input model", and the same paper notes "our quantum SDP solver in Corollary 9 does not assume the sparsity of A_i's, which are crucial for the quantum SDP solvers with the plain model". The Zoo's own wording (LaTeX rendered into plain text) is: "quantum algorithms are now known that can approximately solve semidefinite programs to within ± ε in time O(√m log m · poly(log n, r, ε^(-1))), where r is the rank of the semidefinite program. This constitutes a quadratic speedup over the fastest classical algorithms when r is small compared to n".). No circuit was constructed, simulated or run.
Result: Pass · the record's problem, speedup class and primary reference agree with the two sources named above.
Caveat: This is a literature record. No semidefinite program was solved here, no circuit was built, compiled, simulated or run, and no instance of C, A_j or b_j was constructed. Every figure above is an asymptotic worst-case bound with no constants, and all three papers state theirs in Õ notation, which van Apeldoorn et al. define as hiding polylogarithmic factors in all parameters, so none of them costs a named SDP instance. The bounds are also not interchangeable, and dropping a parameter changes which regime the speedup exists in. Three drops in particular reverse the reading: the r in Brandão and Svore and in van Apeldoorn et al. is a bound on the size of the optimal dual solution, while the r in Brandão, Kalev, Li, Lin, Svore and Wu and in the Zoo's composite figure is the rank of the constraint matrices; the ε^(-10) and ε^(-12) exponents are stated for a trace-one normalisation whose conversion from a general SDP changes ε to ε/R, so they are not a bound free of the size parameters; and the Zoo's headline runtime is a fully-quantum-input-model bound, not an entry-oracle one. The authors are explicit about where their own speedups do and do not live: van Apeldoorn et al. state that the Brandão-Svore algorithm provides a speed-up only in regimes where R, r, s and 1/ε are fairly small compared to mn, adding that finding good examples of SDPs in such regimes is an open problem, and Brandão et al. say of their own m-and-n-optimal solver that it is nontrivial to obtain quantum speed-ups by directly applying it to SDP instances from classical combinatorial problems, the obstacle being the poly-dependence on 1/ε, since for interesting instances such as Max-Cut 1/ε is linear in n — which is the class of application the problem statement above advertises. The classical side is the fastest algorithms currently known, as the Zoo puts it, not a proven lower bound on classical SDP solving. On the quantum side there are real limits: van Apeldoorn et al. prove that in the worst case the complexity of every quantum LP-solver, and hence of every quantum SDP-solver, has to scale linearly with mn when m is about n, the same as classical, and their section 3, headed "Downside of this method: general oracles are restrictive", shows the multiplicative-weights approach fails for families of SDPs with a lot of symmetry. The superpolynomial reading the Zoo mentions belongs only to the fully quantum input model, and the authors who report it warn to be cautious, because that input model is inherently quantum and therefore incomparable to classical SDP solvers. The dequantization is a genuine limit rather than a footnote: Chia, Gilyén, Li, Lin, Tang and Wang solve the same trace-one SDP feasibility problem classically, under sampling and query access to the input matrices, at a cost polylogarithmic in n, and present their framework as compelling evidence that in the corresponding QRAM data structure input model quantum singular value transformation does not yield exponential quantum speedups. That result is scoped to that input model; its stated cost is linear in m where the quantum bounds are √m, and carries exponents up to 22 in the Frobenius-norm bound and up to 46 in 1/ε, so it bounds the asymptotic separation without being a practical classical solver. Finally, the three papers the Zoo cites are not the end of the state of the art: Brandão et al. record that a later independent work of van Apeldoorn and Gilyén improved their entry-oracle bound to Õ(s(√m/ε^4 + √n/ε^5)), in a quantum operator model they call stronger than the plain one, and their quantum-input bound to Õ(B√m/ε^4 + B^3.5/ε^7.5), and Chia et al. call that work the paper with the current best runtime for SDP solving. It lies outside this row's references and outside this record.

Source

Quantum Speed-ups for Semidefinite Programming ↗

Kind: curated reference
Reviewed by: Leona Quantum curation pass
License: Citation metadata only; source publication terms apply

semidefinite programmingconvex optimizationmatrix multiplicative weightsgibbs samplingdequantization

Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.