Tensor networks based quantum optimization algorithm
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914766889418752 |
|---|---|
| author | Akshay, V. Melnikov, Ar. Termanova, A. Perelshtein, M. R. |
| author_facet | Akshay, V. Melnikov, Ar. Termanova, A. Perelshtein, M. R. |
| contents | In optimization, one of the well-known classical algorithms is power iterations. Simply stated, the algorithm recovers the dominant eigenvector of some diagonalizable matrix. Since numerous optimization problems can be formulated as an eigenvalue/eigenvector search, this algorithm features wide applicability. Operationally, power iterations consist of performing repeated matrix-to-vector multiplications (or MatVec) followed by a renormilization step in order to converge to the dominant eigenvalue/eigenvector. However, classical realizations, including novel tensor network based approaches, necessitate an exponential scaling for the algorithm's run-time. In this paper, we propose a quantum realiziation to circumvent this pitfall. Our methodology involves casting low-rank representations; Matrix Product Operators (MPO) for matrices and Matrix Product States (MPS) for vectors, into quantum circuits. Specifically, we recover a unitary approximation by variationally minimizing the Frobenius distance between a target MPO and an MPO ansatz wherein the tensor cores are constrained to unitaries. Such an unitary MPO can easily be implemented as a quantum circuit with the addition of ancillary qubits. Thereafter, with appropriate initialization and post-selection on the ancillary space, we realize a single iteration of the classical algorithm. With our proposed methodology, power iterations can be realized entirely on a quantum computer via repeated, static circuit blocks; therefore, a run-time advantage can indeed be guaranteed. Moreover, by exploiting Riemannian optimization and cross-approximation techniques, our methodology becomes instance agnostic and thus allows one to address black-box optimization within the framework of quantum computing. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_15048 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tensor networks based quantum optimization algorithm Akshay, V. Melnikov, Ar. Termanova, A. Perelshtein, M. R. Quantum Physics In optimization, one of the well-known classical algorithms is power iterations. Simply stated, the algorithm recovers the dominant eigenvector of some diagonalizable matrix. Since numerous optimization problems can be formulated as an eigenvalue/eigenvector search, this algorithm features wide applicability. Operationally, power iterations consist of performing repeated matrix-to-vector multiplications (or MatVec) followed by a renormilization step in order to converge to the dominant eigenvalue/eigenvector. However, classical realizations, including novel tensor network based approaches, necessitate an exponential scaling for the algorithm's run-time. In this paper, we propose a quantum realiziation to circumvent this pitfall. Our methodology involves casting low-rank representations; Matrix Product Operators (MPO) for matrices and Matrix Product States (MPS) for vectors, into quantum circuits. Specifically, we recover a unitary approximation by variationally minimizing the Frobenius distance between a target MPO and an MPO ansatz wherein the tensor cores are constrained to unitaries. Such an unitary MPO can easily be implemented as a quantum circuit with the addition of ancillary qubits. Thereafter, with appropriate initialization and post-selection on the ancillary space, we realize a single iteration of the classical algorithm. With our proposed methodology, power iterations can be realized entirely on a quantum computer via repeated, static circuit blocks; therefore, a run-time advantage can indeed be guaranteed. Moreover, by exploiting Riemannian optimization and cross-approximation techniques, our methodology becomes instance agnostic and thus allows one to address black-box optimization within the framework of quantum computing. |
| title | Tensor networks based quantum optimization algorithm |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2404.15048 |