Can we quantify the "degree of quantumness" in a quantum algorithm ?

Question

Entanglement is often held up as the key ingredient that makes quantum algorithms well... quantum, and this can be traced back to the Bell states that destroy the idea of quantum physics as a hidden-state probabilistic model. In quantum information theory (from my rather weak understanding), entanglement can also be used as a concrete resource that bounds the ability to do certain kinds of coding.

But from other conversations (I recently sat on the Ph.D committee of a physicist working in quantum methods) I gather that entanglement is difficult to quantify, especially for mixed-state quantum states. Specifically, it appears hard to say that a particular quantum state has X units of entanglement in it (the student's Ph.D thesis was about trying to quantify amounts of entanglement "added" by well known gate operations). In fact, a recent Ph.D thesis suggests that a notion termed "quantum discord" might also be relevant (and needed) to quantify the "quantumness" of an algorithm or a state.

If we want to treat entanglement as a resource like randomness, it's fair to ask how to measure how much of it is "needed" for an algorithm. I'm not talking about complete dequantization, merely a way of measuring the quantity.

So is there currently any accepted way of measuring the "quantumness" of a state or an operator, or an algorithm in general ?

Answer 1

It depends on the context.

1. For quantum algorithms, the situation is tricky, since for all we know, P=BPP=BQP. So we can never say that a quantum algorithm does something that no classical algorithm can do; only something that a naive simulation would have trouble with. For example, if a quantum circuit is drawn as a graph, then there is a classical simulation that runs in time exponential in the treewidth of the graph). So treewidth can be thought of as an upper bound to 'quantumness', although not a precise measure.

   Sometimes measuring quantumness in algorithms gets conflated with trying to measure the amount of entanglement produced by an algorithm, but we now think that a noisy quantum computer could have computational advantages over classical computer even with so much noise that its qubits are never in an entangled state (e.g. the one clean qubit model). So the consensus is now more on the side of thinking of the quantumness in quantum algorithms as related to the dynamics rather than the states generated along the way. This can help explain why 'dequantizing' is not likely to be generally possible.

2. For bipartite quantum states, where the context is two-party correlations, we have many many good measures of quantumness. Many have flaws, like being NP-hard, or not additive, but nevertheless we have a pretty sophisticated understanding of this situation. Here is a recent review.

3. There are other contexts, such as when we have a quantum state and would like to choose between different incompatible measurements. In this setting, there are uncertainty principles that tell us things about how incompatible the measurements are. The more incompatible the measurements are, the more 'quantum' a situation we have. This is related to cryptography and zero-error capacities of noisy channels, among many other things.

Answer 2

Aram's answer is excellent, so please don't take me posting an answer as in anyway disagreeing with what he has said, merely supplementing it.

I think perhaps an additional point to raise is that there is not simply one type of entanglement. Bipartite entanglement is extremely well understood, as Aram has pointed out. There are a number of different measures, but for pure states (i.e. states which are distinct quantum states rather than probabilistic ensembles of quantum states) these measures all tend to be monotonic functions of one another. For tripartite and above, however, the situation is different. Let me give you an example of this. For 3 qubits you have two distinct types of entanglement: 1) arising from GHZ-like relations $\frac{1}{\sqrt{2}}\mid 000\rangle + \frac{1}{\sqrt{2}}\mid 111\rangle$ and 2) arising from w-state like relations $\frac{1}{\sqrt{3}}\mid 100\rangle + \frac{1}{\sqrt{3}}\mid 010\rangle + \frac{1}{\sqrt{3}}\mid 001\rangle$. The thing to notice here is that you cannot transform between these two states with purely local operations, and so you need to count two separate quantities when measuring the entanglement of a tri-partite state. As we look at more and more partitions this number increases.

This is particularly pertinent to the question as asked, because it would seem to rule out any monotonic measure of "quantumness" based on entanglement measures.

Answer 3

A more complexity theoretical point of view can be found in Sec. 8 of R. Josza's paper An introduction to measurement based quantum computation. He states the following:

The measurement based models provide a natural formalism for separating a quantum algorithm into "classical parts and quantum parts".

He also states a conjecture on the amount of "quantumness" needed by a BQP algorithm:

Conjecture: Any polynomial time quantum algorithm can be implemented with only $O(\log n)$ quantum layers interspersed with polynomial time classical computations.

See the paper for a clear explanation of quantum layer and of the model in general. The conjecture is still open and I guess this is a nice way to quantify the amount of "quantumness" of an algorithm, at least from the computational complexity side.