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.

Filter by
Sorted by
Tagged with
1 vote
1 answer
32 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 ...
user avatar
0 votes
0 answers
40 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? ...
user avatar
2 votes
1 answer
86 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 ...
user avatar
4 votes
1 answer
81 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.)
user avatar
  • 1,388
3 votes
2 answers
128 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 ...
user avatar
  • 131
6 votes
2 answers
181 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 ...
user avatar
2 votes
2 answers
43 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 ...
user avatar
5 votes
2 answers
831 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 ...
user avatar
3 votes
1 answer
115 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 ...
user avatar
2 votes
0 answers
38 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, ...
user avatar
3 votes
1 answer
175 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 ...
user avatar
4 votes
1 answer
45 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 \{...
user avatar
3 votes
0 answers
112 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. ...
user avatar
3 votes
1 answer
103 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 ...
user avatar
1 vote
0 answers
32 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 $...
user avatar
2 votes
1 answer
115 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, ...
user avatar
7 votes
3 answers
815 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 ...
user avatar
1 vote
1 answer
101 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 ...
user avatar
2 votes
1 answer
72 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 ...
user avatar
12 votes
2 answers
115 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 ...
user avatar
  • 121
2 votes
1 answer
126 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\...
user avatar
5 votes
1 answer
131 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$-...
user avatar
  • 207
3 votes
0 answers
36 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 ...
user avatar
11 votes
1 answer
371 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 ...
user avatar
1 vote
1 answer
35 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 ...
user avatar
2 votes
0 answers
82 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 ...
user avatar
5 votes
0 answers
43 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-...
user avatar
  • 306
4 votes
1 answer
159 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 ...
user avatar
3 votes
0 answers
48 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 ...
user avatar
2 votes
0 answers
72 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 ...
user avatar
2 votes
0 answers
96 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 ...
user avatar
2 votes
1 answer
104 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 ...
user avatar
0 votes
1 answer
169 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, ...
user avatar
  • 101
2 votes
1 answer
115 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 ...
user avatar
0 votes
1 answer
252 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.
user avatar
  • 43
1 vote
0 answers
49 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 ...
user avatar
  • 11
0 votes
1 answer
67 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, ...
user avatar
  • 9
2 votes
2 answers
115 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 ...
user avatar
0 votes
1 answer
178 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 ...
user avatar
3 votes
2 answers
139 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 ...
user avatar
  • 293
8 votes
2 answers
284 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 ...
user avatar
3 votes
1 answer
296 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 \...
user avatar
8 votes
1 answer
162 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 ...
user avatar
2 votes
0 answers
47 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/...
user avatar
  • 147
3 votes
1 answer
207 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 ...
user avatar
  • 111
7 votes
1 answer
181 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 ...
user avatar
  • 145
6 votes
1 answer
114 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 ...
user avatar
3 votes
2 answers
460 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 |...
user avatar
0 votes
1 answer
181 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 ...
user avatar
  • 33
7 votes
1 answer
117 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 ...
user avatar
  • 1,546