東華大學圖書館 |

Quantum Optimization for Linear Algebra Problems.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Quantum Optimization for Linear Algebra Problems./
作者:	Borle, Ajinkya.
面頁冊數:	1 online resource (155 pages)
附註:	Source: Dissertations Abstracts International, Volume: 83-12, Section: B.
Contained By:	Dissertations Abstracts International83-12B.
標題:	Computer science. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28966656click for full text (PQDT)
ISBN:	9798438799214

Quantum Optimization for Linear Algebra Problems.
Borle, Ajinkya.

Quantum Optimization for Linear Algebra Problems. - 1 online resource (155 pages)

Source: Dissertations Abstracts International, Volume: 83-12, Section: B.

Thesis (Ph.D.)--University of Maryland, Baltimore County, 2022.

Includes bibliographical references

We have entered the age of noisy intermediate-scale quantum (NISQ) computers. However, these devices are not fault-tolerant to run the traditional quantum algorithms (like Shor's or Grover's Algorithm) for doing computation on a useful scale. In this dissertation work, we examine the potential of NISQ era quantum optimization, such as quantum annealing implemented for the Ising model and the gate-model quantum approximate optimization algorithm (QAOA), for solving problems in linear algebra. This is especially relevant as many of the other quantum algorithms (such as the Harrow Hassidim Lloyd algorithm) for linear algebra have a list of assumptions that may not be addressed in the near-term future. The discrete quantum optimization approach is an alternative to those techniques that while not being as fast as the more traditional quantum algorithms for linear algebra, may still perform better than the conventional classical techniques in the near-term and beyond.We start with a study of quantum annealing for solving linear least squares problems. Here, we show how quantum annealing can be faster than some of the most prominent direct (classical) methods, given certain assumptions. Our adiabatic simulations give an indication that quantum computing can have an advantage for problems where matrix A ∈ Rmxn has dimensions m>>n and also where A may be ill-conditioned. We followed it up with experiments on least squares problems and compared it to the best classical results.Next, we take a look at a few different ways in which post-processing results from quantum optimizers with classical techniques can impact the quality of the solution. We consider the single-qubit correction (SQC) and the multi-qubit correction (MQC) techniques, two promising techniques and study their effectiveness for the domain of linear algebra. In our work, we found SQC performs much better than MQC for domains where the problem graphs are densely connected, such as in linear algebra. In this context, we can think of numerical iterative techniques such as least squares MINRES (LSMR) for linear least squares and bi-conjugate gradient (BiCG) for linear systems of equations as highly effective domain specific post-processing techniques. When using the outputs from D-wave and SQC as the initial guess x0 for these techniques (instead of an all-zero vector), we found an improvement in a majority of the cases. This improvement was measured in terms of the number of iterations for reaching the termination condition and/or the absolute error in the residual b-Ax for a fixed number of iterations. This implies that a hybrid quantum-classical iterative solver may provide advantages against a purely classical one.And finally, we worked on applying and studying QAOA for binary linear least squares (BLLS), a problem that can serve as a building block for other hard problems in linear algebra. Our experiments were done on the QISKIT simulator and two IBM Q 5 qubit machines. To the best of our knowledge, this is the first work done on applying BLLS on a gate-model quantum computer. We highlight the possibilities of using QAOA and QAOA-like variational algorithms for solving such problems, where the outputs produced are classical, unlike the other gate model algorithms that produce amplitude encoded results. Our simulations indicate that QAOA can scale well with problem size for good approximate solutions but getting an optimal solution is more challenging. We show how Simulated Annealing can outperform QAOA for BLLS at a circuit depth of p≤3 for the probability of sampling the ground state. Finally, we point out some of the challenges involved in current-day experimental implementations of this technique on a cloud-based gate-model quantum computer.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2023

Mode of access: World Wide Web

ISBN: 9798438799214Subjects--Topical Terms:

523869
Computer science.
Subjects--Index Terms:

Adiabatic quantum computingIndex Terms--Genre/Form:

542853
Electronic books.

