Quanta Magazine: The Quest to Quantify Quantumness • Hacker News Board

Re: Quanta Magazine: The Quest to Quantify Quantumness

#11

Post by eigenket » Sat, Oct 21, 2023, 12:31 PM UTC

dabeddabed wrote: post #10

eigenket wrote: post #9

Earlier quoted context omitted.

The obvious dumb classical algorithm for simulating a quantum computer with n qubits runs in O(2^n) time and space. Since 2^log(n) = n is polynomial it follows that "log-space" quantum circuits, I.e. quantum circuits with a logarithmic number of qubits are efficiently classically simulable. These log-space circuits are an obvious "island" in the metaphor of the article and adding more qubits is the "quantum resource…

Would be incorrect to consider the example where there is no superposition like a special case of the island with no entanglement? Because you should be able to classically simulate superposed states as long as these are not entangled so states with no superposition should be a particular subset.

I don't think this argument really works, because you can also classically simulate superposed states as long as they are stabilizer states, or fermionic gaussian states, or log-space states or whatever else. Similarly you can also classically simulate states with arbitrarily large amounts of stabilzer magic if they happen to be fermionic gaussian states or whatever.

I think you can sort-make the argument you want to make, because all computational basis states are also product states, just like all computational basis states are also stabilizer states and also (if they have the right parity) fermionic gaussian states. Where it goes wrong is when you start thinking about gates/circuits instead of states, because (e.g.) CX or CCC..CX gates with arbitrary numbers of controls are (in general) highly entangling gates, but they map computational basis states to other computational basis states.

Does this make sense?

Re: Quanta Magazine: The Quest to Quantify Quantumness

#12

Post by dabeddabed » Sat, Oct 21, 2023, 5:25 PM UTC

eigenket wrote: post #11

dabeddabed wrote: post #10

Earlier quoted context omitted.

Would be incorrect to consider the example where there is no superposition like a special case of the island with no entanglement? Because you should be able to classically simulate superposed states as long as these are not entangled so states with no superposition should be a particular subset.

I don't think this argument really works, because you can also classically simulate superposed states as long as they are stabilizer states, or fermionic gaussian states, or log-space states or whatever else. Similarly you can also classically simulate states with arbitrarily large amounts of stabilzer magic if they happen to be fermionic gaussian states or whatever. I think you can sort-make the argument you want to…

I think it makes sense but I also what I said before so if these really can't be compatible then I'm still confused, what I believe is that non superposing states should be a subset of any superposed state with its corresponding computational basis state, something like:

|Simulated state |Computational basis state that allows classical simulation|

|Non entangled superposed state |product/stabilizer/fermionic state|

|Entangled superposed state |stabilizer/fermionic state|

|Magic superposed state |fermionic state|

So as I see it non superposing states are a special case of any classically simulable superposed state so they can always be classically simulated.

Re: Quanta Magazine: The Quest to Quantify Quantumness

#13

Post by eigenket » Sat, Oct 21, 2023, 7:36 PM UTC

dabeddabed wrote: post #12

eigenket wrote: post #11

Earlier quoted context omitted.

I don't think this argument really works, because you can also classically simulate superposed states as long as they are stabilizer states, or fermionic gaussian states, or log-space states or whatever else. Similarly you can also classically simulate states with arbitrarily large amounts of stabilzer magic if they happen to be fermionic gaussian states or whatever. I think you can sort-make the argument you want to…

I think it makes sense but I also what I said before so if these really can't be compatible then I'm still confused, what I believe is that non superposing states should be a subset of any superposed state with its corresponding computational basis state, something like: |Simulated state |Computational basis state that allows classical simulation| |Non entangled superposed state |product/stabilizer/fermionic state| |…

For individual states I think what you're saying is correct, but I think thinking about individual states is not the right way to go about classical simulation or thinking about complexity.

For example imagine we have a big, complicated quantum circuit, which doesn't look "nice" in any way, but at every time it happens that the state may be expressed as a superposition of only 2 (or a few) stabilzer states. Even though the states are simple in this sense, we wouldn't expect to be able to efficiently classically simulate this circuit.

This is because even though there is an efficient classical description of the state of the quantum computer at every timestep (the efficient description is as a superposition of a few stabilizer states), there isn't an efficient way to find these efficient classical descriptions, or even notice that they exist.

Re: Quanta Magazine: The Quest to Quantify Quantumness

#14

Post by dabeddabed » Sat, Oct 21, 2023, 10:09 PM UTC

eigenket wrote: post #13

dabeddabed wrote: post #12

Earlier quoted context omitted.

I think it makes sense but I also what I said before so if these really can't be compatible then I'm still confused, what I believe is that non superposing states should be a subset of any superposed state with its corresponding computational basis state, something like: |Simulated state |Computational basis state that allows classical simulation| |Non entangled superposed state |product/stabilizer/fermionic state| |…

For individual states I think what you're saying is correct, but I think thinking about individual states is not the right way to go about classical simulation or thinking about complexity. For example imagine we have a big, complicated quantum circuit, which doesn't look "nice" in any way, but at every time it happens that the state may be expressed as a superposition of only 2 (or a few) stabilzer states. Even thou…

Right that is nice point I wouldn't have think about if you hadn't draw my attention there, well that was all I will be not taking more of your time, thank you very much for answering all my doubts it was very productive for me as I learned a lot =), all the best.