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.
59
questions
2
votes
2answers
80 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
46 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 ...
2
votes
2answers
58 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 ...
7
votes
2answers
93 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
132 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 \...
6
votes
1answer
102 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
35 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/...
1
vote
1answer
49 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
113 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 ...
4
votes
1answer
47 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
1answer
135 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
95 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
88 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
55 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
96 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
33 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'...
2
votes
0answers
30 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
124 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
100 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
52 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
417 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
89 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
73 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 ...
6
votes
1answer
135 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.
...
4
votes
1answer
142 views
Decomposing Hamiltonian into qubit model representation
One of the main application of VQE is its application to find the approximation to the ground state energy (smallest eigenvalue) for a particular molecule through an iterative method.
To be able to ...
2
votes
1answer
49 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
70 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
213 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 ...
3
votes
0answers
54 views
Boson Sampling with a single beamsplitter
In Boson Sampling as first proposed by Aaronson and Arkhipov in arxiv.org/abs/1011.3245, the interferometer is made up of phase shifters and beamsplitters. As these gates are universal, drawing the ...
3
votes
3answers
385 views
How to distinguish quantum random from classical random?
Given two sets of $N$ uniformly random binary bitstrings of size $m$, such as $$(x_0,x_1,...,x_m) \space \forall x_i \in \{0,1\}.$$
One generated from a quantum device and the other generated by ...
2
votes
1answer
122 views
What is the problem in demonstrating quantum supremacy?
I am new to the quantum world and it's computing. But it accidentally hit in my mind that DWave built a quantum computer with 2000 qubits which can be use to simulate the whole observable universe or ...
4
votes
2answers
179 views
How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense?
Note: This has been cross-posted to CS Theory SE.
If we assume $\mathsf{BQP} \neq \mathsf{BPP}$, then we can say with reasonable certainty that Google's random sampling experiment falsifies the ...
2
votes
1answer
104 views
How does successfully sampling from a random quantum circuit invalidate the Extended Church-Turing Thesis?
According to these lecture notes from Berkeley, the Extended Church-Turing Thesis (ECT) asserts that:
...any "reasonable" model of computation can be efficiently simulated on a standard model such ...
4
votes
1answer
472 views
Making sense of the Sycamore's computing prowess - power consumption
I came here after reading about the announcement regarding the Sycamore processor and Google's Quantum Supremacy claim. I am hung up on several key things and I am hoping that I could find those ...
19
votes
2answers
4k views
What does Google's claim of “Quantum Supremacy” mean for the question of BQP vs BPP vs NP?
Google recently announced that they have achieved "Quantum Supremacy": "that would be practically impossible for a classical machine."
Does this mean that they have definitely proved that BQP ā BPP ?...
6
votes
1answer
319 views
Why does Google's quantum processor outperform IBM's?
I understand that both have 53 qubit devices, yet it is Google that has demonstrated quantum supremacy (although IBM refutes this!). I'm not sure if this is true but it seems like IBM cannot replicate ...
13
votes
3answers
460 views
Why do the IBM and Google processors both have 53 qubits?
As I understand from this IBM post both the IBM and Google teams have independently built 53-qubit processors. What is the significance of the number 53? It is purely coincidental, or is there a ...
7
votes
1answer
202 views
Are 20 repetitions of Sycamore's one- and 2-qubit gates sufficient to produce a uniformly random state?
In the answer to this question about random circuits, James Wootton states:
One way to see how well we [fully explore the Hilbert space] is to focus on just randomly producing $n$ qubit states. ...
5
votes
3answers
2k views
Quantum Supremacy: Some questions on cross-entropy benchmarking
I was skimming through the Google quantum supremacy paper but got stuck on this section:
For a given circuit, we collect the measured bit-strings $\{x_i\}$ and compute the linear XEB fidelity [24-26, ...
7
votes
1answer
276 views
Number of qubits to achieve quantum supremacy?
Google's Sycamore paper describes achieving quantum supremacy on a $53$-qubit quantum computer. The layout of Sycamore is $n=6\times 9=54$ nearest neighbors, with one qubit nonfunctional. They apply ...
5
votes
1answer
530 views
Understanding Google's āQuantum supremacy using a programmable superconducting processorā (Part 3): sampling
In Google's 54 qubit Sycamore processor, they created a 53 qubit quantum circuit using a random selection of gates from the set $\{\sqrt{X}, \sqrt{Y}, \sqrt{W}\}$ in the following pattern:
...
7
votes
1answer
599 views
Understanding Google's āQuantum supremacy using a programmable superconducting processorā (Part 2): simplifiable and intractable tilings
In Google's 54 qubit Sycamore processor, they created a 53 qubit quantum circuit using a random selection of gates from the set $\{\sqrt{X}, \sqrt{Y}, \sqrt{W}\}$ in the following pattern:
...
10
votes
2answers
639 views
Understanding Google's āQuantum supremacy using a programmable superconducting processorā (Part 1): choice of gate set
I was recently going through the paper titled "Quantum supremacy using a programmable superconducting processor" by NASA Ames Research Centre and the Google Quantum AI team (note that the paper was ...
3
votes
2answers
300 views
Do quantum supremacy experiments repeatedly apply the same random unitary?
It is my understanding that, given a quantum computer with $n$ qubits and a way to apply $m$ single- and 2-qubit gates, quantum supremacy experiments
Initialize the $n$ qubits into the all-zero's ket ...
5
votes
2answers
144 views
What is the point of building arithmetic circuits in a quantum computer?
My question simply is the following: is there any interests in building arithmetic circuits such as adders or multiplier on a quantum computer?
I'm asking this because it seems that classical ...
6
votes
0answers
57 views
Strong vs weak simulations and the polynomial hierarchy collapse
(Edited to make the argument and the question more precise)
An argument for quantum computational "supremacy" (specifically in Bremner et al. and the Google paper) assumes that there exists a ...
8
votes
4answers
951 views
Grover algorithm for a database search: where is the quantum advantage?
I have been trying to understand what could be the advantage of using Grover algorithm for searching in an arbitrary unordered database D(key, value) with N values instead of a classical search.
I ...
5
votes
1answer
369 views
What is the HOG test and how would it help proving quantum supremacy?
Proposed experiments in achieving quantum supremacy, such as with BosonSampling or using random circuits, have been described as using a (not necessarily Turing complete) quantum computer to perform ...
5
votes
1answer
533 views
What exactly makes quantum computers faster than classical computers?
What feature of a quantum algorithm makes it better than its classical counterpart? Are quantum computers faster than classical ones in all respects?
4
votes
0answers
91 views
Simulating quantum computers using anyon braiding
I am new to the concept of topological quantum computation (TQC).
Recently I have been thinking about simulating a quantum computer on a classical computer. I know that if I use merely the unitary ...
