東華大學圖書館 |

語系: 繁體中文

說明(常見問題)

回圖書館首頁

手機版館藏查詢

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

FindBook

Google Book

Amazon

博客來

Quantum Speedups : = Structure, Design, and Application.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Quantum Speedups :/
其他題名:	Structure, Design, and Application.
作者:	Wang, Daochen.
面頁冊數:	1 online resource (153 pages)
附註:	Source: Dissertations Abstracts International, Volume: 84-12, Section: B.
Contained By:	Dissertations Abstracts International84-12B.
標題:	Applied mathematics. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30420382click for full text (PQDT)
ISBN:	9798379761721

Quantum Speedups : = Structure, Design, and Application.
Wang, Daochen.

Quantum Speedups :Structure, Design, and Application. - 1 online resource (153 pages)

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

Thesis (Ph.D.)--University of Maryland, College Park, 2023.

Includes bibliographical references

A quantum speedup occurs when a computational problem can be solved faster on a quantum computer than on a classical computer. This thesis studies the circumstances under which quantum speedups can arise from three perspectives.First, we study the structure of the problem. We characterize how a problem's symmetries decide whether it admits a superpolynomial or polynomial quantum speedup. In particular, we show that the computation of any partial function of a hypergraph's adjacency matrix admits at most a polynomial speedup. Such functions are only weakly symmetric and subsequent work shows that if the symmetry is weakened even further, then a superpolynomial speedup can be possible. To complete the picture for graph problems, we also construct a partial function of a graph's adjacency list that admits an exponential speedup.Second, we study classical paradigms for solving problems. We design a natural quantum query analogue of the divide and conquer paradigm, which we call the ``quantum divide and conquer'' framework. This framework allows us to quantumly speed up the solution of many problems that are classically solved using divide and conquer. The main technical novelty of our framework is that it naturally combines quantum adversary and quantum algorithmic techniques. To showcase its usefulness, we apply it to obtain near-optimal quantum query complexities for four string problems: (i) recognizing regular languages; (ii) decision versions of String Rotation and String Suffix; and natural parameterized versions of (iii) Longest Increasing Subsequence and (iv) Longest Common Subsequence.Third, we study ways of generalizing a problem known to admit a quantum speedup. We generalize the search problem of finding a marked item in a database to the case where the items are not either marked or unmarked, but are ``partially marked''. The goal is to find the item that is the most heavily marked. We construct a quantum algorithm for this problem within the variable-time framework and prove its near-optimality by modifying the standard adversary method to work for oracles encoding probability distributions. Coincidentally, the problem studied is equivalent to the multi-armed bandits problem in reinforcement learning, which has many applications.

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

Mode of access: World Wide Web

ISBN: 9798379761721Subjects--Topical Terms:

2122814
Applied mathematics.
Subjects--Index Terms:

Quantum algorithmsIndex Terms--Genre/Form:

542853
Electronic books.

Quantum Speedups : = Structure, Design, and Application.
LDR:03635nmm a2200385K 4500 001 2363187
005 20231116093819.5
006 m o d
007 cr mn ---uuuuu
008 241011s2023 xx obm 000 0 eng d
020 $a 9798379761721
035 $a (MiAaPQ)AAI30420382
035 $a AAI30420382
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Wang, Daochen. $3 3703937
245 1 0 $a Quantum Speedups : $b Structure, Design, and Application.
264 0 $c 2023
300 $a 1 online resource (153 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: 84-12, Section: B.
500 $a Advisor: Childs, Andrew M.;Miller, Carl A.
502 $a Thesis (Ph.D.)--University of Maryland, College Park, 2023.
504 $a Includes bibliographical references
520 $a A quantum speedup occurs when a computational problem can be solved faster on a quantum computer than on a classical computer. This thesis studies the circumstances under which quantum speedups can arise from three perspectives.First, we study the structure of the problem. We characterize how a problem's symmetries decide whether it admits a superpolynomial or polynomial quantum speedup. In particular, we show that the computation of any partial function of a hypergraph's adjacency matrix admits at most a polynomial speedup. Such functions are only weakly symmetric and subsequent work shows that if the symmetry is weakened even further, then a superpolynomial speedup can be possible. To complete the picture for graph problems, we also construct a partial function of a graph's adjacency list that admits an exponential speedup.Second, we study classical paradigms for solving problems. We design a natural quantum query analogue of the divide and conquer paradigm, which we call the ``quantum divide and conquer'' framework. This framework allows us to quantumly speed up the solution of many problems that are classically solved using divide and conquer. The main technical novelty of our framework is that it naturally combines quantum adversary and quantum algorithmic techniques. To showcase its usefulness, we apply it to obtain near-optimal quantum query complexities for four string problems: (i) recognizing regular languages; (ii) decision versions of String Rotation and String Suffix; and natural parameterized versions of (iii) Longest Increasing Subsequence and (iv) Longest Common Subsequence.Third, we study ways of generalizing a problem known to admit a quantum speedup. We generalize the search problem of finding a marked item in a database to the case where the items are not either marked or unmarked, but are ``partially marked''. The goal is to find the item that is the most heavily marked. We construct a quantum algorithm for this problem within the variable-time framework and prove its near-optimality by modifying the standard adversary method to work for oracles encoding probability distributions. Coincidentally, the problem studied is equivalent to the multi-armed bandits problem in reinforcement learning, which has many applications.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2023
538 $a Mode of access: World Wide Web
650 4 $a Applied mathematics. $3 2122814
650 4 $a Computer science. $3 523869
650 4 $a Quantum physics. $3 726746
653 $a Quantum algorithms
653 $a Quantum computation
653 $a Quantum speedups
653 $a Superpolynomial
655 7 $a Electronic books. $2 lcsh $3 542853
690 $a 0364
690 $a 0984
690 $a 0599
710 2 $a ProQuest Information and Learning Co. $3 783688
710 2 $a University of Maryland, College Park. $b Applied Mathematics and Scientific Computation. $3 1021743
773 0 $t Dissertations Abstracts International $g 84-12B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30420382 $z click for full text (PQDT)