Add support for > 32 qudits to cirq.sample_state_vector. Fix for #6031 #6090

NoureldinYosri · 2023-05-09T19:03:04Z

When the number of qudits > 32 do the transpose operation on the flattened array.
I expect this to be slower than np.transpose(tensor, axes) so I'm keeping the use of np.transpose when we can.
I also rewrote the _prob in a more efficient way. The old way did a lot of extra work when reordering the axes is all that is needed.

Fix for #6031.

rht · 2023-05-12T05:00:54Z

cirq-core/cirq/sim/state_vector.py

+        # If we can't use numpy due to numpy/numpy#5744, use a slower method.
+        probs = linalg.transpose_flattened_array(probs, qid_shape, list(indices) + not_measured)
+
+    if len(not_measured):


This is simpler than the old code. I suppose it is also faster?

yes. the main difference is what happens in the case of not measuring all qudits. In the old way it did $n$ steps each of which is slicing a matrix followed by np.sum. In the new way there is no slicing it's just a reshape since I order the indicies such that the unmeasured qudits are the last indicies so they become rows of the final matrix.

rht · 2023-05-12T05:04:33Z

cirq-core/cirq/sim/state_vector.py

+    if linalg.can_numpy_support_shape(qid_shape):
+        # Use numpy transpose if we can since it's more efficient.
+        probs = probs.reshape(qid_shape)
+        probs = np.transpose(probs, list(indices) + not_measured)


Looking at the usage of np.transpose elsewhere in the codebase, it looks like there is another place with similar usage:

Cirq/cirq-core/cirq/sim/density_matrix_utils.py

Lines 195 to 213 in a95f009

if len(indices) == len(qid_shape):

# We're measuring every qudit, so no need for fancy indexing

probs = np.abs(tensor)

probs = np.transpose(probs, indices)

probs = probs.reshape(-1)

else:

# Fancy indexing required

meas_shape = tuple(qid_shape[i] for i in indices)

probs = np.abs(

[

tensor[

linalg.slice_for_qubits_equal_to(

indices, big_endian_qureg_value=b, qid_shape=qid_shape

)

]

for b in range(np.prod(meas_shape, dtype=np.int64))

]

)

probs = np.sum(probs, axis=tuple(range(1, len(probs.shape))))

this is an exact copy of the code I'm modifying 😞 I refactored this part into a seprate method which I call from both locations

NoureldinYosri · 2023-05-12T14:44:14Z

@rht I refactored the code so that both locations call the method.

I don't know why cirq/study/resolver_test.py::test_custom_value_not_implemented is failing but it seems to be not related to my PR since it's already failing at head

$ git branch
* master
$ pytest cirq/study/resolver_test.py -k test_custom_value_not_implemented
=========================================================================================== test session starts ===========================================================================================
platform linux -- Python 3.10.11, pytest-7.3.1, pluggy-1.0.0
Using --randomly-seed=4244270818
configfile: pyproject.toml
plugins: forked-1.6.0, cov-4.0.0, xdist-2.2.1, randomly-3.12.0, anyio-3.6.2, asyncio-0.21.0
asyncio: mode=strict
collected 47 items / 46 deselected / 1 selected                                                                                                                                                           

cirq/study/resolver_test.py x                                                                                                                                                                       [100%]

==================================================================================== 46 deselected, 1 xfailed in 0.93s ====================================================================================

NoureldinYosri · 2023-05-16T18:55:03Z

@rht this is now ready for merging

cirq-core/cirq/sim/simulation_util.py

rht · 2023-05-25T04:35:11Z

Nit: I searched for the files named *_util.py; there are 2 occurrences. While *_utils.py has 7 occurrences. As such, I think it should be simulation_utils.py?

cirq-core/cirq/sim/simulation_util.py

NoureldinYosri · 2023-05-25T14:43:51Z

this is ready for another look

tanujkhattar · 2023-05-30T23:51:33Z

The 32 qubit dimension constraint for numpy is more annoying that I initially thought. Another example: cirq.unitary() fails when the dimension of circuit is > 16. Note that a 2**17 x 2 ** 17 numpy array of complex64 takes ~128gb, so it's not unreasonable to expect that the protocol should work. We can add this example as part of the issue and track it in a separate PR though.

In [1]: import cirq
In [2]: q = cirq.LineQubit.range(17)
In [3]: circuit = cirq.Circuit(cirq.Z.on_each(*q))
In [4]: cirq.unitary(circuit)

NoureldinYosri · 2023-05-31T17:54:10Z

@tanujkhattar wouldn't computing such a unitary generally (when the unitary is not a tensor product) take a couple of hours/days? ... a single multiplication of two a $2^{17} \times 2^{17}$ matricies will take around half an hour $8^{17} \textit{operations} \approx 2251 \textit{seconds} \approx 37 \textit{minutes}$ (assumming $10^{12}$ operations per second).

