Enable the new efficient MCX decompose

t-imamichi commented 1 week ago

Summary

This PR enables #11993 as QuantumCircuit.mcx. We can reduce the number of CNOT gates as follows.

from qiskit import QuantumCircuit

def bench_mcx(n: int):
    qc = QuantumCircuit(n)
    qc.mcx(list(range(n - 1)), n - 1)
    #print(qc.decompose(reps=1))
    print(n, qc.decompose(reps=4).count_ops()["cx"])

for i in range(6, 10):
    bench_mcx(i)

main

this PR

Details and comments

qiskit-bot commented 1 week ago

One or more of the following people are relevant to this code:

@Qiskit/terra-core

t-imamichi commented 1 week ago

I try to fix errors, but I cannot fix all errors. Need help by experts.

Cryoris commented 1 week ago

Thanks for spotting this, that's indeed an easy win! 🙂 Regarding the errors:

The decomposition failures are expected, since the MCX definition is now more efficient, the references need updating. I think you can just do this in place.
The QASM failures happen because the circuit now places an MCXGate(name="mcx") which, for 3 controls, is decomposed into C3XGate(name="mcx"). I think the naming conflict causes the strange QASM output. Two possible solutions would be renaming C3XGate(name="c3x") but this could have other repercussions or just accept the new QASM output and fit a regex to cover the number. But maybe @jakelishman has a better idea 🙂

ShellyGarion commented 1 week ago

Thanks for handling this @t-imamichi !

One can fix the failing test test/python/transpiler/test_decompose.py as follows:

replace this line: https://github.com/Qiskit/qiskit/blob/87aa89c19387ef7ff4177ef5144f60119da392e3/test/python/transpiler/test_decompose.py#L219 by: decom_circ = self.complex_circuit.decompose(["mcx"], reps=2)

replace this line: https://github.com/Qiskit/qiskit/blob/87aa89c19387ef7ff4177ef5144f60119da392e3/test/python/transpiler/test_decompose.py#L239 by: decom_circ = self.complex_circuit.decompose(["mcx", "gate2"], reps=2)

t-imamichi commented 1 week ago

Thank you for your suggestions, @Cryoris and @ShellyGarion. I tried to update C3X name and C4X name, and found that it affects test_decompose.py. It raises errors even with reps=2 suggested by Shelly.

ShellyGarion commented 1 week ago

Thank you for your suggestions, @Cryoris and @ShellyGarion. I tried to update C3X name and C4X name, and found that it affects test_decompose.py. It raises errors even with reps=2 suggested by Shelly.

my suggestion works with your current PR (without any further changes)

t-imamichi commented 1 week ago

Yes, I confirmed it. But the combination does not work unfortunately. I pushed a commit JFYI.

t-imamichi commented 1 week ago

Changing C3X and C4X names does not seem a good idea. There is an unpredicted error as follows.

test.python.qasm3.test_export.TestCircuitQASM3ExporterTemporaryCasesWithBadParameterisation.test_no_include
-----------------------------------------------------------------------------------------------------------

Captured traceback:
~~~~~~~~~~~~~~~~~~~
    Traceback (most recent call last):

      File "/Users/runner/work/qiskit/qiskit/test/python/qasm3/test_export.py", line 2166, in test_no_include
    res = Exporter(includes=[]).dumps(circuit).splitlines()

      File "/Users/runner/work/qiskit/qiskit/qiskit/qasm3/exporter.py", line 181, in dumps
    self.dump(circuit, stream)

      File "/Users/runner/work/qiskit/qiskit/qiskit/qasm3/exporter.py", line 195, in dump
    builder.build_program()

      File "/Users/runner/work/qiskit/qiskit/qiskit/qasm3/exporter.py", line 487, in build_program
    main_statements = self.build_current_scope()

      File "/Users/runner/work/qiskit/qiskit/qiskit/qasm3/exporter.py", line 850, in build_current_scope
    nodes = [self.build_gate_call(instruction)]

      File "/Users/runner/work/qiskit/qiskit/qiskit/qasm3/exporter.py", line 1060, in build_gate_call
    gate_name = ast.Identifier(self.global_namespace[instruction.operation])

      File "/Users/runner/work/qiskit/qiskit/qiskit/qasm3/exporter.py", line 270, in __getitem__
    return self._data[f"{key.name}_{ctrl_state}_{key.params}"]

    KeyError: 'cx_1_[]'

mtreinish commented 1 week ago

KeyError: 'cx1[]'

You can ignore this error, it's a bug in the qasm3 exporter. It's been looked at here: https://github.com/Qiskit/qiskit/pull/12481

t-imamichi commented 1 week ago

I succeeded in passing both test_decompose.py and test_export.py by changing name of C3X and C4X. But I'm not sure this is a right way. It might be a breaking change perhaps.

coveralls commented 1 week ago

Pull Request Test Coverage Report for Build 9658863540

Details

1 of 1 (100.0%) changed or added relevant line in 1 file are covered.
13 unchanged lines in 2 files lost coverage.
Overall coverage decreased (-0.01%) to 89.744%

Files with Coverage Reduction	New Missed Lines	%
crates/qasm2/src/lex.rs	1	93.64%
crates/qasm2/src/parse.rs	12	97.15%
<!--	Total:	13	-->

Totals
Change from base Build 9650973845:	-0.01%
Covered Lines:	63767
Relevant Lines:	71054

💛 - Coveralls

