Support Qubit & Label Placeholders

[kalzoo]

pyQuil has the capability to insert placeholders for qubits and labels into a program, and quil-rs should support the same concept.

These have no analogue in Quil itself and no serialized form, but are an aid in the construction of valid Quil programs. Both serve as a reference which defers the assignment of a concrete value until later.

Labels

A label placeholder is useful for writing portions of a program in isolation without the concern that a label will conflict with labels in other parts of the program. This is especially important for support of dynamic control flow programs. Imagine that a user may want a program with multiple loops, each of which starts with a label @loop-start.

A label must be unique within a program, so if the user must assign a concrete label value at the time of label construction they must consider all labels already present within the program. With a placeholder, though, they can use Placeholder("loop-start") in several places, and allow the program to distinguish these prior to serialization - perhaps by adding a suffix.

Qubits

Similarly, a routine within a program may want to reference some set of qubits without yet resolving which ones those are. Like labels, this allows for qubits to be isolated to a particular scope within a program while remaining unique at the program scope.

API

Placeholders can be allocated as such:

QubitPlaceholder::new();
LabelPlaceholder::new("label");

They can then be used within the relevant enums. This will be a breaking change:

enum Qubit {
  Fixed(...),
  Variable(...),
  Placeholder(QubitPlaceholder)
}

enum Label {
  Fixed(String), // This is the existing use case, now as an enum variant
  Placeholder(LabelPlaceholder), // This is new
}

These placeholders cannot be resolved in isolation; they must be resolved within / by a Program. So add a relevant method:

impl Program {
  pub fn resolve_label_placeholders(&mut self) {
    // collect all the existing labels in the program, and then iterate through placeholders and resolve each one to a string label, appending a numeric suffix to make each unique as needed.
  }

  pub fn resolve_qubit_placeholders(&mut self) {
    // collect all the existing fixed qubits in the program and then iterate through, resolving each to the lowest-available fixed qubit index
  }

  pub fn resolve_placeholders(&mut self) {
    self.resolve_label_placeholders();
    self.resolve_qubit_placeholders();
  }
}

impl fmt::Display for Program {
   // ... resolve_placeholders is called prior to display, because there is no Quil-spec-defined way to serialize a label or qubit placeholder
}

[notmgsk]

A nice to have would be resolve_qubit_placeholders_with(&mut self, available: &impl Iter) -> Result<()> (or maybe it takes a fn instead) so that the user can restrict the assigned qubits to e.g. physical qubit indices.

[kalzoo]

A nice to have would be resolve_qubit_placeholders_with(&mut self, available: &impl Iter) -> Result<()> (or maybe it takes a fn instead) so that the user can restrict the assigned qubits to e.g. physical qubit indices.

That seems useful. When it comes to a full function though, it would make sense for the user to just iterate over the program themselves - this resolution method is more of a convenience than a necessity, because the user will have the capability to iterate and resolve on the program directly.

[MarquessV]

@kalzoo Just to clarify, how are we going to resolve placeholders inside of the display implementation since it would require &mut self? Are we going to clone the program every time it's called?

[kalzoo]

Are we going to clone the program every time it's called?

This is what I had imagined, as unfortunate as that would be. Been thinking about how to be more clever about this within the existing API. Cow might help, allowing us to avoid a clone if no placeholders were present.

Another option - resolve placeholders within each instruction as it is written, without storing them back on the program.

[MarquessV]

Done in #266