This commit expands the QkTarget API to support taking parameterized
gates that accept any angle value. Previously, this was not possible
because representing these gates internally in the target depended on
Python. That restriction has been removed with Qiskit#14799 and we can now
expose this functionality to C. This is a necessary component for being
able to build targets for current devices since they all typically
expose at least one gate that takes an arbitrary angle.

Fixes Qiskit#14704

This commit expands the QkTarget API to support taking parameterized
gates that accept any angle value. Previously, this was not possible
because representing these gates internally in the target depended on
Python. That restriction has been removed with Qiskit#14799 and we can now
expose this functionality to C. This is a necessary component for being
able to build targets for current devices since they all typically
expose at least one gate that takes an arbitrary angle.

Fixes Qiskit#14704

* Adding the MCX synthesis code based on PLDI24 paper

Co-authored-by: Jens Palsberg <palsberg@ucla.edu>
Co-authored-by: Keli Huang <kelihuang@cs.ucla.edu>

* Adding new funcion to init and docs

* adding test (for small values for the number of controls)

* adding plugin + test for the new method

* modifying the default MCX plugin to use the new method when appropriate

* adding release notes

* doctrings

* fixing comment about v24; adding more tests; improving bounds

* adding unitary simulator in Rust

Consructs a unitary matrix from a CircuitData with only unitary operations, exactly as
what Operator(quantum_circuit).data does.

The code is a simple wrapper on top of unitary_compose.

* adding simple test

* ignoring barriers during simulation

* change error to QiskitError

* splitting code into Rust and Python facing

* adding correctness test for increment_n_dirty

* improving release note

* improving documentation

* more docs

* updating the code following the changes in #14799

* disabling miri on the rust tests: it's way too slow

* updating release notes following review

---------

Co-authored-by: Jens Palsberg <palsberg@ucla.edu>
Co-authored-by: Keli Huang <kelihuang@cs.ucla.edu>

* Add support for parameterized gates to the Target C API

This commit expands the QkTarget API to support taking parameterized
gates that accept any angle value. Previously, this was not possible
because representing these gates internally in the target depended on
Python. That restriction has been removed with #14799 and we can now
expose this functionality to C. This is a necessary component for being
able to build targets for current devices since they all typically
expose at least one gate that takes an arbitrary angle.

Fixes #14704

* Apply suggestions from code review

Co-authored-by: Raynel Sanchez <87539502+raynelfss@users.noreply.github.com>

---------

Co-authored-by: Raynel Sanchez <87539502+raynelfss@users.noreply.github.com>

* Split py and py-free methods

* playing with Symbol as Parameter

-- 606 failing tests

* fix errors

* about to start the mess

* suite passing

* PVE in Rust

* start assign

* add assign

* dealing with unknown params and conflicts

* an attempt at vector fixing

* fix more tests

- name conflicts
- hash(2.3) == hash(ParamExpr(2.3))
- some error messages

* implement name_map as track record

This allows keeping track of which parameters are still in the expression, even though the expression is optimized. E.g. x*0 = 0, but x is still valid to bind.

* The string debacle

- don't use UUID in to_string, only in string_id (using strings for comparisons should probably be avoided in future)
- clippy
- relax Python is-checks to eq-checks

* some housekeeping

* implement _qpy_replay

* implement sympify

* fix copy/deepcopy

* Implement pickle via QPY and Parameter.assign to return Parameter

* fix template matching

this is rather a temporary solution, maybe we ought to disable string parsing in favor or a proper SymPy->parameter expression conversion

* fix rhs - lhs mixup

* fix more tests on binding {x: 0*y}

* fix last failing tests (see numeric(strict=False))

* clippy

* a lot of docs

* rename PyParameterExpression to ParameterExpression

* Thou shan't fake hyperrefs

* start to pull the thread on Param::ParameterExpression

* proper split: (Py)ParameterExpression

* rm pyclass from Symbol

* TODO's and no more RwLock

- rm Arc<RwLock<..>> for inner, since expressions are immutable and not shared, this is not needed
- address a bunch of todos, that include
  - rm rsub/rdiv/rpow
  - introduce try_to_value and _to_symbol
  - make internal data private

* First round of review comments

mainly removing some unnecessary clones, and fixing Hash for ParameterExpression

* rm `name_map` from PyParameterExpression

--- and just reconstruct the Py symbols from ParameterExpression.name_map

* Fix vector element parsing

Co-authored-by: "U-AzureAD\JUNDOI" doichan@jp.ibm.com

* more thread pulling

made the ParameterTable py-free

* finish 1st review round

mainly rm unused code and dangling comments

* fix symbol iteration

we want to iterate over name_map to capture 0*x, not the symbolic tree

* some problems with float/Param types left

* type fixes

A bunch of precautions around preserving integers and validating types, especially around Delay. One problem was that we used Param::Obj to represent bound, complex numbers, but this is now represented by Param::ParameterExpression. That means we need an additional "is numeric" check in the custom gate case, which we could've avoided before.

* resolve some todos, less py-paths

one thing we could investigate is if we can simplify the parameter table's logic around vector elements

* playing rm vector

* rm vector

* housekeeping

a bunch of renaming and removing py-specific comments

* add `CircuitData::parameters`

* Low hanging fruits

Mostly fixing up redundant allocations and preferring refs over values where possible

* Fix clippy failures

* Use Arc<Symbol> for SymbolExpr::Symbol

The size of Symbol is 56 bytes and when put in an enum for SymbolExpr
this brings the size of the enum up to 56 bytes because it's the largest
element. Since SymbolExpr ends up going in Param this brings Param up to
96 bytes from 16 prior to this PR which is a huge jump in the memory
footprint for somethign we put on every instruction in the circuit
whether there is a parameter or not. This commit boxes the symbol in
SymbolExpr to reduce the footprint of the enum down to 32 bytes because
of the Value field which is 24 bytes and the rest is because of 8 byte
alignment and the discriminant. This brings the Param enum down to 72
bytes which is still huge compared to the original 16 but is an
improvement. The next step here is going to be to box
`ParameterExpression` in `Param::ParameterExpression` which will reduce
it to 8 bytes in the Param enum and shrink the footprint back to it's
original size. In a follow up PR we should investigate optimizing the
memory footprint of SymbolExpr even more because the overhead is quite
high right now.

* Use Box<ParameterExpression> for Param::ParameterExpression

The Param::ParameterExpression object contains a ParameterExpression
object which is quite large compared to when it was just a PyObject.
When it was a PyObject it took 8 bytes because a PyObject is just a
pointer to the Python heap. However, the new ParameterExpression object
is significantly larger at 72 bytes, 32 bytes for the SymbolExpr (after
the previous commit) and 40 bytes for the HashMap. Putting this directly
in the enum makes each instance of Param 72 bytes even if there is no
parameter expressions in the circuit. This balloons the memory usage of
Qiskit everywhere because we've just increased the memory footprint of
anything with parameters 4.5x (Param was 16 bytes before because of
the discriminant and alignment). While we should work to reduce the memory
footprint and improve the efficiency of the `ParameterExpression` type
as much as we can, it's unlikely we'll ever get a `ParameterExpression`
down to 8 bytes. This commit updates Param::ParameterExpression to
contain a Box<ParameterExpression> instead so that we're only storing a
pointer to a heap allocated ParameterExpression object which reduces the
size of Param back to what it was prior to this PR branch.

* Move int and complex back to Param::Obj

The Param enum was intended to provide a quick low overhead check to
filter based on whether an instruction has real values, an expression,
or something custom defined for Python gates. In the Python data model
literally any object could be a "parameter" for a gate, as long as a
subclass overrides `.validate_parameter()` to say something is allowed.
The rust data model is more explicit in that everything is either a
float or a parameter expression in Rust, and anything outside of that is
necessarily something custom for a Python object (int is the exception
as it should be allowed in the data model but historically wasn't
because nothing ported to rust prior to Delay needed it, this will need
to be fixed). This is true for numeric types that ParameterExpression
can work with, mainly integer and complex numbers. If they are present
as a param that is only valid for an object coming from Python and
aren't part of the core data model. This enables things consuming
circuits in Rust to be able to filter out contextually on whether
something is parameterized or not.

Previously this PR branch moved these numeric types to be in the
Param::ParameterExpression where they can be stored in their rust
native data type (although arguably int was lossy and could cause
issues for values outside what's expressible in `i64`). However this
broke the above assumptions which added a special condition on anything
consuming parameters in Rust, where `Param::ParameterExpression` became
the indicator of a parameter expression or parameter that was unbound
or a numeric int or complex number in custom contexts from Python. This
was a potential source of bugs as any user of the Param interface would
need to know that they might have to check ParameterExpression manually
even if their operations didn't support unbound expression. Mostly this
would likely come up in transpiler passes that often have short cuts
like:

```rust
if matches!(param, Param::ParameterExpression(_)) {
    continue;
}
```

which might not be correct if there is a bound numeric value in the
expression. This commit switches the logic back to using `Obj` to
indicate a custom Python parameter object. Even if it is a numeric
value that could be represented by a bound `ParameterExpression`

A follow up here though is we should actually define int in `Param`
so we can correctly model `dt` for Delay in Rust space. As this is part
of our standard data model, even if it's only for a single type.

* Clarify ParameterTable comment

* Tune PyParameterExpression::extract_coerce()

This commit updates the extract_coerce() method of the
PyParameterExpression struct. During binding (called from Python) this
method gets called for every value and param in the bind input so the
runtime performance is very important for binding performance. Since
the method relies on basically python type checking with python
pseudocode logic like:

```python
if isinstance(x, int):
    return_expr = Value(int)
elif isinstance(x, float):
    return_expr = Value(float)
elif isinstance(x, complex):
    return_expr = Value(complex)
elif isinstance(x, ParameterVector):
    return_expr = Symbol(vector_element)
elif isinstance(x, Parameter)
    return_expr = Symbol(param)
else:
    return_expr = x
```

we need each successive check to be as fast as possible for the overall
function performance. The function previously was using
`Bound::extract()` to do the type checking here, but this is
unecessarily heavy weight especially in the negative case. This is
because it builds a real PyErr to return to the user, while we don't
actually ever use the Err case so it's safe to ignore it. This was
actually visible in profiles, especially for Complex which building the
result object was particularly prominent. The `.downcast()` method lets
us do a faster validation of the Python type before converting it to a
rust object avoiding this overhead. This is actually called out in the
performance guidance in the PyO3 user guide:

https://pyo3.rs/v0.25.1/performance.html#extract-versus-downcast

* Add parameter tracking to CircuitData convenience push methods

CircuitData had two methods `push_standard_gate()` and
`push_packed_operation()` which are convenience methods for appending
gates to a circuit from rust. Prior to this PR those only would have
ever received `Param::Float()` for their parameter input in a rust
context because Parameters were the domain of Python. As a small
optimization those methods skipped calling the parameter tracking
routine because it was essentially a no-op and unnecessary overhead
because there was never the possibility of anything needing to be
tracked. However, this has now changed with this PR and those
functions need to be tracking any Parameters they receive before adding
an operation to the circuit. This commit fixes this oversight and
changes the `self.data.push()` used internally to append to the
instruction vec to `self.push()` which does the same thing but also
has parameter tracking.

This has the knock-on effect of causing a PyResult<()> to be returned
by these methods because the tracking currently returns a PyResult. In
the C API in particular these are ignored because there is no context
from the existing C API where parameters can exist so the tracking call
is a no-op and won't ever return an Err.

* Switch from .expect() to .unwrap() in cext/circuit.rs

The error condition isn't triggerable from the C API so instead of
having a message saying the impossible input is not valid, just calling
unwrap() is less verbose.

* Fix typo symbolj -> symbol

* Update comment about the Python path in parameter binding for clarity

* Switch Param::ParameterExpression from Box<_> to Arc<_>

This commit updates the Param::ParameterExpression variant to store an
`Arc<ParameterExpression>` instead of `Box<ParameterExpression>`.
Internally the expression is all shared references with reference counting
and this also more closely models behavior from when it was previously a
PyObject (where `.clone()` was a ref count bump and not a full copy).

* Only implement IntoPyObject for owned ParameterExpression

The impl of IntoPyObject was previously only implemented for a borrowed
ParameterExpression, which was just hiding a clone inside the impl. It's
better to be explicit about this and require the user clone manually so
they're aware of it. This commit switches the impl to be on
the owned ParameterExpression and updates the usage to explicitly clone.

* Standardize on symbol naming convention for ParameterTable api

* Remove duplicate Symbol::coerce_into_py() method

This is just duplicated from the IntoPyObject impl.

* Remove stale comment

* Fix TODO comment in qasm3 experimental exporter

* Clarify comment on custom IntoPyObject impl

* Add TODO comment about not using Box<dyn Iterator>

---------

Co-authored-by: Matthew Treinish <mtreinish@kortar.org>