Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We鈥檒l occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

馃悰 Incorrect stripping of idle qubits that are not idle in both circuits #372

Closed
burgholzer opened this issue Feb 28, 2024 · 2 comments 路 Fixed by #394
Closed

馃悰 Incorrect stripping of idle qubits that are not idle in both circuits #372

burgholzer opened this issue Feb 28, 2024 · 2 comments 路 Fixed by #394
Labels
bug Something isn't working c++ Anything related to C++ code good first issue Good for newcomers

Comments

@burgholzer
Copy link
Member

Environment information

Any OS or Python version. Dates back to the very beginning of QCEC.

Description

If two circuits work on the same number of qubits and one of them has an idle qubit (a qubit that does not have a gate acting on it), the equivalence check might fail because the output permutations of the circuits might not match after the idle qubit in one circuit has been stripped.

This behavior is a result of the fact that the circuits are stripped of idle qubits in isolation, i.e., without considering the other circuit.

mqt-qcec/src/EquivalenceCheckingManager.cpp

Lines 210 to 212 in 5d9cbc1

// strip away qubits that are not acted upon
this->qc1.stripIdleQubits();
this->qc2.stripIdleQubits();

Expected behavior

An idle qubit should only be removed if it either

  • is idle in both circuits
  • is idle in one and does not exist in the other circuit

This requires a dedicated stripIdleQubits method in QCEC that considers both circuits in conjunction.
A corresponding implementation can be heavily inspired by the original mqt-core implementation.
However, I believe that the overall logic could even be improved a little bit given the constrained setting here in QCEC.

How to Reproduce

TEST_F(EqualityTest, NotEqualBecauseOfIdleQubitStripping) {
  // we measure only the second qubit
  qc1 = qc::QuantumComputation(2, 1);
  qc1.h(0);
  qc1.x(1);
  qc1.measure(1, 0);
  qc1.setLogicalQubitGarbage(0);

  // the first qubit doesn't have gates here, so stripIdleQubits() will remove
  // it and change the output permutation accordingliy
  qc2 = qc::QuantumComputation(2, 1);
  qc2.x(1);
  qc2.measure(1, 0);
  qc2.setLogicalQubitGarbage(0);

  // run the construction checker -> it will result in `NotEquivalent` because
  // the two circuits have a different output permutation after `stripIdleQubits()`
  config.execution.runConstructionChecker = true;
  ec::EquivalenceCheckingManager ecm(qc1, qc2, config);
  ecm.run();
  EXPECT_EQ(ecm.equivalence(), ec::EquivalenceCriterion::NotEquivalent);
}

Thanks @reb-ddm for bringing this up!
@burgholzer burgholzer added bug Something isn't working good first issue Good for newcomers c++ Anything related to C++ code labels Feb 28, 2024
@clerusch
Copy link

clerusch commented Apr 17, 2024 •
edited

I think I am having a related issue:
If I try to run the following circuit in its qecc variant:
image
The ecc circuit associated with the second two qubits before the red circle looks like this, encoding only two qubits (17 physical):
image
While encoding the circuit after the circle looks like this, encoding all 4 qubits (31 physical):
image
It would therefore appear that the CNOT connection between the first two qubits circuit to the second two qubits circuit at the start is optimized away due to being empty controls.
This is a problem, because while it might seem like CNOTs controlled from qf2.0 in the |0> state would be irrelevant, since they dont change the target qubit, they actually do affect the state in the control qubit qf2.0 if the target qubit is not in a Z eigenstate.

@burgholzer
Copy link
Member Author

I think I am having a related issue: If I try to run the following circuit in its qecc variant: image The ecc circuit associated with the second two qubits before the red circle looks like this, encoding only two qubits (17 physical): image While encoding the circuit after the circle looks like this, encoding all 4 qubits (31 physical): image It would therefore appear that the CNOT connection between the first two qubits circuit to the second two qubits circuit at the start is optimized away due to being empty controls. This is a problem, because while it might seem like CNOTs controlled from qf2.0 in the |0> state would be irrelevant, since they dont change the target qubit, they actually do affect the state in the control qubit qf2.0 if the target qubit is not in a Z eigenstate.

I am fairly sure this is not related to the issue above as QCEC does not optimize away these kinds of gates. As you say, they do influence the overall functionality.
However, I am not quite confident that QCEC can even handle the two circuits you show here. First, its dynamic quantum circuit support is still rather experimental. Secondly, these circuits do not act on the same number of qubits; so I am not quite sure how the equivalence check would even work in that case conceptually.

Could you maybe provide some more information on your particular setting and maybe even the circuits you are trying to verify? Either QASM2 or Qiskit QPY or Qiskit Code to generate the circuits would work.

@TeWas TeWas mentioned this issue May 8, 2024
Merged
4 tasks
burgholzer added a commit that referenced this issue May 23, 2024
@TeWas @burgholzer
馃悰 Fix strip idle qubits (#394)
1358f62 
## Description
This PR fixes the issue of incorrectly removing idle qubits that are not
idle in both circuits.
The following changes have been made:

* Previously, idle qubits were removed regardless of their status in
both circuits. Now, an idle qubit is removed only if:
   - it is idle in both circuits
   - it is idle in one circuit and does not exist in the other circuit
* To implement this logic, a dedicated method `stripIdleQubits` has been
created in QCEC. This method considers both circuits in conjunction
* The `stripIdleQubits` method:
- examines each logical qubit in the `initialLayout` of the larger
circuit
  - checks if the corresponding physical qubit is idle
  - then searches for this logical qubit in the other circuit
- if the corresponding physical qubit in the other circuit is also idle,
then the logical and corresponding physical qubit are removed from each
circuit, respectively, under the following conditions:
- neither the logical nor the physical qubit appears in the output
permutation (applies to both circuits)
- or if the initial and output permutations match for this qubit
(applies to both circuits)
- if an idle logical qubit is present in one circuit only, it is
removed, if neither the logical nor the physical qubit appears in the
output permutation, or the initial and output permutations match for
this qubit

Fixes #372 

## Checklist:

<!---
This checklist serves as a reminder of a couple of things that ensure
your pull request will be merged swiftly.
-->

- [x] The pull request only contains commits that are related to it.
- [x] I have added appropriate tests and documentation.
- [x] I have made sure that all CI jobs on GitHub pass.
- [x] The pull request introduces no new warnings and follows the
project's style guidelines.

---------

Signed-off-by: burgholzer <burgholzer@me.com>
Co-authored-by: burgholzer <burgholzer@me.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug Something isn't working c++ Anything related to C++ code good first issue Good for newcomers
Projects
MQT
Status: Done
MQT Verification
Status: Done
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

馃悰 Fix strip idle qubits TeWas/mqt-qcec
2 participants
@burgholzer @clerusch