Quantum Multiplexer Simplification #13099
Conversation
|
|
|
Thank you for opening a new pull request. Before your PR can be merged it will first need to pass continuous integration tests and be reviewed. Sometimes the review process can be slow, so please be patient. While you're waiting, please feel free to review other open PRs. While only a subset of people are authorized to approve pull requests for merging, everyone is encouraged to review open pull requests. Doing reviews helps reduce the burden on the core team and helps make the project's code better for everyone. One or more of the following people are relevant to this code:
|
Pull Request Test Coverage Report for Build 11779453889Warning: This coverage report may be inaccurate.This pull request's base commit is no longer the HEAD commit of its target branch. This means it includes changes from outside the original pull request, including, potentially, unrelated coverage changes.
Details
💛 - Coveralls |
|
Hi @josejad42, thanks for opening a PR! Could you give some more context to what you're suggesting, e.g. is there a reference that describes this simplification, and could you benchmark your improvement? |
|
Hi @Cryoris, the reference will appear on arxiv in the next few days. |
| statevector2 = Statevector(qc2) | ||
|
|
||
| print(qc1.count_ops()) | ||
| print(qc2.count_ops()) |
There was a problem hiding this comment.
I think that these prints could be removed. In addition, is there some upper bound on the number of ops that can be added to the tests?
There was a problem hiding this comment.
Thanks, we removed the prints and included a test to verify if the Initialize reduced the number of cnots of a disentangled state.
| @@ -39,6 +39,36 @@ class TestInitialize(QiskitTestCase): | |||
|
|
|||
| _desired_fidelity = 0.99 | |||
|
|
|||
| def test_disentangled(self): | |||
There was a problem hiding this comment.
Please note that the current Qiskit Initialize code is based on Isometry by Iten et al. Phys. Rev. A 93, 032318.
This change has been done recently in #12178 for Qiskit 1.2 release.
There was a problem hiding this comment.
Thanks, we fixed the optimization and now the test works.
|
Hi @Cryoris and @ShellyGarion |
| counts1 = qc1.count_ops()["cx"] | ||
| counts2 = qc2.count_ops()["cx"] | ||
|
|
||
| self.assertTrue(counts2 <= counts1) | ||
| self.assertTrue(np.allclose(statevector1, statevector2)) |
There was a problem hiding this comment.
The UCGate simplification impacts state preparation.
If a real-valued state is separable, the number of cx gates of Initialize will be reduced.
However, there is no guarantees that the number of cnots will be optimal.
The initialization of [0, 1, 0, 0] produces a circuit with one cx (that can be removed because the control is always in zero).
In complex-valued states, we can have some optimization. But there is no guarantee that the simplification will work.
There was a problem hiding this comment.
in the test above both counts1 and counts2 are equal (=12). Do you have an example that there is an inequality? (perhaps you would like to fix a seed).
Could you please add some benchmarks comparing your state preparation code to the existing Qiskit code? |
Yes, sure! The best case is a separable real-valued state. qiskit 1.2.0nqubits: 3 depth: 10 time: 0.03743324100003065 this branchnqubits: 3 depth: 2 time: 0.053231799975037575 import numpy as np
from qiskit import transpile, QuantumCircuit
from time import perf_counter
for k in range(1, 5):
size = 2 ** k
state1 = np.random.rand(size)
state1 = state1 / np.linalg.norm(state1)
state2 = np.random.rand(size)
state2 = state2 / np.linalg.norm(state2)
state3 = np.random.rand(size)
state3 = state3 / np.linalg.norm(state3)
state = np.kron(state1, state2)
state = np.kron(state, state3)
nqubits = int(np.log2(len(state)))
start = perf_counter()
qc2 = QuantumCircuit(nqubits)
qc2.initialize(state)
qc2 = transpile(qc2, basis_gates=['u', 'cx'], optimization_level=2)
end = perf_counter()
print('nqubits: ', nqubits, 'depth: ', qc2.depth(), 'time: ', end - start)
|
Co-authored-by: Adenilton Silva <7927558+adjs@users.noreply.github.com>
There was a problem hiding this comment.
@josejad42, @adjs - Thanks for your contribution to Qiskit!
My main question is whether you always reduce the number of CX gates in the StatePreparation or Initialize process ?
I tried the same complex random states that appears in #12081 and I see that the number of CX gates in unchanged. In the example you provided above, the number of CX gates is significantly reduced.
Are there states for which the number of CX gates may increase ?
You may also add your reference and an explanation to the API docs (line 64)
| def __init__(self, gate_list: list[np.ndarray], up_to_diagonal: bool = False): | ||
| def __init__( | ||
| self, gate_list: list[np.ndarray], up_to_diagonal: bool = False, mux_simp: bool = True | ||
| ): |
There was a problem hiding this comment.
-
why do you need the parameter
mux_simp?
if it's needed - please also add it to the documentation (line 81). -
if this parameter is needed, why don't you need to call it in the functions that call
UCGatedirectly or indirectly (mcg_up_to_diagonal,Isometry,StatePreparationandInitialize) ? Since it's default value isTrueit will always affect these functions.
There was a problem hiding this comment.
We think that some users may not want to search for simplifications or may need to use the original version of the multiplexer. Therefore, simplification is enabled by default but can be easily disabled. Documentation will be updated.
| @@ -100,6 +107,21 @@ def test_inverse_ucg(self): | |||
|
|
|||
| self.assertTrue(np.allclose(unitary_desired, unitary)) | |||
|
|
|||
| def test_ucge(self): | |||
There was a problem hiding this comment.
why do you need a specific test? Isn't it enough to add this specific gate_list of hadamards to squs above?
| counts1 = qc1.count_ops()["cx"] | ||
| counts2 = qc2.count_ops()["cx"] | ||
|
|
||
| self.assertTrue(counts2 <= counts1) | ||
| self.assertTrue(np.allclose(statevector1, statevector2)) |
There was a problem hiding this comment.
in the test above both counts1 and counts2 are equal (=12). Do you have an example that there is an inequality? (perhaps you would like to fix a seed).
update documentation
In the context of state preparation, our simplification primarily applies when the state to be prepared is separable, as the presence of a given repetition pattern in multiplexers is quite common in these cases. Randomly generated states are less likely to exhibit such repetitions, meaning that the number of CX ports remains unchanged. The reference was updated in the documentation. |
|
Could you please also add release notes to your PR ? |
|
Wondering if this is needed if mux_simplify:
circuit.append(diagonal, [q_target] + q_controls)
else:
circuit.append(diagonal, q)Isn't |
When there's simplification, to add the diagonal gate in the correct position. |
Hi, @ShellyGarion. The release notes have been added. |
|
May I ask when this will be merged with main? |
I'm still reviewing it. I hope to finish it soon :) |
| @@ -44,6 +46,7 @@ class TestUCGate(QiskitTestCase): | |||
| [_id, _id], | |||
| [_id, 1j * _id], | |||
| [_id, _not, _id, _not], | |||
| [_rand, _had, _rand, _had, _rand, _had, _rand, _had], | |||
There was a problem hiding this comment.
I would also suggest to add here:
[_had, _had, _had, _had, _had, _had, _had, _had],
then after line 53, please also add:
mux_simp = [True, False],
and in line 56, call:
def test_ucg(self, squs, up_to_diagonal, mux_simp):
and update lines 62 and 71 to:
UCGate(squs, up_to_diagonal=up_to_diagonal, mux_simp=mux_simp)
There was a problem hiding this comment.
Suggestions accepted and included.
| uc2 = UCGate(gate_list, up_to_diagonal=False, mux_simp=True) | ||
| qc2.append(uc2, range(4)) | ||
| op2 = Operator(qc2).data | ||
| self.assertTrue(np.allclose(op1, op2)) |
There was a problem hiding this comment.
When I change up_to_diagonal=True in both lines 115 and 120, then the test fails, any idea why?
If mux_simp should not work in case that up_to_diagonal=True - then it's better to state it in the docs and raise a proper error that asserts that the the two variables can not both be True.
There was a problem hiding this comment.
This occurs because the final operator when we have up_to_diagonal=True is not equal for the original and the simplified multiplexers. But when we multiply the two operators by the respective diagonal matrices obtained by self._get_diagonal(), the final operators (and the prepared states) are the same.
|
This is a cool PR! Out of curiosity, how common are multiplexers with repetitions in "practical applications"? I have not thought about the problem too much, but it strongly reminds me of the works on more concisely representing boolean functions. For instance, we can probably express the problem in terms of (multi-valued) decision diagrams, or alternatively as expressing a truth table of a boolean function as a sum-of-products with non-overlapping products. One more question: the simplified representation is not unique, correct? For instance, if the following 3 control paths |
|
@alexanderivrii Multiplexors are essentially uniformly controlled gates. The main use of them for me has been in the implementation of state and unitary synthesis by Shende. If one can implement a multiplexor with less number of gates, then in those applications the overall circuit depth would be considerably smaller. |
|
@alexanderivrii As described above, quantum multiplexers are common in state preparation and unitary synthesis. This method introduces a simplification when a specific pattern of repetitions is detected. This pattern is very common to separable states preparation and can be detected with low computational cost. So, this is not a general simplification. |
Summary
Multiplexer optimization by reducing unnecessary controls.
Details and comments
This method introduces a simplification in multiplexers that removes unnecessary controls and operators when a pattern of repetitions is detected. The main advantage is a significant reduction in both the number of CX gates and the overall circuit depth during separable state preparation.