Qiskit / qiskit

Qiskit is an open-source SDK for working with quantum computers at the level of extended quantum circuits, operators, and primitives.
https://www.ibm.com/quantum/qiskit
Apache License 2.0
5.04k stars 2.32k forks source link

Add builtin interner index for empty qubits or clbits #12932

Open mtreinish opened 1 month ago

mtreinish commented 1 month ago

I have a change to the interners I want to make once the DAGCircuit PR merges that will avoid the need for the Vec here in favour of the static empty slice (which is at least a small saving), but I think the idea of the special "intern key to the 'zero' object" is a good one too. I can see it coming up a lot, and I think it's doable without losing any particular generality in the interners - we can make it like

pub struct Interner<T> { ... };
pub struct InternKey<T> {
   index: u32,
   _phantom: PhantomData<T>,
};
impl<T: Default> InternKey<T> {
    pub fn empty() -> Self {
        Self {
            val: 0,
            _phantom: PhantomData,
        }
    }
}

or something like that, and arrange that the 0 index of Interner<T: Default> always corresponds to <T as Default>::default().

_Originally posted by @jakelishman in https://github.com/Qiskit/qiskit/pull/12809#discussion_r1709932633_

jakelishman commented 1 month ago

I thought about this more overnight, and I think that while specialisation isn't a stable part of Rust, it's hard to make the exact API I sketched above work exactly right, unless we require T: Default for all Interner generics - the trick is that Interner::<T>::new needs to always enforce that the default entry is always created (if T: Default), and we need specialisation for that to work natively.

I think overall the general scheme works, just the API I roughly sketched in the comment isn't 100% there yet.