Asymptotic Quantum Algorithm for the Toeplitz Systems

Solving the Toeplitz systems, which is to find the vector \(x\) such that \(T_nx = b\) given an \(n\times n\) Toeplitz matrix \(T_n\) and a vector \(b\), has a variety of applications in mathematics and engineering. In this paper, we present a quantum algorithm for solving the linear equations of To...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2018-02
Main Authors: Lin-Chun, Wan, Chao-Hua, Yu, Shi-Jie, Pan, Gao, Fei, Qiao-Yan, Wen, Su-Juan, Qin
Format: Article
Language:English
Subjects:
Algorithms
Continuity (mathematics)
Linear equations
Linear systems
Mathematical analysis
Matrix algebra
Matrix methods
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page
container_issue
container_start_page
container_title arXiv.org
container_volume
creator Lin-Chun, Wan
Chao-Hua, Yu
Shi-Jie, Pan
Gao, Fei
Qiao-Yan, Wen
Su-Juan, Qin
description Solving the Toeplitz systems, which is to find the vector \(x\) such that \(T_nx = b\) given an \(n\times n\) Toeplitz matrix \(T_n\) and a vector \(b\), has a variety of applications in mathematics and engineering. In this paper, we present a quantum algorithm for solving the linear equations of Toeplitz matrices, in which the Toeplitz matrices are generated by discretizing a continuous function. It is shown that our algorithm's complexity is nearly \(O(\kappa\textrm{log}^2 n)\), where \(\kappa\) and \(n\) are the condition number and the dimension of \(T_n\) respectively. This implies our algorithm is exponentially faster than the best classical algorithm for the same problem if \(\kappa=O(\textrm{poly}(\textrm{log}\,n))\). Since no assumption on the sparseness of \(T_n\) is demanded in our algorithm, it can serve as an example of quantum algorithms for solving non-sparse linear systems.
doi_str_mv 10.48550/arxiv.1608.02184
format article
fullrecord <record><control><sourceid>proquest</sourceid><recordid>TN_cdi_proquest_journals_2074028508</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2074028508</sourcerecordid><originalsourceid>FETCH-LOGICAL-a528-859b6bc918bff1ded1d4f0916d36452586e88f89fe0c6b035be2d9514b94647a3</originalsourceid><addsrcrecordid>eNotzctKxDAUgOEgCA7jPIC7gOvWk8tJT5Zl8AYDInY_9JI4HdpJbVJxfHoFXf2772fsRkCuCRHu6vmr_8yFAcpBCtIXbCWVEhlpKa_YJsYjAEhTSES1YljG8zilkPqWvy71KS0jL4f3MPfpMHIfZp4OjlfBTUOfvvnbOSY3xmt26eshus1_16x6uK-2T9nu5fF5W-6yGiVlhLYxTWsFNd6LznWi0x6sMJ0yGiWScUSerHfQmgYUNk52FoVurDa6qNWa3f6x0xw-FhfT_hiW-fR73EsoNEhCIPUD96xG1g</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2074028508</pqid></control><display><type>article</type><title>Asymptotic Quantum Algorithm for the Toeplitz Systems</title><source>Publicly Available Content Database</source><creator>Lin-Chun, Wan ; Chao-Hua, Yu ; Shi-Jie, Pan ; Gao, Fei ; Qiao-Yan, Wen ; Su-Juan, Qin</creator><creatorcontrib>Lin-Chun, Wan ; Chao-Hua, Yu ; Shi-Jie, Pan ; Gao, Fei ; Qiao-Yan, Wen ; Su-Juan, Qin</creatorcontrib><description>Solving the Toeplitz systems, which is to find the vector \(x\) such that \(T_nx = b\) given an \(n\times n\) Toeplitz matrix \(T_n\) and a vector \(b\), has a variety of applications in mathematics and engineering. In this paper, we present a quantum algorithm for solving the linear equations of Toeplitz matrices, in which the Toeplitz matrices are generated by discretizing a continuous function. It is shown that our algorithm's complexity is nearly \(O(\kappa\textrm{log}^2 n)\), where \(\kappa\) and \(n\) are the condition number and the dimension of \(T_n\) respectively. This implies our algorithm is exponentially faster than the best classical algorithm for the same problem if \(\kappa=O(\textrm{poly}(\textrm{log}\,n))\). Since no assumption on the sparseness of \(T_n\) is demanded in our algorithm, it can serve as an example of quantum algorithms for solving non-sparse linear systems.</description><identifier>EISSN: 2331-8422</identifier><identifier>DOI: 10.48550/arxiv.1608.02184</identifier><language>eng</language><publisher>Ithaca: Cornell University Library, arXiv.org</publisher><subject>Algorithms ; Continuity (mathematics) ; Linear equations ; Linear systems ; Mathematical analysis ; Matrix algebra ; Matrix methods</subject><ispartof>arXiv.org, 2018-02</ispartof><rights>2018. This work is published under http://arxiv.org/licenses/nonexclusive-distrib/1.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.</rights><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.proquest.com/docview/2074028508?pq-origsite=primo$$EHTML$$P50$$Gproquest$$Hfree_for_read</linktohtml><link.rule.ids>776,780,25732,27904,36991,44569</link.rule.ids></links><search><creatorcontrib>Lin-Chun, Wan</creatorcontrib><creatorcontrib>Chao-Hua, Yu</creatorcontrib><creatorcontrib>Shi-Jie, Pan</creatorcontrib><creatorcontrib>Gao, Fei</creatorcontrib><creatorcontrib>Qiao-Yan, Wen</creatorcontrib><creatorcontrib>Su-Juan, Qin</creatorcontrib><title>Asymptotic Quantum Algorithm for the Toeplitz Systems</title><title>arXiv.org</title><description>Solving the Toeplitz systems, which is to find the vector \(x\) such that \(T_nx = b\) given an \(n\times n\) Toeplitz matrix \(T_n\) and a vector \(b\), has a variety of applications in mathematics and engineering. In this paper, we present a quantum algorithm for solving the linear equations of Toeplitz matrices, in which the Toeplitz matrices are generated by discretizing a continuous function. It is shown that our algorithm's complexity is nearly \(O(\kappa\textrm{log}^2 n)\), where \(\kappa\) and \(n\) are the condition number and the dimension of \(T_n\) respectively. This implies our algorithm is exponentially faster than the best classical algorithm for the same problem if \(\kappa=O(\textrm{poly}(\textrm{log}\,n))\). Since no assumption on the sparseness of \(T_n\) is demanded in our algorithm, it can serve as an example of quantum algorithms for solving non-sparse linear systems.</description><subject>Algorithms</subject><subject>Continuity (mathematics)</subject><subject>Linear equations</subject><subject>Linear systems</subject><subject>Mathematical analysis</subject><subject>Matrix algebra</subject><subject>Matrix methods</subject><issn>2331-8422</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2018</creationdate><recordtype>article</recordtype><sourceid>PIMPY</sourceid><recordid>eNotzctKxDAUgOEgCA7jPIC7gOvWk8tJT5Zl8AYDInY_9JI4HdpJbVJxfHoFXf2772fsRkCuCRHu6vmr_8yFAcpBCtIXbCWVEhlpKa_YJsYjAEhTSES1YljG8zilkPqWvy71KS0jL4f3MPfpMHIfZp4OjlfBTUOfvvnbOSY3xmt26eshus1_16x6uK-2T9nu5fF5W-6yGiVlhLYxTWsFNd6LznWi0x6sMJ0yGiWScUSerHfQmgYUNk52FoVurDa6qNWa3f6x0xw-FhfT_hiW-fR73EsoNEhCIPUD96xG1g</recordid><startdate>20180201</startdate><enddate>20180201</enddate><creator>Lin-Chun, Wan</creator><creator>Chao-Hua, Yu</creator><creator>Shi-Jie, Pan</creator><creator>Gao, Fei</creator><creator>Qiao-Yan, Wen</creator><creator>Su-Juan, Qin</creator><general>Cornell University Library, arXiv.org</general><scope>8FE</scope><scope>8FG</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>HCIFZ</scope><scope>L6V</scope><scope>M7S</scope><scope>PIMPY</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PTHSS</scope></search><sort><creationdate>20180201</creationdate><title>Asymptotic Quantum Algorithm for the Toeplitz Systems</title><author>Lin-Chun, Wan ; Chao-Hua, Yu ; Shi-Jie, Pan ; Gao, Fei ; Qiao-Yan, Wen ; Su-Juan, Qin</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-a528-859b6bc918bff1ded1d4f0916d36452586e88f89fe0c6b035be2d9514b94647a3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2018</creationdate><topic>Algorithms</topic><topic>Continuity (mathematics)</topic><topic>Linear equations</topic><topic>Linear systems</topic><topic>Mathematical analysis</topic><topic>Matrix algebra</topic><topic>Matrix methods</topic><toplevel>online_resources</toplevel><creatorcontrib>Lin-Chun, Wan</creatorcontrib><creatorcontrib>Chao-Hua, Yu</creatorcontrib><creatorcontrib>Shi-Jie, Pan</creatorcontrib><creatorcontrib>Gao, Fei</creatorcontrib><creatorcontrib>Qiao-Yan, Wen</creatorcontrib><creatorcontrib>Su-Juan, Qin</creatorcontrib><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central UK/Ireland</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central Korea</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Engineering Collection</collection><collection>Engineering Database</collection><collection>Publicly Available Content Database</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>Engineering collection</collection><jtitle>arXiv.org</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Lin-Chun, Wan</au><au>Chao-Hua, Yu</au><au>Shi-Jie, Pan</au><au>Gao, Fei</au><au>Qiao-Yan, Wen</au><au>Su-Juan, Qin</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Asymptotic Quantum Algorithm for the Toeplitz Systems</atitle><jtitle>arXiv.org</jtitle><date>2018-02-01</date><risdate>2018</risdate><eissn>2331-8422</eissn><abstract>Solving the Toeplitz systems, which is to find the vector \(x\) such that \(T_nx = b\) given an \(n\times n\) Toeplitz matrix \(T_n\) and a vector \(b\), has a variety of applications in mathematics and engineering. In this paper, we present a quantum algorithm for solving the linear equations of Toeplitz matrices, in which the Toeplitz matrices are generated by discretizing a continuous function. It is shown that our algorithm's complexity is nearly \(O(\kappa\textrm{log}^2 n)\), where \(\kappa\) and \(n\) are the condition number and the dimension of \(T_n\) respectively. This implies our algorithm is exponentially faster than the best classical algorithm for the same problem if \(\kappa=O(\textrm{poly}(\textrm{log}\,n))\). Since no assumption on the sparseness of \(T_n\) is demanded in our algorithm, it can serve as an example of quantum algorithms for solving non-sparse linear systems.</abstract><cop>Ithaca</cop><pub>Cornell University Library, arXiv.org</pub><doi>10.48550/arxiv.1608.02184</doi><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier EISSN: 2331-8422
ispartof arXiv.org, 2018-02
issn 2331-8422
language eng
recordid cdi_proquest_journals_2074028508
source Publicly Available Content Database
subjects Algorithms
Continuity (mathematics)
Linear equations
Linear systems
Mathematical analysis
Matrix algebra
Matrix methods
title Asymptotic Quantum Algorithm for the Toeplitz Systems
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-24T10%3A10%3A29IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Asymptotic%20Quantum%20Algorithm%20for%20the%20Toeplitz%20Systems&rft.jtitle=arXiv.org&rft.au=Lin-Chun,%20Wan&rft.date=2018-02-01&rft.eissn=2331-8422&rft_id=info:doi/10.48550/arxiv.1608.02184&rft_dat=%3Cproquest%3E2074028508%3C/proquest%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-a528-859b6bc918bff1ded1d4f0916d36452586e88f89fe0c6b035be2d9514b94647a3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2074028508&rft_id=info:pmid/&rfr_iscdi=true