English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We present a quantum interior-point method (IPM) for second-order coneprogramming (SOCP) that runs in time $\widetilde{O} \left( n\sqrt{r}\frac{\zeta \kappa}{\delta^2} \log \left(1/\epsilon\right) \right)$ where $r$is the rank and $n$ the dimension of the SOCP, $\delta$ bounds the distance ofintermediate solutions from the cone boundary, $\zeta$ is a parameter upperbounded by $\sqrt{n}$, and $\kappa$ is an upper bound on the condition numberof matrices arising in the classical IPM for SOCP. The algorithm takes as itsinput a suitable quantum description of an arbitrary SOCP and outputs aclassical description of a $\delta$-approximate $\epsilon$-optimal solution ofthe given problem.  Furthermore, we perform numerical simulations to determine the values of theaforementioned parameters when solving the SOCP up to a fixed precision$\epsilon$. We present experimental evidence that in this case our quantumalgorithm exhibits a polynomial speedup over the best classical algorithms forsolving general SOCPs that run in time $O(n^{\omega+0.5})$ (here, $\omega$ isthe matrix multiplication exponent, with a value of roughly $2.37$ in theory,and up to $3$ in practice). For the case of random SVM (support vector machine)instances of size $O(n)$, the quantum algorithm scales as $O(n^k)$, where theexponent $k$ is estimated to be $2.59$ using a least-squares power law. On thesame family random instances, the estimated scaling exponent for an externalSOCP solver is $3.31$ while that for a state-of-the-art SVM solver is $3.11$.

Quantum algorithms for Second-Order Cone Programming and Support Vector Machines