New answers tagged complexity-theory
0
votes
Equivalence checking of quantum circuits up to error
Sam's link to the posting on tcs answers the OP's question - but here's some other comments that were hinted at here and there.
The exact classical problem is coNP-complete as this reduces to ...
Community wiki
4
votes
Accepted
Why is it hard to prove complexity bounds for variational algorithms?
The goal of a variational quantum algorithm is to minimize a cost function $f(\theta)$ over $\theta$ where evaluating $f$ involves the output of a quantum computer. In short, the quantum computer ...
6
votes
Why is it hard to prove complexity bounds for variational algorithms?
Looking for a solution by following a heuristic criteria means that you are proceeding by intuition, which has no proof of being correct nor efficient. You propose a heuristic, you show the results, ...
Top 50 recent answers are included
Related Tags
complexity-theory × 275quantum-algorithms × 83
bqp × 27
quantum-circuit × 20
speedup × 19
qma × 19
quantum-gate × 18
grovers-algorithm × 17
quantum-advantage × 17
circuit-construction × 14
resource-request × 14
hamiltonian-simulation × 14
classical-computing × 14
quantum-state × 10
simulation × 10
oracles × 10
mathematics × 9
quantum-fourier-transform × 8
random-quantum-circuit × 8
entanglement × 7
shors-algorithm × 7
cryptography × 7
nielsen-and-chuang × 6
deutsch-jozsa-algorithm × 6
optimization × 5