Pith. sign in

REVIEW 3 major objections 3 minor 45 references

Quantum and classical algorithms for SOCP based on the multiplicative weights update method

T0 review · 3 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A multiplicative-weights method solves second-order cone programs with $\widetilde{O}(\sqrt{r}\gamma^5 + \sqrt{m}\gamma^4)$ quantum query complexity, nearly matching linear programs and beating the naive SDP embedding.

desk verdict Genuinely new end-to-end MW-based algorithms for general SOCPs, with honest complexity statements and a real speedup claim, but the advertised quantum query count leans on a cheap-QRAM assumption and one degenerate first iteration needs a patch. read the letter →

arxiv 2507.14127 v2 pith:ZQ4CUCA4 submitted 2025-07-18 quant-ph

M. Isabel Franco Garrido , Alexander M. Dalzell , Sam McArdle This is my paper
classification quant-ph MSC 90C2590C2268Q12
keywords second-orderconeprogrammingmultiplicativeweightsupdatequantumalgorithmsGibbssamplingsingularvaluetransformationsample-and-querymodelJordanalgebraconvexoptimization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Second-order cone programs (SOCPs) are optimization problems that sit between linear programs and semidefinite programs: the variables form vectors constrained to a product of 'ice-cream' cones, each of which adds one nonlinear direction to a linear program. This paper claims that SOCPs can be solved approximately by a multiplicative-weights method whose quantum query complexity, $\widetilde{O}(\sqrt{r}\,\gamma^5 + \sqrt{m}\,\gamma^4)$ for $m$ constraints over $n$ variables grouped into $r$ cones, is nearly the same as the cost of solving linear programs, and its classical companion runs in $\widetilde{O}(n\gamma^4 + m\gamma^6)$ samples and queries in the sample-and-query model (with $\gamma = R\widetilde{R}/\epsilon$ the scale-invariant inverse-precision parameter). The structural insight is that each second-order cone has rank two, so the Gibbs-like state at the heart of the multiplicative-weights iteration is pure, not mixed; this makes the SOCP-specific algorithms cheaper than embedding the SOCP into a semidefinite program, which would cost $\widetilde{O}(\gamma^4(n + \gamma\sqrt{n} + \sqrt{m}))$. If the complexity claims are right, large SOCPs from finance, control, and power-systems optimization could be solved to moderate precision with costs that scale with $\sqrt{r} + \sqrt{m}$ quantumly rather than with the full problem size, and the paper provides the first end-to-end oracle implementations making these bounds concrete.

What carries the argument

The central object is the Euclidean Jordan algebra of the second-order cone, whose defining gadget is the Arrowhead matrix: a cone vector $v^{(k)} = (v_0, \vec v)$ maps to $\operatorname{Arw}(v^{(k)}) = \begin{pmatrix} v_0 & \vec v^{\top} \\ \vec v & v_0 I \end{pmatrix}$, a matrix that is positive semidefinite exactly when $v^{(k)}$ lies in the cone. Every cone vector splits into two eigen-components $v^{(k)} = \lambda_+ c_+ + \lambda_- c_-$, so the multiplicative-weights candidate $x \propto e^{-A^{\top} y}$—an exponential computed in the Jordan algebra—is represented by a pure two-level state per cone, and the whole candidate becomes the 'cone-index Gibbs state' $|\sqrt{2x}\rangle = \sum_k \sqrt{Z^{(k)}/Z}\,|k\rangle|\sqrt{2p^{(k)}}\rangle$ whose preparation dominates the cost. The outer loop is the standard multiplicative-weights update (raise the weight of a violated constraint by $\theta/6$), needing only $O(\log r/\theta^2)$ iterations because the potential function $\Phi(t) = \operatorname{Tr}(e^{\delta \sum M^{(\tau)}})$ shrinks multiplicatively; the Golden–Thompson inequality for Jordan algebras supplies the key bound. The violated-constraint oracle is split into a two-step procedure whose costs add: the cone-index Gibbs sampler, built quantumly from minimum-finding on the Arrowhead block-encoding followed by a QSVT polynomial approximation of the exponential, and the sampled violated-constraint search, built from a block-encoding of the violation matrix $\hat V$ filtered through a QSVT Heaviside step and boosted by fixed-point amplitude amplification.

What would settle it

Count, on a fixed instance family (say $r = 2^k$ identical second-order cones with a single linear constraint), the actual number of data-oracle queries the two-step violated-constraint oracle uses per iteration. The paper predicts $\widetilde{O}(\sqrt{r}/\theta^2)$ quantum queries and $\widetilde{O}(n/\theta^4)$ classical samples-and-queries; measured growth beyond these powers of $r$ and $n$, ignoring log factors, would refute the complexity claims. A second, cheaper check targets the load-bearing access assumption directly: implement the row-prep and state-prep oracles on a concrete QRAM architecture and measure their circuit depth—if it grows polynomially in $m$ or $n$ rather than polylogarithmically, the end-to-end quantum gate complexity no longer exhibits the advertised near-LP speedup.

Watch

Extended reading notes

Core claim

The central claim is that the multiplicative-weights framework, previously applied to linear and semidefinite programs, carries over to second-order cone programs with near-linear-program cost. The paper reduces approximate SOCP optimization to a sequence of feasibility checks, each solved by iterating a sparse nonnegative weight vector $y$ for $T = O(\log r / \theta^2)$ steps; every step queries a violated-constraint oracle that either certifies all constraints are satisfied or returns a constraint violated by at least $\theta$. The oracle is implemented in two additive-cost steps: a cone-index Gibbs sampler that draws cone indices $k$ with probability proportional to $Z^{(k)} = \operatorname{Tr}(e^{-A^{(k)\top}y})$, and a sampled violated-constraint search that estimates each constraint's violation from those samples. Because the Jordan-algebra exponential of a cone vector decomposes into just two eigen-components, the candidate solution's 'Gibbs state' is a pure state, so the quantum implementation prepares it via quantum singular value transformation on a block-encoding of the Arrowhead matrix at cost $\widetilde{O}(\sqrt{r}\,\beta)$ per iteration; adding the cost of finding a violated constraint among $m$ candidates gives the total quantum query complexity $\widetilde{O}(\sqrt{r}\,\gamma^5 + \sqrt{m}\,\gamma^4)$, with $\gamma = R\widetilde{R}/\epsilon$. The classical implementation computes the cone weights by exact sparse matrix-vector products, giving $\widetilde{O}(n\gamma^4 + m\gamma^6)$, and the authors present the pair of results as evidence that SOCP's intermediate expressiveness carries an intermediate, additive query cost.

Load-bearing premise

The advertised quantum query count is only the number of calls to data oracles whose circuits are assumed to be very shallow (polylogarithmic depth), which the paper itself equates to assuming cheap quantum random-access memory; if building that memory is expensive, the end-to-end quantum gate count grows by that overhead.

Editorial extensions

If this is right

  • In the dense regime $r = \Theta(n)$, the quantum bound $\widetilde{O}(\sqrt{r}\gamma^5 + \sqrt{m}\gamma^4)$ is a near-quadratic improvement over the classical $\widetilde{O}(n\gamma^4 + m\gamma^6)$, and the speedup is even larger when $r \ll n$.
  • Embedding an SOCP into an SDP is dominated for large $n$: the naive bound $\widetilde{O}(\gamma^4(n + \gamma\sqrt{n} + \sqrt{m}))$ is beaten whenever $n \gg \sqrt{r}$, so cone structure should be exploited directly rather than through the arrowhead-matrix SDP reformulation.
  • The multiplicative-weights route becomes competitive with interior-point methods for large, low-precision instances: IPM complexity grows superlinearly in problem size (roughly $O(\sqrt{r}\,n^{\omega})$ for SOCP), while here the number of iterations depends only logarithmically on $r$ and polynomially on $\gamma$.
  • Because Lemma 1 converts any feasibility oracle into an $\epsilon$-approximate optimizer with $\widetilde{O}(\log(R/\epsilon))$ oracle calls, the query bounds transfer from decision problems to full optimization without changing the $\gamma$ scaling.
  • In the sample-and-query access model, the classical algorithm's $\widetilde{O}(n\gamma^4 + m\gamma^6)$ cost means feasibility can be certified without writing down the full $m \times n$ instance, which the authors note is the reason sublinear classical complexity is achievable in this model.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If quantum random-access memory turns out to be expensive, the end-to-end gate count for implementing the row-prep and state-prep oracles would add a polynomial-in-size overhead per query, so the near-LP speedup would hold at the query level but not necessarily at the physical-gate level; the paper's own 'essentially equivalent to an assumption of cheap QRAM' remark marks this as the point to watc
  • The reduction of SOCP solving to preparing a pure per-cone Gibbs state is the paper's most reusable idea: any faster preparation of $|\sqrt{2x}\rangle$—for instance, when the two Jordan-frame eigenvalues are well separated so the state thermalizes faster—would directly lower the $\widetilde{O}(\sqrt{r})$ term, a route to larger speedups the paper explicitly leaves open.
  • The classical algorithm's $\widetilde{O}(n)$-dependence comes from computing each cone weight $Z^{(k)}$ exactly, and the paper explains why a direct sampling estimate needs precision $1/r$ per cone; a quantum-inspired estimator that reaches the needed precision in $\operatorname{polylog}$ time would close the gap to $\widetilde{O}(r + m)$ and determine how much of the quantum advantage is genuine
  • Because the two-step oracle decomposition keeps the $r$-dependence and $m$-dependence additive, the same design should transfer to other low-rank conic programs, and with care to the full symmetric-cone case, suggesting the framework is a template for conic optimization rather than a one-off SOCP construction.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper presents multiplicative-weights (MW) based classical and quantum algorithms for approximately solving second-order cone programs (SOCPs). The quantum algorithm implements a two-step violated-constraint oracle: a cone-index Gibbs sampler and a sampled violated-constraint search, both built from block-encodings, QSVT, and amplitude amplification. The claimed quantum query complexity is O~(sqrt(r) gamma^5 + sqrt(m) gamma^4), and the classical sample-and-query complexity is O~(n gamma^4 + m gamma^6), where gamma = R R~ / epsilon. The paper includes a reduction from general SOCPs to a unit-trace feasibility problem, a convergence proof for the MW feasibility algorithm, and explicit circuit constructions in Appendix A.

Significance. If the main claims are correct, this is a significant contribution: it specializes the MW framework to SOCPs in a way that nearly matches the query complexity of linear programs and improves on the naive SOCP-to-SDP embedding. The paper is largely self-contained, uses established tools (QSVT, Golden-Thompson for Euclidean Jordan algebras, minimum finding), and provides explicit oracles and circuits. The advertised speedup is, however, stated in a query model that relies on cheap QRAM for the state-preparation oracles Oy and OT, a caveat the paper acknowledges in Section 2.3.2. More importantly, the convergence proof of the central MW feasibility algorithm contains a normalization error that undermines the claimed iteration count; this must be corrected before the complexity statements can be accepted.

major comments (3)
  1. [Theorem 1 (Section 3.3), equations (3.43)-(3.44)] The proof of Theorem 1 uses the identity e^T p = 1 for unit-trace vectors p, but with the trace defined as Tr(v) = 2 v_0 in Section 2.1, the correct identity is e^T p = 1/2. As a result, inequality (3.44) is false: Tr(M(t) o Q) = 1/2 - (A Q)_j, and feasibility of Q only gives (A Q)_j <= b_j, hence Tr(M(t) o Q) >= 1/2 - b_j, not 1 - b_j. Equation (3.43) is a valid but loose upper bound for the same reason. If the correct inequalities are used together with Proposition 1 (which applies with delta = theta/3 given the definition of P(t) in (3.41)), the chain (3.45)-(3.47) does not yield T <= 36 log(2r)/theta^2; a direct rederivation gives T = O(log r / theta^3). Since the iteration count T is used in Corollaries 1 and 2, the advertised quantum complexity exponents gamma^5 and gamma^4 are not established by the proof as written.
  2. [Lemma 1 (Section 2.2), last paragraph of proof] The probability accounting in the reduction from SOCP optimization to feasibility is incomplete. After the binary search, the proof runs the oracle O_theta one final time to obtain the vector y, but O_theta has failure probability at most 1/3. The binary search steps are boosted to failure probability 1/3 overall (via zeta = 1/(3 T_bs)), so the combined success probability of the binary search and the final oracle call is at most (2/3)*(2/3) = 4/9, not at least 2/3 as stated. The final call must also be boosted (e.g., to failure probability 1/6) or the failure budget zeta must be redistributed, which only changes the O-tilde(log(R/theta)) call count by a constant.
  3. [Section 4.1, Lemma 5 and Corollary 3] The quantum Gibbs sampler construction assumes a nonzero norm beta = ||y||_1. In the first iteration of Algorithm 1, y = 0, so the (2 beta, 0)-block-encoding of Arw(A^T y) in (4.5) is degenerate (division by zero), and the subsequent minimum-finding and QSVT steps in Lemma 5 are undefined. Moreover, for 0 < beta < 1/2, the claim that the shifted eigenvalues lie in [0,1] is false: with eta_lambda = 1/2, the upper bound is (2 beta + 2 eta_lambda)/(4 beta) > 1, violating the QSVT polynomial domain. The paper needs to handle the small-beta regime separately, either by special-casing beta = 0 (where the cone-index distribution is uniform and the desired state can be prepared directly) or by replacing beta with max(beta,1) in the normalization. This is load-bearing because the first oracle call has beta = 0 and still requires data queries to find a violated constraint, so the claimed query bound for that call is not captured by the formula in Theorem 3.
