Entangling power and quantum circuit complexity

Understand

Notions of circuit complexity and cost play a key role in quantum computing and simulation where they capture the (weighted) minimal number of gates that is required to implement a unitary.

• Similar notions also become increasingly prominent in high energy physics in the study of holography.
• While notions of entanglement have in general little implications for the quantum circuit complexity and the cost of a unitary, in this note, we discuss a simple such relationship when both the entanglement of a state and the cost of a unitary take small values, building on ideas on how values of entangling power of quantum gates add up.
• This bound implies that if entanglement entropies grow linearly in time, so does the cost.