6
votes
Accepted
Can a quantum computer count up by 1 faster than a classical computer?
A classical computer takes less than a nanosecond to increment a 64 bit integer.
A superconducting quantum computer takes 10-100 nanoseconds to perform a CNOT gate, the reversible equivalent of a XOR ...
- 33.3k
3
votes
Accepted
How does one convert a truth table to a square permutation matrix?
In the standard convention, a state $|\psi\rangle$ is a column vector and operator $M$ is left multiplied with the state for evolution, i.e $M|\psi\rangle = |\phi\rangle$.
In this convention, the (row,...
2
votes
Accepted
Can a classical circuit of size $2^k$ be modelled by a quantum circuit of size $k$ or vice versa?
Before answering let me generalize and formalize your framing a bit, so that I can say things concretely without fussing over details. I believe the heart of your question concerns the power of an ...
- 595
2
votes
Deutsch-Jozsa Algorithm - classical solution
As discussed in the comments, your main mistake is applying $F$ to $\sum_{x=0}^{2^n-1} x$ in the classical case. Unlike the quantum case, there's no superposition of classical bitstrings, and such an ...
- 2,372
2
votes
Accepted
Where is "quantum search" in the complexity hierarchy?
Grover's algorithm is best thought of as solving an oracle problem, using the square-root of the number of oracle calls that a classical computer would use.
Grover originally framed the problem as ...
- 10.7k
2
votes
Accepted
Is there something wrong with cross-entropy benchmarking, or is it still considered as a reasonable path towards quantum supremacy?
I think that the original rationale for using the linear cross-entropy (XEB) score as a metric to claim quantum computational supremacy was valid, but we may now be at a point now where the continued ...
- 10.7k
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 ...
- 190
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 ...
- 10.7k
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 ...
1
vote
Prove that classical counting requires $k=\Omega(N)$ oracle calls
I solved this problem using Chebyshev's inequality, $p(|S-E(S)|\geq\lambda\Delta(S))\leq1/\lambda^2$. To obtain a probability at least 3/4, let $\lambda=2$. We know that
$$p\left(|S-E(S)|\leq2\Delta ...
- 53
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 ...
- 10.7k
Only top scored, non community-wiki answers of a minimum length are eligible