Skip to main content
Share Your Experience: Take the 2024 Developer Survey
7 votes

What is the computational power of classically mixed states?

(The other answers and comments have already touched on the main points, but I have to take the opportunity to answer in my own words.) What you're describing is known as randomized or probabilistic ...
John Watrous's user avatar
  • 6,097
5 votes

Are Quantum Computers Bad at Addition?

Yes, current quantum computers are bad at addition. A 5-bit adder requires several dozen two-qubit gates. Current state of the art two-qubit gate error rates are between 0.1% and 1%. At the time I am ...
Craig Gidney's user avatar
  • 37.6k
4 votes

Is there a fast sparse Hadamard transform?

This partial answer provides a simple algorithm that generalizes the $k=1$ case and exploits sparsity promise to beat the Walsh-Hadamard transform when $k$ is constant. Specifically, the algorithm ...
Adam Zalcman's user avatar
  • 22.9k
4 votes
Accepted

Classical computation required in Shor's algorithm: are they heavy?

My guess is that a laptop would be sufficient for computing the lookup tables and delayed choice fixups and various other things-that-aren't-error-correction on the fly. There's tens of microseconds ...
Craig Gidney's user avatar
  • 37.6k
2 votes

Simulating any fixed time classical circuit in time poly(t) on a quantum computer

In talking to some professors I found the answer myself. The statement does indeed hold (and is probably proven using the universality of the Toffili gate). The reason I was confused with the binary ...
Thyrum's user avatar
  • 61
2 votes

How does the Curry-Howard correspondence apply to quantum programs?

A formulation of the logic underlying quantum theory (and quantum systems), posed by Isham et al., that supersedes the older (non-distributive) quantum logic formulation associated with von Neumann, ...
NinjaDarth's user avatar
2 votes

Quantum Computing and Overhead

The books never talk about the overhead introduced by the Hadamard gates because the speedup of Grover's search algorithm is defined specifically in terms of the number of calls to the oracle (the ...
Mariia Mykhailova's user avatar
2 votes

What is the computational power of classically mixed states?

"Nondeterministic" as used in theoretical computer science is a legacy term popularized from at least the 70's, and imagines a special Turing machine (that's the machine with an infinite ...
Mark Spinelli's user avatar
1 vote
Accepted

How should large quantum computers use Clifford simulators like Stim?

There are potential uses for Clifford simulation even with a large scale quantum computer available. To help it run more smoothly. For example, in Daniel Litinsky's "game of surface codes" ...
Craig Gidney's user avatar
  • 37.6k
1 vote
Accepted

Why are quantum computing networks so far behind classical methods?

Quantum communication is a field where theory is far beyond experiment. Entanglement theory lies at the heart of computational complexity and entanglement is what really separates quantum mechanics ...
sycramore's user avatar
  • 325
1 vote
Accepted

What does Quantum Circuit Wires and Separated mean?

For most qubit modalities quantum wires are best thought of as time while quantum gates are best thought of as electromagnetic pulses applied to individual qubits. This is in contrast to classical ...
Mark Spinelli's user avatar
1 vote

Could a quantum computer simulate any system based on different types of logic?

Quantum computers can simulate different logical systems that are used in Classical Computers, but the effectiveness of the simulation depends on the problem at hand. With the help of X, CNOT, CCNOT ...
Ausaf Hussain Akhlaq's user avatar
1 vote

Is it possible to "calculate" the absolute value of a permanent using Boson Sampling?

Just a couple of more comments to expand on the already thorough answers. Initially relating to the error associated with the calculation of the permanent, much of the theory of the complexity of ...
Mark Spinelli's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible