qiskit.quantum_info.StabilizerState needs get_probability() method

[ginsparg]

What should we add?

qiskit.quantum_info.StabilizerState has a method .probabilities_dict() , which recurses through all 2^n possibilities so time complexity scales exponentially in the number of qubits. For a variety of purposes (including classical shadows), it is necessary to calculate only a single probability for some target bitstring via .get_probability(target). I've added that method to my own installation, by adapting from the _get_probablities helper function (note misspelling in function name). i pass it an argument target, and instead of iterating for single_qubit_outcome in range(0, 2): I use instead single_qubit_outcome = int(target[qubit_for_branching]) and it returns only the outcome of interest (or zero if there's a deterministic outcome that doesn't agree with the target string)

so this is an extremely useful method that entirely uses existing code, just eliminates unnecessary branches. instead of a separate method, you could also add an argument to the .probabilities_dict() method that would permit specifying any restricted subset of strings to return in the dict (and not calculate the rest)

[jakelishman]

Putting in a method to restrict the set of returned probabilities sounds useful to me. @ShellyGarion: I think you were the original author - do you have any thoughts?

[ShellyGarion]

I agree that adding a new method to the StabilizerState class that returns a restricted set of probabilities will be very useful. @ginsparg - would you like to contribute and open a PR?

[DerekMiner]

Hi, I am part of the IBM OpenSource Coalition for getting started with open source. @psschwei thought this was a good first issue, this issue looks interesting to me and I would like implement it

[ShellyGarion]

Hi @DerekMiner - Thanks for your willing to contribute to qiskit. You have been assigned on this issue. When you open a PR please tag me, so I'll look at it and review it.

[DerekMiner]

Hi @DerekMiner - Thanks for your willing to contribute to qiskit. You have been assigned on this issue. When you open a PR please tag me, so I'll look at it and review it.

Sounds great, thank you!

[DerekMiner]

regarding: "you could also add an argument to the .probabilities_dict() method that would permit specifying any restricted subset of strings to return in the dict (and not calculate the rest)"

does anyone in the community have a preference of adding a parm to probabilities_dict() method, otherwise I could create a method of something like probabilities_dict_using_target()

@ShellyGarion you mentioned "I agree that adding a new method to the StabilizerState class that returns a restricted set of probabilities will be very #useful." any preference?

I am leaning towards using the same method with a new target parm default of None, if not provided then will operate as before, if provided it will rely on the target

[ShellyGarion]

regarding: "you could also add an argument to the .probabilities_dict() method that would permit specifying any restricted subset of strings to return in the dict (and not calculate the rest)"

does anyone in the community have a preference of adding a parm to probabilities_dict() method, otherwise I could create a method of something like probabilities_dict_using_target()

@ShellyGarion you mentioned "I agree that adding a new method to the StabilizerState class that returns a restricted set of probabilities will be very #useful." any preference?

I am leaning towards using the same method with a new target parm default of None, if not provided then will operate as before, if provided it will rely on the target

My preference would be to add a separate method, as the probabilities and probabilities_dict methods also exist in the Statevector class, and we would like to keep the same API of both classes: https://docs.quantum.ibm.com/api/qiskit/qiskit.quantum_info.Statevector#probabilities

But since "target" has a different meaning in Qiskit, I would suggest to call it something like: probabilities_dict_from_bitstrings

[DerekMiner]

regarding: "you could also add an argument to the .probabilities_dict() method that would permit specifying any restricted subset of strings to return in the dict (and not calculate the rest)" does anyone in the community have a preference of adding a parm to probabilities_dict() method, otherwise I could create a method of something like probabilities_dict_using_target() @ShellyGarion you mentioned "I agree that adding a new method to the StabilizerState class that returns a restricted set of probabilities will be very #useful." any preference? I am leaning towards using the same method with a new target parm default of None, if not provided then will operate as before, if provided it will rely on the target

My preference would be to add a separate method, as the probabilities and probabilities_dict methods also exist in the Statevector class, and we would like to keep the same API of both classes: https://docs.quantum.ibm.com/api/qiskit/qiskit.quantum_info.Statevector#probabilities

But since "target" has a different meaning in Qiskit, I would suggest to call it something like: probabilities_dict_from_bitstrings

I will go with that, thank you!

[ginsparg]

thanks all for looking into this ... (and for suggesting i open a PR -- forgot to respond that never having recovered from the experience of starting with fortran programming in the 1960s unfortunately my code in any language is not ordinarily fit for human consumption).

