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.
106
questions
3
votes
2
answers
2k
views
What is the fastest quantum computational algorithm by which quantum computer speed up than classic one?
What is the fastest quantum computational algorithm by which quantum computers speed up than classic one? Of course, those speedup algorithms have to be proven.
5
votes
2
answers
173
views
Can we use cryptocurrency mining to verify claims of quantum advantage?
Beginning with the earlier works of work of Brakerski et al. or the more recent results of Kahanamoku-Meyer et al., interactive proofs of quantum advantage entail a classical verifier (Vicky) ...
- 7,921
9
votes
1
answer
521
views
Any simple description of a circuit for Yamakawa-Zhandry algorithm?
Recently, popular sources (including Aaranson's blog and Quanta Magazine) have made it look like the recent Yamakawa-Zhandry algorithm is akin to Shor's algorithm, in the sense that it could ...
- 1,584
8
votes
0
answers
140
views
Status of Google's quantum supremacy claim 2022
More than a year ago a couple of scientists made a splash by presenting a classical algorithm that took less than a week to simulate Sycamore's circuits on a small GPU cluster. Also, their simulations ...
- 1,161
7
votes
1
answer
115
views
What arguments point towards D-Wave devices being potentially useful?
I'm looking for any evidence pointing towards D-Wave's approach to quantum computation being promising to achieve any sort of computational advantage with respect to classical devices.
Note that I'm ...
glS♦
- 19.6k
3
votes
3
answers
247
views
What are quantum computers actually doing today?
I am curious about what are quantum computers actually doing today. I seem to only be able to find information online about what they could be used for in the future (i.e. breaking encryption, quantum ...
- 31
2
votes
0
answers
56
views
Understanding the supremacy regime plot in Google's "Quantum supremacy using a programmable superconducting processor"
I was going through the Google's 2019 paper & had difficulties regarding some details.
How are they calculating XEB in quantum supremacy regime? To calculate the XEB,we also need the ideal ...
- 21
2
votes
1
answer
58
views
Is there any rigorous proof that Quantum Annealing provides a quantum advantage?
Is there any rigorous proof that Quantum Annealing (QA) is of any benefit (e.g. in terms of time to optimal solution, convergence rate, etc.) for a specific problem? Or any empirical evidence for the ...
- 415
2
votes
3
answers
123
views
Why do we need physical qubit if qubit can be simulated?
I do not see any advantage in constructing very costly and imperfect physical qubit while this qubit can be simulated with using conventional computer memory (noise-free).
So what is the purpose when ...
- 379
2
votes
1
answer
43
views
I have question about cost of 'modular multiplication unitary' in Shor's algorithm
Here modular multiplication unitary means $U_a : |s\rangle \to|as\mod N\rangle$.
My main question is, can the modular multiplication unitary $U_a$ can be constructed in time polynomial in the number ...
- 21
0
votes
0
answers
42
views
What tasks are quantum computers good at that classical computers are not?
At this stage, a large number of theoretical proofs have made us vaguely aware of the particularity of quantum computers. But what tasks are quantum computers good at that classical computers are not? ...
- 388
2
votes
1
answer
110
views
Exponential advantage with Hadamard test
My question is the following:
Let's assume that the only algorithm a quantum computer would be able to implement is the Hadamard test, which circuit is represented below, would we say that compared to ...
5
votes
1
answer
97
views
Quantum advantage without phase?
I'm wondering if one can (potentially) get any quantum advantage with $R_y$ single-qubit rotations and $CNOT$s only?
(Note that I don't care about having a universal quantum computer.)
- 1,488
3
votes
2
answers
148
views
Are qubits just analog, continuous classical bits? [duplicate]
Topologically, classical bits (cbits) are essentially special cases of qubits restricted to the poles of the Bloch sphere. However, this restriction doesn't seem to be classical per se, but is simply ...
- 131
6
votes
2
answers
191
views
Proven quantum advantage (in the algorithmic sense) without error correction (for specific algo, or noise models)
I would like to know if there are some specific class of quantum algorithms, under some hypotheses about the noise model behind the quantum gates for which we know that there is an exponential ...
2
votes
2
answers
76
views
Derivation of the linear cross entropy
I'm looking at cross-entropy benchmarks and there's much that I'm reading at the moment but I'm stuck on one detail: how to derive the linear cross-entropy formula from the cross-entropy formula.
The ...
5
votes
2
answers
872
views
Are there quantum algorithms showing a double exponential advantage?
I would like to know if there are known quantum algorithms that provide a double exponential advantage compared to the best known classical algorithms.
More precisely, if the characteristics of the ...
3
votes
1
answer
204
views
What exactly makes VQE faster than classical optimization?
I have been trying to understand Variational Quantum Eigensolver (VQE), particularly from the non-linear binary programming perspective. But after reading a few resources I'm still confused about ...
- 131
2
votes
0
answers
51
views
What is the explicit best known quantum algorithm for LWE?
Consider the learning with errors(LWE) problem which is known to be hard for quantum computers.
Let $q \geq 2$ be a prime integer. Consider us being given (polynomially many samples of) either:
$$A, ...
- 273
3
votes
1
answer
190
views
Schmidt vectors for random quantum states
Consider a random quantum circuit $U$ over $n$ qubits, drawn from the Haar measure. Consider the quantum state
$$|\psi\rangle = U |0^{n}\rangle.$$
Now, partition $n$ into two and consider the Schmidt ...
- 963
5
votes
1
answer
53
views
Anticoncentration for two independent random quantum circuits in parallel
Consider two Haar random $n$ qubit unitaries, $U_1$ and $U_2$. Consider the quantum state
$$|\psi\rangle = (U_1 \otimes U_2) |0^{2n}\rangle. $$
Let $p_x = |\langle x| \psi \rangle|^{2}$, for $x \in \{...
- 273
3
votes
0
answers
147
views
Reduced density matrix of a Haar random state and its Schmidt decomposition
Consider a Haar random quantum state $|\psi\rangle$. Note that
$$\rho =\mathbb{E}[|\psi\rangle\langle \psi|] = \frac{\mathbb{I}_{n}}{2^{n}}.$$
$\mathbb{I}_n$ is the identity operator on $n$ qubits. ...
- 963
4
votes
1
answer
147
views
Random quantum states and Schur-Weyl duality
Consider the following density matrix over $n$ qubits, with $C$ being a single qubit operator:
$$
\rho_{n} = \int_{C \sim \text{Haar}} \big(C|0\rangle\langle0|C^\dagger\big)^{\otimes n} dC.
$$
Let's ...
- 963
1
vote
0
answers
34
views
Optimality of the SWAP test versus weak Schur sampling for testing unitarily invariant properties
Consider the following setting.
I am either given the density matrix $|\psi\rangle \langle \psi|^{\otimes k}$ or the density matrix $\frac{\mathbb{I}^{\otimes k}}{2^{nk}}$, where $\mathbb{I}$ is the $...
- 963
2
votes
1
answer
150
views
At what depth and for what architecture are random quantum circuits $1$-designs?
I was confused about something related to quantum $1$ designs.
Let us recap two facts we know about random circuit ensembles that form a $1$ design.
$1$ design, for a quantum circuit over $n$ qubits, ...
- 963
9
votes
3
answers
889
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
1
answer
122
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 ...
- 111
2
votes
1
answer
94
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 ...
- 963
13
votes
2
answers
136
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 ...
- 131
2
votes
1
answer
166
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\...
- 963
5
votes
1
answer
146
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$-...
- 227
3
votes
0
answers
39
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 ...
- 1,283
11
votes
1
answer
484
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,283
1
vote
1
answer
256
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 ...
- 143
2
votes
0
answers
99
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
...
- 963
7
votes
0
answers
56
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-...
- 326
4
votes
1
answer
163
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 ...
- 963
3
votes
0
answers
51
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 ...
- 963
2
votes
0
answers
88
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 ...
- 963
2
votes
0
answers
117
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 ...
- 121
2
votes
1
answer
110
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
1
answer
257
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, ...
- 101
3
votes
1
answer
119
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 ...
- 963
0
votes
1
answer
319
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.
- 43
1
vote
0
answers
56
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 ...
- 11
0
votes
1
answer
71
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, ...
- 9
2
votes
2
answers
142
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 ...
- 1,059
0
votes
1
answer
244
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 ...
- 963
3
votes
2
answers
171
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 ...
- 323
8
votes
2
answers
372
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 ...
- 415