Quantum Multiplexer Simplification

josejad42 commented 3 weeks ago

Summary

Multiplexer optimization by reducing unnecessary controls.

Details and comments

CLAassistant commented 3 weeks ago

All committers have signed the CLA.

qiskit-bot commented 3 weeks ago

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:

@Cryoris
@Qiskit/terra-core
@ajavadia

coveralls commented 3 weeks ago

Pull Request Test Coverage Report for Build 10954395085

Warning: 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.

For more information on this, see Tracking coverage changes with pull request builds.
To avoid this issue with future PRs, see these Recommended CI Configurations.
For a quick fix, rebase this PR at GitHub. Your next report should be accurate.

Details

72 of 72 (100.0%) changed or added relevant lines in 1 file are covered.
1750 unchanged lines in 57 files lost coverage.
Overall coverage decreased (-0.4%) to 88.787%

Files with Coverage Reduction	New Missed Lines	%
qiskit/quantum_info/operators/mixins/multiply.py	1	93.75%
qiskit/pulse/instructions/directives.py	1	97.22%
qiskit/synthesis/one_qubit/one_qubit_decompose.py	1	70.67%
qiskit/quantum_info/operators/mixins/group.py	1	92.59%
qiskit/transpiler/passes/synthesis/unitary_synthesis.py	1	88.61%
qiskit/quantum_info/operators/channel/quantum_channel.py	1	72.14%
qiskit/pulse/transforms/alignments.py	1	96.45%
qiskit/quantum_info/operators/mixins/adjoint.py	1	90.0%
qiskit/transpiler/passes/layout/sabre_pre_layout.py	1	98.88%
crates/qasm2/src/lex.rs	1	92.73%
<!--	Total:	1750	-->

Totals
Change from base Build 10725151093:	-0.4%
Covered Lines:	73544
Relevant Lines:	82832

💛 - Coveralls

Cryoris commented 3 weeks ago

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?

adjs commented 3 weeks ago

Hi @Cryoris, the reference will appear on arxiv in the next few days.

adjs commented 3 weeks ago

Hi @Cryoris and @ShellyGarion The multiplexer simplification is described in https://arxiv.org/pdf/2409.05618

ShellyGarion commented 3 weeks ago

Hi @Cryoris and @ShellyGarion The multiplexer simplification is described in https://arxiv.org/pdf/2409.05618

Could you please add some benchmarks comparing your state preparation code to the existing Qiskit code? See e.g. the benchmarks in https://github.com/Qiskit/qiskit/issues/12081

adjs commented 3 weeks ago

Hi @Cryoris and @ShellyGarion The multiplexer simplification is described in https://arxiv.org/pdf/2409.05618

Could you please add some benchmarks comparing your state preparation code to the existing Qiskit code? See e.g. the benchmarks in #12081

Yes, sure! The best case is a separable real-valued state.

qiskit 1.2.0

nqubits: 3 depth: 10 time: 0.03743324100003065 nqubits: 6 depth: 116 time: 0.08239613299997472 nqubits: 9 depth: 1006 time: 0.8098489340000015 nqubits: 12 depth: 8168 time: 27.270649252000112

this branch

nqubits: 3 depth: 2 time: 0.053231799975037575 nqubits: 6 depth: 4 time: 0.05455289990641177 nqubits: 9 depth: 10 time: 0.10728330002166331 nqubits: 12 depth: 24 time: 0.424586100038141

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)

josejad42 commented 1 week ago

@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)

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.

ShellyGarion commented 6 days ago

Could you please also add release notes to your PR ?

ACE07-Sev commented 4 days ago

Wondering if this is needed

if mux_simplify:
    circuit.append(diagonal, [q_target] + q_controls)
else:
    circuit.append(diagonal, q)

Isn't q also [q_target] + q_controls? If we ignore mux_simplify, then q_target=q[0], and q_controls=q[1:], ergo q. Given the clause above, it would still be just q whether mux_simplify is True or not. Please correct me if I am wrong, I may be missing something.

Qiskit / qiskit