adding a parameter to the existing method would have been conceptually much cleaner, so it's unfortunate that turns out not to be as practical. (we've all had the experience of being forced to go through multiple methods in documentation of some class, only to be mystified by why there are two methods with 90% overlap -- or worse, we stop at the first and never notice the later one which has the extra 10% we need.) it does make sense to keep the methods synchronized with the Statevector class, so perhaps all could be updated simultaneously.

regardless, if something works out here, i have some additional code that may help inform the architectural considerations. i also used qiskit to sample from say Clifford evolution of W-states with large number n of qubits. While W states are not themselves stabilizer states, they are low-rank linear combinations of stabilizer states, so the amplitudes can be efficiently simulated independently and then added, presuming one keeps track of the phases +/- 1, +/- i, which i added as well to my local installation. e.g., to simulate W states (or any other O(n) rank combination), it's still just low polynomial in n (rather than exponential). that method was slightly less trivial but more fun to write. i use a .get_amplitudes() method for a set of bitstrings, then superpose and abs val square for a probability, or sequence through qubits to sample. am mentioning just in case the possibility of accommodating something along those lines in the future as another epsilon extension would affect current decision-making.

(and of course the spelling of '_get_probablities' should be corrected) tks, pg

[DerekMiner]

I will make sure to fix the probabilities typo as well, I created an issue for it just to document that #11688

[DerekMiner]

I am continuing to work this issue, having some problems getting the baseline tests to run without any code changes, but this issue is still on my list of priorities to work on

[DerekMiner]

@ginsparg do you have any examples of inputs and targets I could use to add for the tests that you have used?

[ginsparg]

the program i was running to calculate classical shadows found squared amplitudes for specific basis elements after applying random cliffords, so that would not be reproducible. but is see qiskit.quantum_info.random_clifford has an optional seed, so i'll run a set of reproducible inputs and targets to benchmark against (probably over weekend) .

[DerekMiner]

I made some good progress on this issue, I am hoping to have something in the next week or two to submit

[ShellyGarion]

@ginsparg do you have any examples of inputs and targets I could use to add for the tests that you have used?

I also recommend looking at the current tests in: https://github.com/Qiskit/qiskit/blob/main/test/python/quantum_info/states/test_stabilizerstate.py and: https://github.com/Qiskit/qiskit/blob/main/test/python/quantum_info/operators/symplectic/test_clifford.py for deterministic and pseudo-random tests.

[DerekMiner]

Thanks! I was actually working on adding some tests in the test_stabilizerstate.py, I will look at the other file as well

[DerekMiner]

I finished the enhancement and got it working, just working on adding tests. Ended up having an ah ha moment while working, was headed down a path with having to way over track the state of things, back tracked and ended up with much simpler code. Seems to be a nice performance boost when targeting specific targets you want, especially as the number of qubits gets larger, the improvement is quite significant. I am adding some tests that will also verify there is a performance benefit when using targets

[DerekMiner]

I was hitting a problem where if you calculate roughly half of the targets of a normal call to the probability function, it would end up performing worse because it was traversing down branches it had already done some calculations for. I was able to squeeze out a bit better performance then my last update by adding a caching dict when going down the branches, so if you have more then 1 target you want calculated, and one of the targets previously went down a similar branch, you can start at a better starting point for calculating the rest of the branch, again a nice performance boost. Still finishing up adding tests, but overall things are going great

[DerekMiner]

I generated a draft pull request #11947. I focused very heavily on writing tests the prove integrity of the results as well as the verifying the major performance increase

[DerekMiner]

To give some insight into the performance improvement, if you do a calculation with 12 qubits, loop through the test for 10 samples, with no target it takes 14.39 seconds on my local machine to run through all those calculation. If you now have 2 targets to get results for, to retrieve those 2 targets it takes 0.048 seconds, about a 300x speed increase roughly for that example. Since you are getting 2 targets you could expect close to 2x that if you were getting the result of 1 target, or 600x faster.

The more qubits you have and the smaller the target list you want to retrieve, the better the performance improvement you will see.

[DerekMiner]

@ginsparg have you gotten a chance to try out my branch and try using targets?

you can pass in a None (no targets), or target str, list[str] or dict[str, any] for your targets, and you will get back the normal dict[str, float] values for only what you specified without calculating any unnecessary branches now

new method is probabilities_dict_from_bitstrings, I recommended leaving the caching variable to on which is set to True by default in this method

[DerekMiner]

I had a discussion with @ShellyGarion in PR #11947 and I am going to make some changes and create a new PR that is simpler and accepts only one target outcome bitstring value