New answers tagged complexity-theory
0
votes
Can a polynomial-sized superposition of computational basis states be prepared with a polynomial-sized quantum circuit?
I think so. Let me rephrase what you're asking and hopefully it captures what you want: Suppose you have $N$ distinct circuits $U_i$ such that $U_i|0\rangle = |\psi_i\rangle$, each with complexity $O(...
1
vote
Accepted
Definitions of a quantum circuit's depth and connectivity
I would like to give explicit definitions of the circuit depth and connectivity.
I assume that the meaning of terms like vector state, quantum circuit, wires, and 1- and 2-qubit gates is understood.
I'...
4
votes
Definitions of a quantum circuit's depth and connectivity
The traditional definitions of classical Boolean circuits work perfectly well here: https://en.wikipedia.org/wiki/Boolean_circuit. This is the definition that gives you Niel de Beaudrap's definition.
...
2
votes
Definitions of a quantum circuit's depth and connectivity
Let me try to provide a more precise definition of connectivity in a quantum circuit.
Every quantum circuit defines a graph (network), with vertices (nodes) given by qubits. There is an edge $q_1 q_2$ ...
Top 50 recent answers are included
Related Tags
complexity-theory × 209algorithm × 74
speedup × 18
bqp × 18
quantum-advantage × 17
qma × 17
quantum-gate × 15
classical-computing × 14
circuit-construction × 12
grovers-algorithm × 12
resource-request × 11
quantum-circuit × 9
mathematics × 8
random-quantum-circuit × 8
quantum-state × 7
simulation × 7
hamiltonian-simulation × 7
cryptography × 7
oracles × 7
shors-algorithm × 6
entanglement × 5
nielsen-and-chuang × 5
quantum-fourier-transform × 5
deutsch-jozsa-algorithm × 5
gate-synthesis × 4