ShellyGarion commented 1 week ago

Following the qiskit dev meeting, it was suggested that the gates names will remain "mcx" (and not "c3x" or "c4x") in order to keep the current API, and the name changes can be done in qiskit 2.0 release. Only the tests should be updated accordingly. Could you please change the names, tests and add release notes?

t-imamichi commented 1 week ago

I reverted the C3X and C4X names. But due to the name conflict of C3X, C4X and MCX (all "mcx"), qasm2/test_export.py fails as follows (a random suffix is appended, e.g., mcx_4685682992). I don't know how to deal with it. Could you suggest a solution or take it over?

FAIL: test_mcx_gate (test.python.qasm2.test_export.TestQASM2Export)
test.python.qasm2.test_export.TestQASM2Export.test_mcx_gate
----------------------------------------------------------------------
testtools.testresult.real._StringException: Traceback (most recent call last):
  File "/Users/ima/tasks/4_2024/qiskit/terra/test/python/qasm2/test_export.py", line 396, in test_mcx_gate
    self.assertEqual(qasm2.dumps(qc), expected_qasm)
  File "/opt/homebrew/Cellar/python@3.10/3.10.14/Frameworks/Python.framework/Versions/3.10/lib/python3.10/unittest/case.py", line 845, in assertEqual
    assertion_func(first, second, msg=msg)
  File "/opt/homebrew/Cellar/python@3.10/3.10.14/Frameworks/Python.framework/Versions/3.10/lib/python3.10/unittest/case.py", line 1226, in assertMultiLineEqual
    self.fail(self._formatMessage(msg, standardMsg))
  File "/opt/homebrew/Cellar/python@3.10/3.10.14/Frameworks/Python.framework/Versions/3.10/lib/python3.10/unittest/case.py", line 675, in fail
    raise self.failureException(msg)
AssertionError: 'OPEN[394 chars]; }\ngate mcx_4685682992 q0,q1,q2,q3 { mcx q0,[56 chars][3];' != 'OPEN[394 chars]; }\nqreg q[4];\nmcx q[0],q[1],q[2],q[3];'
  OPENQASM 2.0;
  include "qelib1.inc";
  gate mcx q0,q1,q2,q3 { h q3; p(pi/8) q0; p(pi/8) q1; p(pi/8) q2; p(pi/8) q3; cx q0,q1; p(-pi/8) q1; cx q0,q1; cx q1,q2; p(-pi/8) q2; cx q0,q2; p(pi/8) q2; cx q1,q2; p(-pi/8) q2; cx q0,q2; cx q2,q3; p(-pi/8) q3; cx q1,q3; p(pi/8) q3; cx q2,q3; p(-pi/8) q3; cx q0,q3; p(pi/8) q3; cx q2,q3; p(-pi/8) q3; cx q1,q3; p(pi/8) q3; cx q2,q3; p(-pi/8) q3; cx q0,q3; h q3; }
- gate mcx_4685682992 q0,q1,q2,q3 { mcx q0,q1,q2,q3; }
  qreg q[4];
- mcx_4685682992 q[0],q[1],q[2],q[3];?    -----------
+ mcx q[0],q[1],q[2],q[3];

It might be a solution to update MCXGrayCode to replace MCU1 with MCP, but it might be another breaking change.

Cryoris commented 1 week ago

Hi @t-imamichi, I pushed a small fix for the qasm tests using regex to match the randomized gate ID, hopefully everything passes now 🙂

coveralls commented 1 week ago

Pull Request Test Coverage Report for Build 9676110521

Details

1 of 1 (100.0%) changed or added relevant line in 1 file are covered.
5 unchanged lines in 1 file lost coverage.
Overall coverage increased (+0.03%) to 89.747%

Files with Coverage Reduction	New Missed Lines	%
crates/qasm2/src/lex.rs	5	91.86%
<!--	Total:	5		-->

Totals
Change from base Build 9661630219:	0.03%
Covered Lines:	63769
Relevant Lines:	71054

💛 - Coveralls

ShellyGarion commented 1 week ago

Hi @t-imamichi, I pushed a small fix for the qasm tests using regex to match the randomized gate ID, hopefully everything passes now 🙂

thanks! this looks good, the tests are OK now, only some lint errors (line too long)

qiskit-bot commented 6 days ago

One or more of the following people are relevant to this code:

@Qiskit/terra-core

t-imamichi commented 6 days ago

Thank you for your supports, @ShellyGarion and @Cryoris. I fixed the lint errors and added reno. Could you review it?

coveralls commented 6 days ago

Pull Request Test Coverage Report for Build 9689789453

Details

1 of 1 (100.0%) changed or added relevant line in 1 file are covered.
5 unchanged lines in 2 files lost coverage.
Overall coverage decreased (-0.002%) to 89.782%

Files with Coverage Reduction	New Missed Lines	%
qiskit/transpiler/passes/synthesis/unitary_synthesis.py	2	88.2%
crates/qasm2/src/lex.rs	3	92.88%
<!--	Total:	5	-->

Totals
Change from base Build 9683280067:	-0.002%
Covered Lines:	63814
Relevant Lines:	71077

💛 - Coveralls

t-imamichi commented 6 days ago

Something may go wrong around qpy compatibility. But I have no idea what to do.

ShellyGarion commented 6 days ago

Something may go wrong around qpy compatibility. But I have no idea what to do.

merged!

t-imamichi commented 5 days ago

thanks!

Qiskit / qiskit