minor comments (3)
  1. [Lemma 5 (Section 4.1)] The trace-distance bound is stated as 32 sqrt(2r) delta_exp log(1/omega_AA) + omega_AA + sqrt(2 omega_AA), but the corresponding bound in Lemma 18 contains a square root of the approximation error, i.e., 32 sqrt(2r) sqrt(delta_exp) log(1/omega_AA). The chosen value of delta_exp still makes the final bound work, so this appears to be a typographical error.
  2. [Lemma 12 (Section 5.2)] The text says that computing u^(k_h) = (A^(k_h))^T y for each h = 0, ..., T'-1 costs a total of O(n s), but a naive per-sample computation would cost O(T' n s). The O(n s) bound is only valid if the computation is memoized across repeated cone indices; this should be stated explicitly.
  3. [Section 2.3.2] The caveat that the complexity statements assume cheap QRAM for the oracles Oy and OT is important and should be restated prominently in the abstract or introduction, since the advertised speedup relative to classical algorithms depends on this access-model assumption.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the SOCP MW derivation is self-contained and external benchmark tools carry the load.

full rationale

The paper's central complexity statements (Theorem 3 and Corollaries 1–2) count coherent queries to specified oracles (OR, Ob, Oy, OT) and are derived from explicit subroutine constructions, not from fitting a parameter to a subset of data and renaming it a prediction. The MW convergence proof (Theorem 1) is proved in-paper using the Golden–Thompson inequality in Euclidean Jordan algebras cited to external work [TWK21] and the standard MW potential framework from [Kal07]; neither is the authors' own prior result. The quantum subroutines rely on QSVT [GSLW19], minimum finding [LT20], and polynomial approximation lemmas [vAG19b], all external, machine-checkable-style results. The block-encodings of Arrowhead matrices are constructed explicitly in Appendix A from the stated access oracles. The only self-citations are [DCS+23], used as background comparison for quantum interior-point SOCP solvers, and [DGH+25], used in the remark that implementing Oy/OT with polylog-depth circuits is 'essentially equivalent to an assumption of cheap QRAM.' That remark is a transparent limitation of the end-to-end gate count, not a load-bearing circular step: the advertised complexity is a query complexity, and the cheap-QRAM dependence is explicitly stated as an assumption. No step reduces, by construction or by self-citation, to its own input. The skeptical concern about QRAM costs is a resource-model caveat, not circularity, and the paper acknowledges it honestly.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The central claims rest on standard quantum algorithmic toolkit (QSVT, amplitude amplification, minimum finding), a cited Jordan-algebra Golden-Thompson inequality, and standard SOCP assumptions (normalization, trace bounds, strong duality, promise gap). No free parameters are fit to data; all constants (T', η, ζ, etc.) are set analytically. No new physical entities are introduced.

assumptions (8)
  • standard math Golden-Thompson inequality holds in the Euclidean Jordan algebra of the second-order cone (Tr(e^{m+q}) ≤ Tr(e^m ∘ e^q))
    Used to upper-bound the potential function in Proposition 1 and Theorem 1; cited from [TWK21].
  • standard math QSVT polynomial transformation allows implementing polynomial functions of block-encoded Hermitian matrices with precision guarantees
    Core quantum subroutine used to exponentiate Arrowhead matrices and apply Heaviside/amplitude-amplification polynomials; cited from [GSLW19] and [vAG19a].
  • standard math Fixed-point amplitude amplification can boost success probability of an imperfect block-encoding (Lemma 18)
    Used in Lemma 5 and Lemma 10 to prepare Gibbs states and find violated constraints; cited from [GSLW19].
  • standard math Minimum eigenvalue of a Hamiltonian can be estimated with query complexity O(β/(ν η)) given a block-encoding and overlap guarantee ν
    Used to compute λ_min of Arw(u) in Section 4.1; cited from [LT20, Theorem 8].
  • domain assumption Strong duality holds for the SOCP instance (primal and dual optimal objective values coincide)
    Stated after Definition 7; required for the reduction of optimization to feasibility in Lemma 1.
  • domain assumption The SOCP satisfies normalization conditions and R-trace / R~-dual-trace constraints with known R, R~
    Definitions 8-10; needed to define γ = R R~ / ε and to make the oracle estimates bounded.
  • domain assumption The feasibility problem satisfies the promise that either S0 is nonempty or Sθ is empty
    Definition 11; the MW feasibility algorithm and the reduction rely on this promise to produce correct outputs with high probability.
  • domain assumption Quantum access model with row-prep and state-prep oracles (Oracles 1-3) implementable with polylog-depth circuits, i.e., cheap QRAM
    Section 2.3.2; the query complexity is stated in terms of these oracles, and the end-to-end gate complexity assumes they are cheap.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum and classical algorithms for SOCP based on the multiplicative weights update method." pith.science (2026). https://pith.science/paper/ZQ4CUCA4

@misc{pith2026250714127,
  author       = {Pith},
  title        = {Pith review of: Quantum and classical algorithms for SOCP based on the multiplicative weights update method},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZQ4CUCA4}},
  note         = {Machine review of arXiv:2507.14127}
}
abstract