anyway lets keep track of all the places suffering from this problem in the original issue.

can we merge this PR?

NoureldinYosri · 2023-06-28T17:25:57Z

@tanujkhattar ping

…tumlib#6031 (quantumlib#6090) * Add support for > 32 qudits to cirq.sample_state_vector. Fix for quantumlib#6031 * refactor the method into a seprate util module * fix lint * accept only probabilities not complex numbers * added tests

Add support for > 32 qudits to cirq.sample_state_vector. Fix for quan…

04814e1

…tumlib#6031

NoureldinYosri requested review from a team, vtomole and cduck as code owners May 9, 2023 19:03

NoureldinYosri requested a review from MichaelBroughton May 9, 2023 19:03

rht reviewed May 12, 2023

View reviewed changes

NoureldinYosri added 4 commits May 12, 2023 14:15

refactor the method into a seprate util module

655adee

fix lint

2fff505

accept only probabilities not complex numbers

c431e4f

Merge branch 'master' into support_more_than_32d

9a37ef4

NoureldinYosri mentioned this pull request May 12, 2023

isolated_packages_test.py fails at HEAD #6092

Closed

Merge branch 'master' into support_more_than_32d

79f97ad

CirqBot added the size: L 250< lines changed <1000 label May 16, 2023

Merge branch 'master' into support_more_than_32d

c5aa76a

tanujkhattar reviewed May 24, 2023

View reviewed changes

cirq-core/cirq/sim/simulation_util.py Outdated Show resolved Hide resolved

rht reviewed May 25, 2023

View reviewed changes

cirq-core/cirq/sim/simulation_util.py Outdated Show resolved Hide resolved

NoureldinYosri mentioned this pull request May 25, 2023

cirq.sample_state_vector fails when the number of qubits > 32 #6031

Closed

NoureldinYosri added 2 commits May 25, 2023 15:03

Merge branch 'master' into support_more_than_32d

07688e9

added tests

5905c69

tanujkhattar self-assigned this May 30, 2023

NoureldinYosri added 2 commits June 22, 2023 16:45

Merge branch 'master' into support_more_than_32d

7490b3c

Merge branch 'master' into support_more_than_32d

41bec75

tanujkhattar approved these changes Jun 28, 2023

View reviewed changes

tanujkhattar merged commit 74cee7e into quantumlib:master Jun 28, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add support for > 32 qudits to cirq.sample_state_vector. Fix for #6031 #6090

Add support for > 32 qudits to cirq.sample_state_vector. Fix for #6031 #6090

NoureldinYosri commented May 9, 2023 •

edited

Loading

rht May 12, 2023

NoureldinYosri May 12, 2023

rht May 12, 2023

NoureldinYosri May 12, 2023

NoureldinYosri commented May 12, 2023

NoureldinYosri commented May 16, 2023

rht commented May 25, 2023

NoureldinYosri commented May 25, 2023

tanujkhattar commented May 30, 2023 •

edited

Loading

NoureldinYosri commented May 31, 2023

NoureldinYosri commented Jun 28, 2023

	if len(indices) == len(qid_shape):
	# We're measuring every qudit, so no need for fancy indexing
	probs = np.abs(tensor)
	probs = np.transpose(probs, indices)
	probs = probs.reshape(-1)
	else:
	# Fancy indexing required
	meas_shape = tuple(qid_shape[i] for i in indices)
	probs = np.abs(
	[
	tensor[
	linalg.slice_for_qubits_equal_to(
	indices, big_endian_qureg_value=b, qid_shape=qid_shape
	)
	]
	for b in range(np.prod(meas_shape, dtype=np.int64))
	]
	)
	probs = np.sum(probs, axis=tuple(range(1, len(probs.shape))))

Add support for > 32 qudits to cirq.sample_state_vector. Fix for #6031 #6090

Add support for > 32 qudits to cirq.sample_state_vector. Fix for #6031 #6090

Conversation

NoureldinYosri commented May 9, 2023 • edited Loading

rht May 12, 2023

Choose a reason for hiding this comment

NoureldinYosri May 12, 2023

Choose a reason for hiding this comment

rht May 12, 2023

Choose a reason for hiding this comment

NoureldinYosri May 12, 2023

Choose a reason for hiding this comment

NoureldinYosri commented May 12, 2023

NoureldinYosri commented May 16, 2023

rht commented May 25, 2023

NoureldinYosri commented May 25, 2023

tanujkhattar commented May 30, 2023 • edited Loading

NoureldinYosri commented May 31, 2023

NoureldinYosri commented Jun 28, 2023

NoureldinYosri commented May 9, 2023 •

edited

Loading

tanujkhattar commented May 30, 2023 •

edited

Loading