What should we add?

The tweedledum external library is currently used inside qiskit extensively in the circuit.classical library. It is used when parsing boolean and Python expressions to generate an inner representation (ClassicalFunction), to read cnf representations from DIMACS files (BooleanExpression), and to simulate and synthesize quantum circuits for those functions, especially as part of PhaseOracle.

However, it seems the library is no longer maintained and we need to drop it as part of the 2.0.0 release.

Essentially, this requires us to provide different ways to:

1. Parse Python expressions.
2. Parse DIMACS file (or drop support)
3. Simulate (i.e. evaluate) the resulting expressions on bitstrings.
4. Synthesize the expressions to QuantumCircuit.

Doing 1 and 2 is very simply and can be done with not major changes to the code; doing 1 requires some modification of how ClassicalFunctionVisitor works since currently it relies on tweedledum's LogicNetwork class. For 2, since DIMACS is a very simply file format, parsing can be done via a small standalone function

Given convenient representations resulting from 1+2, doing 3 is also fairly simple, leaving 4 as the only real obstacle. The synthesis of a quantum circuit for a given logical expression is highly dependent on the complexity of the representation of the expression. Currently, tweedledum uses a method that relies on the ESOP (exclusive sum of products) for small number of variables, and a method based on XAG (xor-and graph) for more complex expressions; see Bruno Schmitt's description here.

Obtaining a convenient ESOP representation in cases where the truth table for the expression can be conveniently computed (i.e. given a way to do 3) is straightforward, and given such an ESOP, synthesizing a circuit is immediate. However, dropping tweedledum's support means we'll encounter difficulty in handling more complex expressions where there are too many variables to compute the truth table. In the future we can explore the idea of using more robust tools such as Z3 for optimizing this stage. For the 2.0.0 release I suggest we focus on removing the reliance on tweedledum with minimal interface changes, in the cost of being unusable for some cases.

Note, however, that since synthesizing ESOP is always easy, we can add a new feature for the user to supply the ESOP directly, in addition to 1+2, so the expression optimization stage can be done by the user with his libraries of choice.