Quantum Optimization for Linear Algebra Problems.
LDR:05122nmm a2200385K 4500 001 2354229
005 20230403071153.5
006 m o d
007 cr mn ---uuuuu
008 241011s2022 xx obm 000 0 eng d
020 $a 9798438799214
035 $a (MiAaPQ)AAI28966656
035 $a AAI28966656
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Borle, Ajinkya. $3 3694577
245 1 0 $a Quantum Optimization for Linear Algebra Problems.
264 0 $c 2022
300 $a 1 online resource (155 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 83-12, Section: B.
500 $a Advisor: Lomonaco, Samuel.
502 $a Thesis (Ph.D.)--University of Maryland, Baltimore County, 2022.
504 $a Includes bibliographical references
520 $a We have entered the age of noisy intermediate-scale quantum (NISQ) computers. However, these devices are not fault-tolerant to run the traditional quantum algorithms (like Shor's or Grover's Algorithm) for doing computation on a useful scale. In this dissertation work, we examine the potential of NISQ era quantum optimization, such as quantum annealing implemented for the Ising model and the gate-model quantum approximate optimization algorithm (QAOA), for solving problems in linear algebra. This is especially relevant as many of the other quantum algorithms (such as the Harrow Hassidim Lloyd algorithm) for linear algebra have a list of assumptions that may not be addressed in the near-term future. The discrete quantum optimization approach is an alternative to those techniques that while not being as fast as the more traditional quantum algorithms for linear algebra, may still perform better than the conventional classical techniques in the near-term and beyond.We start with a study of quantum annealing for solving linear least squares problems. Here, we show how quantum annealing can be faster than some of the most prominent direct (classical) methods, given certain assumptions. Our adiabatic simulations give an indication that quantum computing can have an advantage for problems where matrix A ∈ Rmxn has dimensions m>>n and also where A may be ill-conditioned. We followed it up with experiments on least squares problems and compared it to the best classical results.Next, we take a look at a few different ways in which post-processing results from quantum optimizers with classical techniques can impact the quality of the solution. We consider the single-qubit correction (SQC) and the multi-qubit correction (MQC) techniques, two promising techniques and study their effectiveness for the domain of linear algebra. In our work, we found SQC performs much better than MQC for domains where the problem graphs are densely connected, such as in linear algebra. In this context, we can think of numerical iterative techniques such as least squares MINRES (LSMR) for linear least squares and bi-conjugate gradient (BiCG) for linear systems of equations as highly effective domain specific post-processing techniques. When using the outputs from D-wave and SQC as the initial guess x0 for these techniques (instead of an all-zero vector), we found an improvement in a majority of the cases. This improvement was measured in terms of the number of iterations for reaching the termination condition and/or the absolute error in the residual b-Ax for a fixed number of iterations. This implies that a hybrid quantum-classical iterative solver may provide advantages against a purely classical one.And finally, we worked on applying and studying QAOA for binary linear least squares (BLLS), a problem that can serve as a building block for other hard problems in linear algebra. Our experiments were done on the QISKIT simulator and two IBM Q 5 qubit machines. To the best of our knowledge, this is the first work done on applying BLLS on a gate-model quantum computer. We highlight the possibilities of using QAOA and QAOA-like variational algorithms for solving such problems, where the outputs produced are classical, unlike the other gate model algorithms that produce amplitude encoded results. Our simulations indicate that QAOA can scale well with problem size for good approximate solutions but getting an optimal solution is more challenging. We show how Simulated Annealing can outperform QAOA for BLLS at a circuit depth of p≤3 for the probability of sampling the ground state. Finally, we point out some of the challenges involved in current-day experimental implementations of this technique on a cloud-based gate-model quantum computer.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2023
538 $a Mode of access: World Wide Web
650 4 $a Computer science. $3 523869
650 4 $a Quantum physics. $3 726746
650 4 $a Applied mathematics. $3 2122814
653 $a Adiabatic quantum computing
653 $a Linear algebra
653 $a Quantum annealing
653 $a Quantum optimization
655 7 $a Electronic books. $2 lcsh $3 542853
690 $a 0984
690 $a 0599
690 $a 0364
710 2 $a ProQuest Information and Learning Co. $3 783688
710 2 $a University of Maryland, Baltimore County. $b Computer Science. $3 1018441
773 0 $t Dissertations Abstracts International $g 83-12B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28966656 $z click for full text (PQDT)