Quantum algorithms for Second-Order Cone Programming and Support Vector Machines
We present a quantum interior-point method (IPM) for second-order cone programming (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 of int...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2021-04-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2021-04-08-427/pdf/ |
| _version_ | 1818726462671290368 |
|---|---|
| author | Iordanis Kerenidis Anupam Prakash Dániel Szilágyi |
| author_facet | Iordanis Kerenidis Anupam Prakash Dániel Szilágyi |
| author_sort | Iordanis Kerenidis |
| collection | DOAJ |
| description | We present a quantum interior-point method (IPM) for second-order cone programming (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 of intermediate solutions from the cone boundary, $\zeta$ is a parameter upper bounded by $\sqrt{n}$, and $\kappa$ is an upper bound on the condition number of matrices arising in the classical IPM for SOCP. The algorithm takes as its input a suitable quantum description of an arbitrary SOCP and outputs a classical description of a $\delta$-approximate $\epsilon$-optimal solution of the given problem.
Furthermore, we perform numerical simulations to determine the values of the aforementioned parameters when solving the SOCP up to a fixed precision $\epsilon$. We present experimental evidence that in this case our quantum algorithm exhibits a polynomial speedup over the best classical algorithms for solving general SOCPs that run in time $O(n^{\omega+0.5})$ (here, $\omega$ is the 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 the exponent $k$ is estimated to be $2.59$ using a least-squares power law. On the same family random instances, the estimated scaling exponent for an external SOCP solver is $3.31$ while that for a state-of-the-art SVM solver is $3.11$. |
| first_indexed | 2024-12-17T21:58:35Z |
| format | Article |
| id | doaj.art-b0e74baf98e843c09119de25150c4b28 |
| institution | Directory Open Access Journal |
| issn | 2521-327X |
| language | English |
| last_indexed | 2024-12-17T21:58:35Z |
| publishDate | 2021-04-01 |
| publisher | Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften |
| record_format | Article |
| series | Quantum |
| spelling | doaj.art-b0e74baf98e843c09119de25150c4b282022-12-21T21:31:03ZengVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenQuantum2521-327X2021-04-01542710.22331/q-2021-04-08-42710.22331/q-2021-04-08-427Quantum algorithms for Second-Order Cone Programming and Support Vector MachinesIordanis KerenidisAnupam PrakashDániel SzilágyiWe present a quantum interior-point method (IPM) for second-order cone programming (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 of intermediate solutions from the cone boundary, $\zeta$ is a parameter upper bounded by $\sqrt{n}$, and $\kappa$ is an upper bound on the condition number of matrices arising in the classical IPM for SOCP. The algorithm takes as its input a suitable quantum description of an arbitrary SOCP and outputs a classical description of a $\delta$-approximate $\epsilon$-optimal solution of the given problem. Furthermore, we perform numerical simulations to determine the values of the aforementioned parameters when solving the SOCP up to a fixed precision $\epsilon$. We present experimental evidence that in this case our quantum algorithm exhibits a polynomial speedup over the best classical algorithms for solving general SOCPs that run in time $O(n^{\omega+0.5})$ (here, $\omega$ is the 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 the exponent $k$ is estimated to be $2.59$ using a least-squares power law. On the same family random instances, the estimated scaling exponent for an external SOCP solver is $3.31$ while that for a state-of-the-art SVM solver is $3.11$.https://quantum-journal.org/papers/q-2021-04-08-427/pdf/ |
| spellingShingle | Iordanis Kerenidis Anupam Prakash Dániel Szilágyi Quantum algorithms for Second-Order Cone Programming and Support Vector Machines Quantum |
| title | Quantum algorithms for Second-Order Cone Programming and Support Vector Machines |
| title_full | Quantum algorithms for Second-Order Cone Programming and Support Vector Machines |
| title_fullStr | Quantum algorithms for Second-Order Cone Programming and Support Vector Machines |
| title_full_unstemmed | Quantum algorithms for Second-Order Cone Programming and Support Vector Machines |
| title_short | Quantum algorithms for Second-Order Cone Programming and Support Vector Machines |
| title_sort | quantum algorithms for second order cone programming and support vector machines |
| url | https://quantum-journal.org/papers/q-2021-04-08-427/pdf/ |
| work_keys_str_mv | AT iordaniskerenidis quantumalgorithmsforsecondorderconeprogrammingandsupportvectormachines AT anupamprakash quantumalgorithmsforsecondorderconeprogrammingandsupportvectormachines AT danielszilagyi quantumalgorithmsforsecondorderconeprogrammingandsupportvectormachines |