|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
The Complexity of NISQ | | Sitan Chen
; Jordan Cotler
; Hsin-Yuan Huang
; Jerry Li
; | | Date: |
13 Oct 2022 | | Abstract: | The recent proliferation of NISQ devices has made it imperative to understand
their computational power. In this work, we define and study the complexity
class $ extsf{NISQ} $, which is intended to encapsulate problems that can be
efficiently solved by a classical computer with access to a NISQ device. To
model existing devices, we assume the device can (1) noisily initialize all
qubits, (2) apply many noisy quantum gates, and (3) perform a noisy measurement
on all qubits. We first give evidence that $ extsf{BPP}subsetneq
extsf{NISQ}subsetneq extsf{BQP}$, by demonstrating super-polynomial oracle
separations among the three classes, based on modifications of Simon’s problem.
We then consider the power of $ extsf{NISQ}$ for three well-studied problems.
For unstructured search, we prove that $ extsf{NISQ}$ cannot achieve a
Grover-like quadratic speedup over $ extsf{BPP}$. For the Bernstein-Vazirani
problem, we show that $ extsf{NISQ}$ only needs a number of queries
logarithmic in what is required for $ extsf{BPP}$. Finally, for a quantum
state learning problem, we prove that $ extsf{NISQ}$ is exponentially weaker
than classical computation with access to noiseless constant-depth quantum
circuits. | | Source: | arXiv, 2210.07234 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER