Questions tagged [quantum-advantage]
"Quantum advantage" or "quantum supremacy" is the potential ability of quantum computing devices to solve problems that classical computers practically cannot.
81
questions
6
votes
3answers
652 views
Quantum advantage with only Clifford gates (Gottesman Knill theorem)
Let's say I want to solve a computational task which input can be encoded in $n$ bits of information.
The look for a quantum advantage is (usually) asking to find a quantum algorithm in which there ...
1
vote
1answer
77 views
How does a quantum computer execute a process by leveraging superposition?
I understand in plain terms superposition and entanglement, but I'm very unclear how either of these could work as a means to increase computation power.
A helpful metaphor is that of the maze. A ...
2
votes
1answer
40 views
Random quantum circuits and general efficient POVM measurement
Let's consider a random quantum circuit $C$, applied to the $n$ qubit initial state $|0^{n}\rangle$, producing the state $|\psi\rangle$.
Consider a general efficiently implementable $m$-outcome POVM ...
8
votes
1answer
76 views
How can one define contextuality within the circuit model?
It is in general believed that contextuality is one of the quantum resource that provides the quantum advantage. A context is usually defined in terms of a set of commuting observables. The quantum ...
2
votes
1answer
89 views
Average output state of random quantum circuits
Let $|\psi\rangle = C_1 |0^{n}\rangle$ be a quantum state, such that $C_1$ is a Haar random unitary circuit. Consider a density matrix $\rho$ as follows
\begin{equation}
\rho_1 = \mathbb{E}[|\psi\...
5
votes
1answer
112 views
How powerful are boundedly many $T$-gates?
For a natural number $k$ (0 is a natural number), let $T_k$ be the collection of all languages that can be efficiently decided by quantum circuits consisting of Clifford gates and at most $k$ $T$-...
3
votes
0answers
28 views
If a hybrid classical+quantum algorithm can achieve quantum advantage, does this mean that the quantum part alone can?
Take for example a variational algorithm which has a classical optimization part and a quantum sampling part. In principle, the quantum part can be simulated by another classical computer given ...
8
votes
1answer
197 views
Why exactly are variational algorithms considered promising?
There is obviously a great deal of work happening at the moment on variational quantum algorithms. However, I'm struggling to understand why exactly are they considered promising? Looking through some ...
1
vote
1answer
32 views
Would quantum computers be more efficient at solving circular reference problems than classical computers?
A circular reference is when a certain value either refers to itself or a value refers to a value that refers to it. An example of a circular reference problem would be $x=f(x)$. One way to solve ...
2
votes
0answers
61 views
Spreading of entanglement with depth for Haar random states
Consider a Haar random quantum state of depth $d$. Consider any bipartition of this state. According to this paper (page $2$):
Haar-random states on $n$ qudits are nearly maximally entangled across
...
5
votes
0answers
40 views
Is there a practical architecture-independent benchmark suitable for adversarial proof of quantum supremacy?
Recent quantum supremacy claims rely, among other things, on extrapolation, which motivates the question in the title, where the word "adversarial" is added to exclude such extrapolation-...
4
votes
1answer
153 views
Spoofing XQUATH with the Feynman method
Consider the XQUATH conjecture for random quantum circuits, as mentioned here.
(XQUATH, or Linear Cross-Entropy Quantum Threshold Assumption). There
is no polynomial-time classical algorithm that ...
3
votes
0answers
43 views
Feynman method and polynomial time algorithm for XQUATH
Consider the Feynman algorithm for simulating quantum circuits, as given here.
Consider the XQUATH conjecture for random quantum circuits from here, given by
(XQUATH, or Linear Cross-Entropy Quantum ...
2
votes
0answers
47 views
Relation between approximate counting and sampling
Consider the following statement of Stockmeyer counting theorem.
Given as input a function $f:\{0, 1\}^{n} \rightarrow \{0, 1\}^{m}$
and $y \in \{0, 1\}^{m}$, there is a procedure that runs in ...
2
votes
0answers
84 views
When is a Quantum Computer Slower Than a Classical Computer?
Someone offhandedly mentioned to me that quantum computers are sometimes significantly (I guess they meant asymptotically) slower than classical computers.
Unfortunately, I didn't get any arguments ...
2
votes
1answer
82 views
Can I use Grover's algorithm on overlapping sets of qubits?
Let's say I have 3 qubits: $q_1,q_2,q_3$.
I want to apply Grover's algorithm on q1,q2, such that q1,q2 $\neq$ 10 and do the same for q2,q3, so that q2,q3 $\neq$ 11. The final possible combinations of ...
0
votes
1answer
100 views
How are quantum computers more powerful than classical computers? [duplicate]
I feel the answer to this question is just out of reach - I "understand" the implication that a quantum computer uses all combinations of bits simultaneously compared to a classic computer, ...
2
votes
1answer
102 views
Quantum hardness of XQUATH conjecture
Consider the XQUATH conjectures, as defined here (https://arxiv.org/abs/1910.12085, Definition 1).
(XQUATH, or Linear Cross-Entropy Quantum Threshold Assumption). There
is no polynomial-time ...
0
votes
1answer
147 views
What is the main advantage of using the Variational Quantum Eigensolver over a classical algorithm?
What is the main advantage of using the Variational Quantum Eigensolver (quantum computing) over a classical algorithm? I know a key fact is the speed-up, but how is this speed-up quantised.
1
vote
0answers
38 views
Has any analogue quantum simulator showed quantum advantage yet?
Quantum advantage/supremacy was achieved by Google using a quantum computer and more recently by Pan Jianwei's group using photons. So I was wondering, has any analog quantum simulator showed quantum ...
0
votes
1answer
65 views
Is it possible to design a Quantum Computing Advantage to deploy an application on the web?
I need to understand the frontier and practical applications of quantum computing.
Is it possible to design a Quantum Computing Advantage to deploy an application on the web, such as a browser, ...
2
votes
2answers
95 views
Generally speaking, are quantum speedups always due to parallelization of a given problem?
We know that quantum computers use the wave-like nature of quantum mechanics to perform interference. Sometimes we can use this interference to perform specific algorithms that will cause enough ...
0
votes
1answer
103 views
Quantum supremacy: shallow depth Haar random circuits and unitary designs
I had a confusion about shallow depth Haar random quantum circuits. In this paper, in Section B (related works), it is mentioned that Haar random quantum circuits form approximate $2$-designs only ...
3
votes
2answers
90 views
Q-means, QRAM and how it helps algorithmic speedup
I am trying to understand how QRAM will help improve algorithm performance. I am reading a paper on Q-means classification, but I have noticed that some other algorithms (Grovers) seem to have a ...
8
votes
2answers
154 views
Why does QAOA achieve quantum supremacy in an algorithmic sense?
In the paper Quantum Supremacy through the Quantum Approximate Optimization Algorithm the authors claim (last sentence of page 15):
"If [...] the QAOA outperforms all known classical algorithms ...
2
votes
1answer
202 views
Confusion about the output distribution of Haar random quantum states
Consider a Haar random quantum state $|\psi \rangle$. I was confused between two facts about $|\psi \rangle$, which appear related:
Consider the output distribution of a particular $n$-qubit $|\psi \...
7
votes
1answer
127 views
List of practical quantum computing algorithms that have speed-up higher than quadratic speed-up?
From this link (provided by @KAJ226's comment in this question), it appears as though current error correction methods are not enough to get practical speedup out of algorithms that have quadratic ...
2
votes
0answers
45 views
Can quantum computers speed up parsing?
Can quantum computers offer Grover-like speed ups in parsing of context-free languages? For instance, general CFLs can be parsed in $O(n^3)$ with standard algorithm like https://en.wikipedia.org/wiki/...
2
votes
1answer
101 views
Grover Algorithm vs Classical Search Algorithms
If Grover algorithm has a better speed than classical search algorithms, would it be an example of where Quantum computers outruns classical computers?
Can we use Grover Algorithm in real world ...
7
votes
1answer
150 views
Is Gaussian boson sampling (used for showing quantum advantage) a subcategory of the continuous variable approach?
I read about the photonic QC Jiŭzhāng that showed quantum advantage by Gaussian boson sampling. I read that boson sampling itself is a sub-universal technique of QC (where they use single-photon ...
5
votes
1answer
87 views
Could a new benchmark of quantum processors Q-Score by Atos be more useful than quantum volume?
A few days ago, Atos company published new benchmark for quantum computers. The benchmark is called Q-Score and it is defined as follows:
To provide a frame of reference for comparing performance ...
3
votes
2answers
275 views
Question regarding integration of Haar random state
I am trying to understand the integration on page 4 of this paper. Consider a Haar random circuit $C$ and a fixed basis $z$. Each output probability of a Haar random circuit (given by $|\langle z | C |...
0
votes
1answer
137 views
Comparing QSVM & Classic SVM on BigData. Quantum Supremacy
I work on comparing QSVM and Classic SVM (SKlearnSVM) with using Qiskit. I have to show
quantum supremacy at 400000-500000 samples but I don't get good results. I have problem with long time training ...
7
votes
1answer
101 views
Could random quantum circuits be efficiently approximately simulated?
Google's landmark result last year was to compute a task with a quantum computer that a classical computer could not compute, and they chose random circuit sampling. Part of their justification was ...
2
votes
1answer
61 views
How do quantum bits increase computational power?
I'm new to quantum computing, I'm learning how to use Qiskit. I'm trying to understand better how exactly the quantum characteristics of quantum computer help to increase its computational power. I ...
1
vote
1answer
110 views
Dirichlet distribution: posteriors and priors of distribution
Let $|\psi\rangle \in \mathbb{C}^{2n}$ be a random quantum state such that $ |\langle z| \psi \rangle|^{2} $ is distributed according to a $\text{Dirichlet}(1, 1, \ldots, 1)$ distribution, for $z \in \...
1
vote
0answers
46 views
What is the reason for the exponential speed-up of quantum computers? [duplicate]
In quantum computers the following two effects should be seen:
If an operator acts on an arbitrary qubit $Q_n$ of a quantum system $S$ consisting of several qubits than we get a new quantum system $S'...
7
votes
2answers
443 views
What is the advantage of quantum machine learning over traditional machine learning?
Why exactly is machine learning on quantum computers different than classical machine learning? Is there a specific difference that allows quantum machine learning to outperform classical machine ...
2
votes
0answers
32 views
When we do a linear fit, what is the correlation coefficient of the estimated parameters?
In Google's quantum supremacy experiment, supplementary Section VIIIH, they calculate the correlation coefficient of the linear fit coefficients $p_0$,$p_1$. I can't figure out the definition of this ...
3
votes
1answer
138 views
Does quantum computers give any advantage over classical computers in Sudoku?
To my basic knowledge I know that solving a generalized Sudoku problems is an NP-complete problem so, is there any possible way quantum computers give an advantage over classical computers in this ...
4
votes
1answer
118 views
Is the BB84 protocol an example of "quantum supremacy"?
This is a fairly broad question, I hope it fits here. I am wondering if the BB84 protocol is an example of "quantum supremacy", ie. something a quantum computer can do but something that is assumed a ...
0
votes
1answer
129 views
How does Deutsch Oracle shows quantum supremacy?
I learnt from this lecture (at 33:20) that Deutsch Oracle is way faster on quantum computers than on classical computers. However, it seems to me that this is just due to smart structuring of input ...
8
votes
1answer
475 views
Why Google has used $\sqrt{X}$ and $\sqrt{Y}$ instead of $X$ and $Y$ in supremacy experiment?
In supremacy experiment Google has used $\sqrt{X}$ and $\sqrt{Y}$ as two of their single qubit gates (paper).
So My questions are:
Is there any specific reason for choosing these gates and not $X$...
7
votes
3answers
111 views
Is there quantum advantage to be had with a D-Wave computer in 2020?
I've seen a lot of excitement in the popular press about the computers made by D-Wave Systems, but when I dig deep the only practical things that I can figure out that one can do with the computer are ...
3
votes
1answer
94 views
What is the role of choosing the single-qubits randomly in Google quantum supremacy experiment?
In supremacy paper and part D of section VII of supplementary information (below), it is said that there is a pseudo-random number generator that is initialized with a seed called $s$; And then the ...
7
votes
1answer
182 views
What did exactly Google do in simulating a random quantum circuit on a classical computer in supremacy experiment?
I've been working on Google quantum supremacy paper for quite some time now and I have a problem in understanding how exactly they simulate their actual random quantum circuit on a classical computer.
...
8
votes
2answers
242 views
Decomposing Hamiltonian into qubit model representation
One of the main applications of VQE is its application to find the approximation to the ground state energy (smallest eigenvalue of the Hamiltonian) for a particular molecule through an iterative ...
2
votes
1answer
53 views
In Google's Quantum Supremacy experiment, what if we use $\theta=45°$ for two-qubit $f_{sim}$ gates?
In Google's Quantum Supremacy experiment, they use $f_{sim}$(fermionic-simulation) gates with $\theta=90°$ and $\phi=30°$ as their two-qubit gates. What if we use $\theta=45°$ for the two-qubit $f_{...
1
vote
1answer
136 views
What is the difference between classical and quantum computers as well as computing (permuting) itself?
Theoretically and for sure physically (I know the quantum physics behind it) I know something about it. But not that much. That's why I ask the question here. I'm very interested. The only answer to ...
2
votes
1answer
218 views
Interpretations of quantum computing power [closed]
Over the years I encountered different explanations of quantum computing advantage over classical computers. But I am not sure which explanations are in fact valid and which are not.
Quantum ...