We give classical and quantum algorithms for approximately solving second-order cone programs (SOCPs) based on the multiplicative weights (MW) update method. Our approach follows the MW framework previously applied to semidefinite programs (SDPs), of which SOCP is a special case. We show that the additional structure of SOCPs can be exploited to give better runtime with SOCP-specific algorithms. For an SOCP with $m$ linear constraints over $n$ variables partitioned into $r \leq n$ second-order cones, our quantum algorithm requires $\widetilde{O}(\sqrt{r}\gamma^5 + \sqrt{m}\gamma^4)$ (coherent) queries to the underlying data defining the instance, where $\gamma$ is a scale-invariant parameter proportional to the inverse precision. This nearly matches the complexity of solving linear programs (LPs), which are a less expressive subset of SOCP. It also outperforms (especially if $n \gg r$) the naive approach that applies existing SDP algorithms onto SOCPs, which has complexity $\widetilde{O}(\gamma^{4}(n + \gamma \sqrt{n} + \sqrt{m}))$. Our classical algorithm for SOCP has complexity $\widetilde{O}(n\gamma^4 + m \gamma^6)$ in the sample-and-query model.

Figures

Figures reproduced from arXiv: 2507.14127 by the authors.

Figure 1
Figure 1. Summary of the subroutines in our analysis that are used to approximately solve an [PITH_FULL_IMAGE:figures/full_fig_p018_1.png] view at source ↗
Figure 2
Figure 2. Given a point y ∈ R m, which implicitly defines (x (0); . . . ; x (r−1)) via eq. (3.2), each constraint j ∈ [m] is violated by an amount Pr−1 k=0 A (k) j,: x (k) − bj (negative numbers indicate the constraint is satisfied). The set V>θ contains values of j for which the violation is more than θ, and the set Vθ contains values of j the violation is in the interval (θ/2, θ]. a point with Ω(θ) violation using only prec… view at source ↗
Figure 4
Figure 4. fig. 4. We can divide the block-encoding of the arrowhead matrix in two parts, the diagonal matrix [PITH_FULL_IMAGE:figures/full_fig_p046_4.png] view at source ↗
Figures from the paper (4 more)
Figure 3
Figure 3. Figure 3: Schematic LCU circuit. Since Uod and Ud have a common structure, they need not be performed sequentially and independently. A diagram of the circuit is shown in fig. 3. |0⟩ H H ⟨0| Row: |¯0⟩ Oy O † y ⟨¯0| Cone: |k⟩ ⟨k| Column: |i⟩ OR O † R ⟨i ′ | Flag: |0⟩ ⟨0| Control:…
Figure 4
Figure 4. Figure 4: Detailed LCU circuit. 47 [PITH_FULL_IMAGE:figures/full_fig_p047_4.png]
Figure 5
Figure 5. Figure 5: Diagonal block-encoding. |¯0⟩ here represents top to bottom |0 log2( ¯m) ⟩ and |0 log2(¯n) ⟩. □ is here a simplification for □ ⊗log2(m) , □ ⊗log2(r) Proof. Up to the OR gate, we see the circuit behaves as the following map |¯0, k, i, 0, 0, ¯0⟩ 7→   X j,˜i A (k) j˜i r…
Figure 6
Figure 6. Figure 6: Off-diagonal elements block-encoding. Top to bottom, the first [PITH_FULL_IMAGE:figures/full_fig_p050_6.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

45 extracted references · 42 canonical work pages

  1. [1]

    Second-order cone programming

    Farid Alizadeh and Donald Goldfarb. Second-order cone programming. Mathematical programming , 95(1):3--51, 2003

    work page 2003

  2. [2]

    A computationally efficient learning-based model predictive control for multirotors under aerodynamic disturbances

    Babak Akbari and Melissa Greeff. A computationally efficient learning-based model predictive control for multirotors under aerodynamic disturbances. In 2024 International Conference on Unmanned Aircraft Systems (ICUAS) , page 185–192. IEEE, June 2024

    work page 2024

  3. [3]

    Quantum speedups for linear programming via interior point methods, 2024

    Simon Apers and Sander Gribling. Quantum speedups for linear programming via interior point methods, 2024

    work page 2024

  4. [4]

    A quantum central path algorithm for linear optimization, 2024

    Brandon Augustino, Jiaqi Leng, Giacomo Nannicini, Tamás Terlaky, and Xiaodi Wu. A quantum central path algorithm for linear optimization, 2024

    work page 2024

  5. [5]

    DSOS and SDSOS optimization: More tractable alternatives to sum of squares and semidefinite optimization

    Amir Ali Ahmadi and Anirudha Majumdar. DSOS and SDSOS optimization: More tractable alternatives to sum of squares and semidefinite optimization. SIAM Journal on Applied Algebra and Geometry , 3(2):193–230, January 2019

    work page 2019

  6. [6]

    Fernando G. S. L. Brand\ a o, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu. Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning . In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming ...

    work page 2019

  7. [7]

    Brandao and Krysta M

    Fernando G.S.L. Brandao and Krysta M. Svore. Quantum speed-ups for solving semidefinite programs. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , page 415–426. IEEE, October 2017

    work page 2017

  8. [8]

    The power of block-encoded matrix powers: Improved regression techniques via faster hamiltonian simulation

    Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The power of block-encoded matrix powers: Improved regression techniques via faster hamiltonian simulation. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) . Schloss Dagstuhl – Leibniz-Zentrum f\" u r Informatik, 2019

    work page 2019

Show all 45 references
  1. [9]

    Quantum-inspired sublinear algorithm for solving low-rank semidefinite programming

    Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang. Quantum-inspired sublinear algorithm for solving low-rank semidefinite programming. In MFCS 2020 . Schloss Dagstuhl – Leibniz-Zentrum f\" u r Informatik, 2020

    2020

  2. [10]

    Two-dimensional beampattern synthesis for polarized smart antenna array and its sparse array optimization

    Zhikun Chen, Tao Li, Dongliang Peng, and Kang Du. Two-dimensional beampattern synthesis for polarized smart antenna array and its sparse array optimization. International Journal of Antennas and Propagation , 2020:1–13, June 2020

    2020

  3. [11]

    Multiplicative updates for online convex optimization over symmetric cones

    Ilayda Canyakmaz, Wayne Lin, Georgios Piliouras, and Antonios Varvitsiotis. Multiplicative updates for online convex optimization over symmetric cones. ArXiv , abs/2307.03136, 2023

    2023 arXiv

  4. [12]

    Cohen, Yin Tat Lee, and Zhao Song

    Michael B. Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. J. ACM , 68(1), January 2021

    2021

  5. [13]

    Dalzell, B

    Alexander M. Dalzell, B. David Clader, Grant Salton, Mario Berta, Cedric Yen-Yu Lin, David A. Bader, Nikitas Stamatopoulos, Martin J. A. Schuetz, Fernando G. S. L. Brandão, Helmut G. Katzgraber, and William J. Zeng. End-to-end resource analysis for quantum interior-point metho...

    2023

  6. [14]

    A distillation-teleportation protocol for fault-tolerant QRAM

    Alexander M Dalzell, Andr \'a s Gily \'e n, Connor T Hann, Sam McArdle, Grant Salton, Quynh T Nguyen, Aleksander Kubica, and Fernando GSL Brand \ a o. A distillation-teleportation protocol for fault-tolerant QRAM . arXiv preprint arXiv:2505.20265 , 2025

    2025 arXiv

  7. [15]

    An efficient support vector machine learning method with second-order cone programming for large-scale problems

    Rameswar Debnath, Masakazu Muramatsu, and Haruhisa Takahashi. An efficient support vector machine learning method with second-order cone programming for large-scale problems. Applied Intelligence , 23(3):219–239, December 2005

    2005

  8. [16]

    Computing a task-dependent grasp metric using second-order cone programs

    Amin Fakhari, Aditya Patankar, Jiayin Xie, and Nilanjan Chakraborty. Computing a task-dependent grasp metric using second-order cone programs. In 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) , page 4009–4016. IEEE, September 2021

    2021

  9. [17]

    Risk return trade-off in relaxed risk parity portfolio optimization

    Vaughn Gambeta and Roy Kwon. Risk return trade-off in relaxed risk parity portfolio optimization. Journal of Risk and Financial Management , 13(10):237, October 2020

    2020

  10. [18]

    Nonlinear transformation of complex amplitudes via quantum singular value transformation

    Naixu Guo, Kosuke Mitarai, and Keisuke Fujii. Nonlinear transformation of complex amplitudes via quantum singular value transformation. Phys. Rev. Res. , 6:043227, Dec 2024

    2024

  11. [19]

    Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

    András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , STOC ’19. ACM, June 2019

    2019

  12. [20]

    Sequential measurements, disturbance and property testing

    Aram W Harrow, Cedric Yen-Yu Lin, and Ashley Montanaro. Sequential measurements, disturbance and property testing. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1598--1611. SIAM, 2017

    2017

  13. [21]

    A SOCP -based ACOPF for operational scheduling of three-phase unbalanced distribution systems and coordination of PV smart inverters

    Mingyue He, Zahra Soltani, Mohammad Ghaljehei, Masoud Esmaili, Shanshan Ma, Mengxi Chen, Mojdeh Khorsand, Raja Ayyanar, and Vijay Vittal. A SOCP -based ACOPF for operational scheduling of three-phase unbalanced distribution systems and coordination of PV smart inverters. IEEE ...

    2024

  14. [22]

    Second order cone relaxations for quantum Max Cut , 11 2024

    Felix Huber, Kevin Thompson, Ojas Parekh, and Sevag Gharibian. Second order cone relaxations for quantum Max Cut , 11 2024

    2024

  15. [23]

    R.A. Jabr. Radial distribution load flow using conic programming. IEEE Transactions on Power Systems , 21(3):1458–1459, August 2006

    2006

  16. [24]

    Minimax design of IIR digital filters using iterative SOCP

    Aimin Jiang and Hon Keung Kwan. Minimax design of IIR digital filters using iterative SOCP . IEEE Transactions on Circuits and Systems I: Regular Papers , 57(6):1326–1337, June 2010

    2010

  17. [25]

    Samuel Jaques and Arthur G. Rattew. QRAM : A survey and critique, 2023

    2023

  18. [26]

    Efficient algorithms using the multiplicative weights update method

    Satyen Kale. Efficient algorithms using the multiplicative weights update method . PhD thesis, Princeton University, USA, 2007. AAI3286120

    2007

  19. [27]

    Dey, and X

    Burak Kocuk, Santanu S. Dey, and X. Andy Sun. Matrix minor reformulation and socp-based spatial branch-and-cut method for the AC optimal power flow problem. Mathematical Programming Computation , 10(4):557–596, October 2018

    2018

  20. [28]

    Alternating direction method of multipliers for truss topology optimization with limited number of nodes: a cardinality-constrained second-order cone programming approach

    Yoshihiro Kanno and Shinnosuke Fujita. Alternating direction method of multipliers for truss topology optimization with limited number of nodes: a cardinality-constrained second-order cone programming approach. Optimization and Engineering , 19(2):327–358, February 2018

    2018

  21. [29]

    Quantum recommendation systems

    Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In ITCS 2017 . Schloss Dagstuhl – Leibniz-Zentrum f\" u r Informatik, 2017

    2017

  22. [30]

    Quantum algorithms for second-order cone programming and support vector machines

    Iordanis Kerenidis, Anupam Prakash, and Dániel Szilágyi. Quantum algorithms for second-order cone programming and support vector machines. Quantum , 5:427, April 2021

    2021

  23. [31]

    Robust portfolio optimization using second-order cone programming , page 1–22

    Fiona Kolbert and Laurence Wormald. Robust portfolio optimization using second-order cone programming , page 1–22. Elsevier, 2010

    2010

  24. [32]

    Near-optimal ground state preparation

    Lin Lin and Yu Tong. Near-optimal ground state preparation. Quantum , 4:372, 2020

    2020

  25. [33]

    Applications of second-order cone programming

    Miguel Sousa Lobo, Lieven Vandenberghe, Stephen Boyd, and Hervé Lebret. Applications of second-order cone programming. Linear Algebra and its Applications , 284(1–3):193–228, November 1998

    1998

  26. [34]

    Martyn, Zane M

    John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. Grand unification of quantum algorithms. PRX Quantum , 2(4), December 2021

    2021

  27. [35]

    Renato D. C. Monteiro and Takashi Tsuchiya. Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ -family of directions. Mathematical Programming , 88(1):61--83, 2000

    2000

  28. [36]

    Ivan Papusha and Richard M. Murray. Analysis of control systems on symmetric cones. In 2015 54th IEEE Conference on Decision and Control (CDC) , page 3971–3976. IEEE, December 2015

    2015

  29. [37]

    Rattew and Patrick Rebentrost

    Arthur G. Rattew and Patrick Rebentrost. Non-linear transformations of quantum amplitudes: Exponential improvement, generalization, and applications, 2023

    2023

  30. [38]

    Biel Roig-Solvas and M. Sznaier. Globally convergent low complexity algorithms for semidefinite programming. In 2021 60th IEEE Conference on Decision and Control (CDC) , pages 1709--1714, 2021

    2021

  31. [39]

    A quantum-inspired classical algorithm for recommendation systems

    Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st annual ACM SIGACT symposium on theory of computing , pages 217--228, 2019

    2019

  32. [40]

    A CS guide to the quantum singular value transformation , pages 121--143

    Ewin Tang and Kevin Tian. A CS guide to the quantum singular value transformation , pages 121--143. Society for Industrial and Applied Mathematics (SIAM), 2024

    2024

  33. [41]

    J. Tao, G. Q. Wang, and L. Kong. The A raki- L ieb- T hirring inequality and the G olden- T hompson inequality in E uclidean J ordan algebras. Linear and Multilinear Algebra , 70(19):4228–4243, January 2021

    2021

  34. [42]

    Improvements in Quantum SDP-Solving with Applications

    Joran van Apeldoorn and Andr\' a s Gily\' e n. Improvements in Quantum SDP-Solving with Applications . In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)...

    2019

  35. [43]

    Quantum algorithms for zero-sum games, 2019

    Joran van Apeldoorn and András Gilyén. Quantum algorithms for zero-sum games, 2019

    2019

  36. [44]

    Quantum SDP -solvers: Better upper and lower bounds

    Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP -solvers: Better upper and lower bounds. Quantum , 4:230, February 2020

    2020

  37. [45]

    Second-order conic programming approach for W asserstein distributionally robust two-stage linear programs

    Zhuolin Wang, Keyou You, Shiji Song, and Yuli Zhang. Second-order conic programming approach for W asserstein distributionally robust two-stage linear programs. IEEE Transactions on Automation Science and Engineering , 19(2):946–958, April 2022

    2022

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.