Fault-ignorant quantum search
We investigate the problem of quantum searching on a noisy quantum computer. Taking a fault-ignorant approach, we analyze quantum algorithms that solve the task for various different noise strengths, which are possibly unknown beforehand. We prove lower bounds on the runtime of such algorithms and t...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IOP Publishing
2014-01-01
|
| Series: | New Journal of Physics |
| Subjects: | |
| Online Access: | https://doi.org/10.1088/1367-2630/16/7/073033 |
| _version_ | 1827874181349376000 |
|---|---|
| author | Péter Vrana David Reeb Daniel Reitzner Michael M Wolf |
| author_facet | Péter Vrana David Reeb Daniel Reitzner Michael M Wolf |
| author_sort | Péter Vrana |
| collection | DOAJ |
| description | We investigate the problem of quantum searching on a noisy quantum computer. Taking a fault-ignorant approach, we analyze quantum algorithms that solve the task for various different noise strengths, which are possibly unknown beforehand. We prove lower bounds on the runtime of such algorithms and thereby find that the quadratic speedup is necessarily lost (in our noise models). However, for low but constant noise levels the algorithms we provide (based on Groverʼs algorithm) still outperform the best noiseless classical search algorithm. |
| first_indexed | 2024-03-12T16:48:34Z |
| format | Article |
| id | doaj.art-661e04eb566f406cb4836753fc13827f |
| institution | Directory Open Access Journal |
| issn | 1367-2630 |
| language | English |
| last_indexed | 2024-03-12T16:48:34Z |
| publishDate | 2014-01-01 |
| publisher | IOP Publishing |
| record_format | Article |
| series | New Journal of Physics |
| spelling | doaj.art-661e04eb566f406cb4836753fc13827f2023-08-08T11:27:45ZengIOP PublishingNew Journal of Physics1367-26302014-01-0116707303310.1088/1367-2630/16/7/073033Fault-ignorant quantum searchPéter Vrana0David Reeb1Daniel Reitzner2Michael M Wolf3Institute for Theoretical Physics , ETH Zürich, 8093 Zürich, SwitzerlandDepartment of Mathematics, Technische Universität München , D-85748 Garching, GermanyDepartment of Mathematics, Technische Universität München , D-85748 Garching, Germany; Institute of Physics, Slovak Academy of Sciences , 845 11 Bratislava, SlovakiaDepartment of Mathematics, Technische Universität München , D-85748 Garching, GermanyWe investigate the problem of quantum searching on a noisy quantum computer. Taking a fault-ignorant approach, we analyze quantum algorithms that solve the task for various different noise strengths, which are possibly unknown beforehand. We prove lower bounds on the runtime of such algorithms and thereby find that the quadratic speedup is necessarily lost (in our noise models). However, for low but constant noise levels the algorithms we provide (based on Groverʼs algorithm) still outperform the best noiseless classical search algorithm.https://doi.org/10.1088/1367-2630/16/7/073033quantum searchalgorithmsfault toleranceGrover searchcomputational complexityerror correction |
| spellingShingle | Péter Vrana David Reeb Daniel Reitzner Michael M Wolf Fault-ignorant quantum search New Journal of Physics quantum search algorithms fault tolerance Grover search computational complexity error correction |
| title | Fault-ignorant quantum search |
| title_full | Fault-ignorant quantum search |
| title_fullStr | Fault-ignorant quantum search |
| title_full_unstemmed | Fault-ignorant quantum search |
| title_short | Fault-ignorant quantum search |
| title_sort | fault ignorant quantum search |
| topic | quantum search algorithms fault tolerance Grover search computational complexity error correction |
| url | https://doi.org/10.1088/1367-2630/16/7/073033 |
| work_keys_str_mv | AT petervrana faultignorantquantumsearch AT davidreeb faultignorantquantumsearch AT danielreitzner faultignorantquantumsearch AT michaelmwolf faultignorantquantumsearch |