For questions about schemes to prove that quantum devices can, at least in principle, be exponentially more efficient than their classical ones. Also often referred to as "quantum computational advantage" or "quantum supremacy". Typical examples are sampling problems such as boson sampling and random circuit sampling.

133 questions
Filter by
Sorted by
Tagged with
1 vote
49 views

### Are there any instances of the "Lights Out" puzzle only solvable with square-root-of-NOT gates?

TL/DR: Can we solve a classically unsolvable instance of "Lights Out" when the lightbulbs neighboring the switch that we flip see a $\sqrt X$ gate, instead of being fully negated? If so, ...
• 12.8k
1 vote
250 views

### Exponential Quantum Speedup for the Traveling Salesman Problem - where is the catch?

Such an article claims that an NP-complete problem can be solved efficiently. Is it real? I noticed that they prepare a state $|0\rangle\langle0|+|1\rangle\langle1|$ on an ancilla, which is impossible ...
• 1,482
1 vote
49 views

### What is the intuition behind achieving Quantum advantage in simulating non-hermitian dynamics using Quantum computer?

There have been several works on simulating ODE for classical systems like here and here. They are quantum techniques to solve the ODE related to classical systems. A generic methodology is: To solve ...
• 681
1 vote
22 views

### Quantum code for Substitution Box

How to write quantum code(qiskit) for n-bit Substitution Box with minimum number of gate and qubit.
33 views

### Parallelism of two or more quantum machines

Suppose I have 2 quantum machines: The first is 2 qubits machine and the second is 4 qubits. Is there a way to parallelize these machines and get a result as if I had 6 quibts machine? Is there a ...
• 163
172 views

### What is the computational power of classically mixed states?

It is my understanding that mostly one considers as the "classical" state, a single bit string (eg 00101), with a discrete number of deterministic gates applied to it. All computers that ...
• 301
1 vote
41 views

### What are problems so computationally difficult that they'll likely only be solved with quantum computers? [duplicate]

Of course, there are the exceedingly well-known examples of this, eg. breaking RSI encryption, possibly protein folding, etc. What are some more obscure or overlooked ways that the greater computing ...
• 21