Repository: microsoft/qsharp
Pull request #1539 (2024-05-17 16:57:01)

RCA check for use of dynamic rhs in exponent binop
This adds a special case to RCA for the rhs of exponentiation that adds a `UseOfDynamicExponent` feature flag if appropriate. This can then be used to tie dynamic exponentiation to backward branching (aka looping) which is needed to support such exponentiation.

github-actions[bot]: ## Benchmark for 3077da7
  <details>
    <summary>Click to view benchmark</summary>

| Test | Base         | PR               | % |
|------|--------------|------------------|---|
| Array append evaluation | 326.1±6.40µs | 325.1±2.59µs | -0.31% |
| Array literal evaluation | 182.8±2.02µs | **171.4±1.12µs** | **-6.24%** |
| Array update evaluation | 409.6±10.96µs | 408.6±2.58µs | -0.24% |
| Core + Standard library compilation | **17.0±0.32ms** | 20.0±1.41ms | **+17.65%** |
| Deutsch-Jozsa evaluation | 5.0±0.16ms | 5.0±0.04ms | 0.00% |
| Large file parity evaluation | **34.0±0.09ms** | 34.1±0.35ms | **+0.29%** |
| Large input file compilation | 11.9±0.32ms | **11.7±0.12ms** | **-1.68%** |
| Large input file compilation (interpreter) | **45.6±1.64ms** | 49.3±1.70ms | **+8.11%** |
| Large nested iteration | 32.4±1.06ms | 32.3±0.15ms | -0.31% |
| Perform Runtime Capabilities Analysis (RCA) on Deutsch-Jozsa sample | 1550.0±33.90µs | 1551.8±50.74µs | +0.12% |
| Perform Runtime Capabilities Analysis (RCA) on large file sample | 8.1±0.13ms | **7.7±0.14ms** | **-4.94%** |
| Perform Runtime Capabilities Analysis (RCA) on teleport sample | 1414.0±30.92µs | 1409.7±35.18µs | -0.30% |
| Perform Runtime Capabilities Analysis (RCA) on the core and std libraries | **27.1±0.22ms** | 27.5±0.64ms | **+1.48%** |
| Teleport evaluation | 88.2±4.38µs | 89.1±5.96µs | +1.02% |

  </details>
  

Patch:
diff --git a/.gitignore b/.gitignore
index 8cbb2b66..70b96253 100644
--- a/.gitignore
+++ b/.gitignore
@@ -17,3 +17,4 @@ __pycache__/
 /fuzz/Cargo.lock
 .mypy_cache/
 .pytest_cache/
+.idea/
diff --git a/Cargo.lock b/Cargo.lock
index a057a2fc..fc61bd3a 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -1007,6 +1007,7 @@ dependencies = [
  "bitflags 2.4.2",
  "expect-test",
  "miette",
+ "rustc-hash",
  "serde",
 ]
 
diff --git a/Cargo.toml b/Cargo.toml
index e5f49900..14c03b40 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -82,8 +82,8 @@ missing_panics_doc = "allow"
 module_name_repetitions = "allow"
 
 [profile.release]
-debug = 1
-strip = true
+debug = "limited"
+strip = "symbols"
 lto = "fat"
 codegen-units = 1
 
diff --git a/compiler/qsc/src/interpret/debug.rs b/compiler/qsc/src/interpret/debug.rs
index 013075e7..f60a1378 100644
--- a/compiler/qsc/src/interpret/debug.rs
+++ b/compiler/qsc/src/interpret/debug.rs
@@ -10,6 +10,7 @@ use qsc_frontend::compile::PackageStore;
 use qsc_hir::hir;
 use qsc_hir::hir::{Item, ItemKind};
 use qsc_lowerer::map_fir_package_to_hir;
+use std::rc::Rc;
 
 #[must_use]
 pub(crate) fn format_call_stack(
@@ -82,10 +83,9 @@ fn get_item_file_name(store: &PackageStore, id: StoreItemId) -> Option<String> {
 }
 
 #[must_use]
-fn get_ns_name(item: &Item) -> Option<String> {
-    if let ItemKind::Namespace(ns, _) = &item.kind {
-        Some(ns.name.to_string())
-    } else {
-        None
-    }
+fn get_ns_name(item: &Item) -> Option<Rc<str>> {
+    let ItemKind::Namespace(ns, _) = &item.kind else {
+        return None;
+    };
+    Some(ns.name())
 }
diff --git a/compiler/qsc/src/lib.rs b/compiler/qsc/src/lib.rs
index 4712f815..be716ff6 100644
--- a/compiler/qsc/src/lib.rs
+++ b/compiler/qsc/src/lib.rs
@@ -34,7 +34,7 @@ pub mod project {
 }
 
 pub use qsc_data_structures::{
-    language_features::LanguageFeatures, span::Span, target::TargetCapabilityFlags,
+    language_features::LanguageFeatures, namespaces::*, span::Span, target::TargetCapabilityFlags,
 };
 
 pub use qsc_passes::{lower_hir_to_fir, PackageType, PassContext};
diff --git a/compiler/qsc_ast/src/ast.rs b/compiler/qsc_ast/src/ast.rs
index be3f5996..29f7400b 100644
--- a/compiler/qsc_ast/src/ast.rs
+++ b/compiler/qsc_ast/src/ast.rs
@@ -164,7 +164,7 @@ pub struct Namespace {
     /// The documentation.
     pub doc: Rc<str>,
     /// The namespace name.
-    pub name: Box<Ident>,
+    pub name: Idents,
     /// The items in the namespace.
     pub items: Box<[Box<Item>]>,
 }
@@ -259,7 +259,7 @@ pub enum ItemKind {
     #[default]
     Err,
     /// An `open` item for a namespace with an optional alias.
-    Open(Box<Ident>, Option<Box<Ident>>),
+    Open(Idents, Option<Box<Ident>>),
     /// A `newtype` declaration.
     Ty(Box<Ident>, Box<TyDef>),
 }
@@ -1273,7 +1273,7 @@ pub struct Path {
     /// The span.
     pub span: Span,
     /// The namespace.
-    pub namespace: Option<Box<Ident>>,
+    pub namespace: Option<Idents>,
     /// The declaration name.
     pub name: Box<Ident>,
 }
@@ -1306,6 +1306,133 @@ pub struct Ident {
     pub name: Rc<str>,
 }
 
+/// A [`Idents`] represents a sequence of idents. It provides a helpful abstraction
+/// that is more powerful than a simple `Vec<Ident>`, and is primarily used to represent
+/// dot-separated paths.
+#[derive(Clone, Debug, Eq, Hash, PartialEq, Default)]
+pub struct Idents(pub Box<[Ident]>);
+
+impl From<Idents> for Vec<Rc<str>> {
+    fn from(v: Idents) -> Self {
+        v.0.iter().map(|i| i.name.clone()).collect()
+    }
+}
+
+impl From<&Idents> for Vec<Rc<str>> {
+    fn from(v: &Idents) -> Self {
+        v.0.iter().map(|i| i.name.clone()).collect()
+    }
+}
+
+impl From<Vec<Ident>> for Idents {
+    fn from(v: Vec<Ident>) -> Self {
+        Idents(v.into_boxed_slice())
+    }
+}
+
+impl From<Idents> for Vec<Ident> {
+    fn from(v: Idents) -> Self {
+        v.0.to_vec()
+    }
+}
+
+impl Display for Idents {
+    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
+        let mut buf = Vec::with_capacity(self.0.len());
+
+        for ident in self.0.iter() {
+            buf.push(format!("{ident}"));
+        }
+        if buf.len() > 1 {
+            // use square brackets only if there are more than one ident
+            write!(f, "[{}]", buf.join(", "))
+        } else {
+            write!(f, "{}", buf[0])
+        }
+    }
+}
+
+impl<'a> IntoIterator for &'a Idents {
+    type IntoIter = std::slice::Iter<'a, Ident>;
+    type Item = &'a Ident;
+    fn into_iter(self) -> Self::IntoIter {
+        self.iter()
+    }
+}
+
+impl<'a> From<&'a Idents> for IdentsStrIter<'a> {
+    fn from(v: &'a Idents) -> Self {
+        IdentsStrIter(v)
+    }
+}
+
+/// An iterator which yields string slices of the names of the idents in a [`Idents`].
+/// Note that [`Idents`] itself only implements [`IntoIterator`] where the item is an [`Ident`].
+pub struct IdentsStrIter<'a>(pub &'a Idents);
+
+impl<'a> IntoIterator for IdentsStrIter<'a> {
+    type IntoIter = std::iter::Map<std::slice::Iter<'a, Ident>, fn(&'a Ident) -> &'a str>;
+    type Item = &'a str;
+    fn into_iter(self) -> Self::IntoIter {
+        self.0.iter().map(|i| i.name.as_ref())
+    }
+}
+
+impl FromIterator<Ident> for Idents {
+    fn from_iter<T: IntoIterator<Item = Ident>>(iter: T) -> Self {
+        Idents(iter.into_iter().collect())
+    }
+}
+
+impl From<Path> for Idents {
+    fn from(p: Path) -> Self {
+        let mut buf = p.namespace.unwrap_or_default().0.to_vec();
+        buf.push(*p.name);
+        Self(buf.into_boxed_slice())
+    }
+}
+
+impl Idents {
+    /// constructs an iterator over the [Ident]s that this contains.
+    /// see [`Self::str_iter`] for an iterator over the string slices of the [Ident]s.
+    pub fn iter(&self) -> std::slice::Iter<'_, Ident> {
+        self.0.iter()
+    }
+
+    /// constructs an iterator over the elements of `self` as string slices.
+    /// see [`Self::iter`] for an iterator over the [Ident]s.
+    #[must_use]
+    pub fn str_iter(&self) -> IdentsStrIter {
+        self.into()
+    }
+
+    /// the conjoined span of all idents in the `VecIdent`
+    #[must_use]
+    pub fn span(&self) -> Span {
+        Span {
+            lo: self.0.first().map(|i| i.span.lo).unwrap_or_default(),
+            hi: self.0.last().map(|i| i.span.hi).unwrap_or_default(),
+        }
+    }
+
+    /// The stringified dot-separated path of the idents in this [`Idents`]
+    /// E.g. `a.b.c`
+    #[must_use]
+    pub fn name(&self) -> Rc<str> {
+        if self.0.len() == 1 {
+            return self.0[0].name.clone();
+        }
+        let mut buf = String::new();
+        for ident in self.0.iter() {
+            if !buf.is_empty() {
+                buf.push('.');
+            }
+            buf.push_str(&ident.name);
+        }
+        Rc::from(buf)
+    }
+}
+
 impl Default for Ident {
     fn default() -> Self {
         Ident {
diff --git a/compiler/qsc_ast/src/mut_visit.rs b/compiler/qsc_ast/src/mut_visit.rs
index 8b47a31b..78ede9bf 100644
--- a/compiler/qsc_ast/src/mut_visit.rs
+++ b/compiler/qsc_ast/src/mut_visit.rs
@@ -76,6 +76,10 @@ pub trait MutVisitor: Sized {
         walk_ident(self, ident);
     }
 
+    fn visit_idents(&mut self, ident: &mut crate::ast::Idents) {
+        walk_idents(self, ident);
+    }
+
     fn visit_span(&mut self, _: &mut Span) {}
 }
 
@@ -89,7 +93,8 @@ pub fn walk_package(vis: &mut impl MutVisitor, package: &mut Package) {
 
 pub fn walk_namespace(vis: &mut impl MutVisitor, namespace: &mut Namespace) {
     vis.visit_span(&mut namespace.span);
-    vis.visit_ident(&mut namespace.name);
+    vis.visit_idents(&mut namespace.name);
+
     namespace.items.iter_mut().for_each(|i| vis.visit_item(i));
 }
 
@@ -104,7 +109,7 @@ pub fn walk_item(vis: &mut impl MutVisitor, item: &mut Item) {
         ItemKind::Callable(decl) => vis.visit_callable_decl(decl),
         ItemKind::Err => {}
         ItemKind::Open(ns, alias) => {
-            vis.visit_ident(ns);
+            vis.visit_idents(ns);
             alias.iter_mut().for_each(|a| vis.visit_ident(a));
         }
         ItemKind::Ty(ident, def) => {
@@ -333,10 +338,18 @@ pub fn walk_qubit_init(vis: &mut impl MutVisitor, init: &mut QubitInit) {
 
 pub fn walk_path(vis: &mut impl MutVisitor, path: &mut Path) {
     vis.visit_span(&mut path.span);
-    path.namespace.iter_mut().for_each(|n| vis.visit_ident(n));
+    if let Some(ref mut ns) = path.namespace {
+        vis.visit_idents(ns);
+    }
     vis.visit_ident(&mut path.name);
 }
 
 pub fn walk_ident(vis: &mut impl MutVisitor, ident: &mut Ident) {
     vis.visit_span(&mut ident.span);
 }
+
+pub fn walk_idents(vis: &mut impl MutVisitor, ident: &mut crate::ast::Idents) {
+    for ref mut ident in ident.0.iter_mut() {
+        vis.visit_ident(ident);
+    }
+}
diff --git a/compiler/qsc_ast/src/visit.rs b/compiler/qsc_ast/src/visit.rs
index f9afe8b0..d16f2f34 100644
--- a/compiler/qsc_ast/src/visit.rs
+++ b/compiler/qsc_ast/src/visit.rs
@@ -3,9 +3,9 @@
 
 use crate::ast::{
     Attr, Block, CallableBody, CallableDecl, Expr, ExprKind, FunctorExpr, FunctorExprKind, Ident,
-    Item, ItemKind, Namespace, Package, Pat, PatKind, Path, QubitInit, QubitInitKind, SpecBody,
-    SpecDecl, Stmt, StmtKind, StringComponent, TopLevelNode, Ty, TyDef, TyDefKind, TyKind,
-    Visibility,
+    Idents, Item, ItemKind, Namespace, Package, Pat, PatKind, Path, QubitInit, QubitInitKind,
+    SpecBody, SpecDecl, Stmt, StmtKind, StringComponent, TopLevelNode, Ty, TyDef, TyDefKind,
+    TyKind, Visibility,
 };
 
 pub trait Visitor<'a>: Sized {
@@ -72,6 +72,10 @@ pub trait Visitor<'a>: Sized {
     }
 
     fn visit_ident(&mut self, _: &'a Ident) {}
+
+    fn visit_idents(&mut self, idents: &'a Idents) {
+        walk_idents(self, idents);
+    }
 }
 
 pub fn walk_package<'a>(vis: &mut impl Visitor<'a>, package: &'a Package) {
@@ -83,7 +87,7 @@ pub fn walk_package<'a>(vis: &mut impl Visitor<'a>, package: &'a Package) {
 }
 
 pub fn walk_namespace<'a>(vis: &mut impl Visitor<'a>, namespace: &'a Namespace) {
-    vis.visit_ident(&namespace.name);
+    vis.visit_idents(&namespace.name);
     namespace.items.iter().for_each(|i| vis.visit_item(i));
 }
 
@@ -94,7 +98,7 @@ pub fn walk_item<'a>(vis: &mut impl Visitor<'a>, item: &'a Item) {
         ItemKind::Err => {}
         ItemKind::Callable(decl) => vis.visit_callable_decl(decl),
         ItemKind::Open(ns, alias) => {
-            vis.visit_ident(ns);
+            vis.visit_idents(ns);
             alias.iter().for_each(|a| vis.visit_ident(a));
         }
         ItemKind::Ty(ident, def) => {
@@ -300,6 +304,12 @@ pub fn walk_qubit_init<'a>(vis: &mut impl Visitor<'a>, init: &'a QubitInit) {
 }
 
 pub fn walk_path<'a>(vis: &mut impl Visitor<'a>, path: &'a Path) {
-    path.namespace.iter().for_each(|n| vis.visit_ident(n));
+    if let Some(ref ns) = path.namespace {
+        vis.visit_idents(ns);
+    }
     vis.visit_ident(&path.name);
 }
+
+pub fn walk_idents<'a>(vis: &mut impl Visitor<'a>, idents: &'a Idents) {
+    idents.iter().for_each(|i| vis.visit_ident(i));
+}
diff --git a/compiler/qsc_codegen/src/qsharp.rs b/compiler/qsc_codegen/src/qsharp.rs
index 51afd385..d4ea80b2 100644
--- a/compiler/qsc_codegen/src/qsharp.rs
+++ b/compiler/qsc_codegen/src/qsharp.rs
@@ -15,8 +15,8 @@ use std::vec;
 
 use qsc_ast::ast::{
     self, Attr, BinOp, Block, CallableBody, CallableDecl, CallableKind, Expr, ExprKind, Functor,
-    FunctorExpr, FunctorExprKind, Ident, Item, ItemKind, Lit, Mutability, Pat, PatKind, Path,
-    Pauli, QubitInit, QubitInitKind, QubitSource, SetOp, SpecBody, SpecDecl, SpecGen, Stmt,
+    FunctorExpr, FunctorExprKind, Ident, Idents, Item, ItemKind, Lit, Mutability, Pat, PatKind,
+    Path, Pauli, QubitInit, QubitInitKind, QubitSource, SetOp, SpecBody, SpecDecl, SpecGen, Stmt,
     StmtKind, StringComponent, TernOp, TopLevelNode, Ty, TyDef, TyDefKind, TyKind, UnOp,
     Visibility, VisibilityKind,
 };
@@ -104,7 +104,7 @@ impl<W: Write> Visitor<'_> for QSharpGen<W> {
 
     fn visit_namespace(&mut self, namespace: &'_ Namespace) {
         self.write("namespace ");
-        self.visit_ident(&namespace.name);
+        self.visit_idents(&namespace.name);
         self.writeln("{");
         namespace.items.iter().for_each(|i| {
             self.visit_item(i);
@@ -124,7 +124,7 @@ impl<W: Write> Visitor<'_> for QSharpGen<W> {
             ItemKind::Callable(decl) => self.visit_callable_decl(decl),
             ItemKind::Open(ns, alias) => {
                 self.write("open ");
-                self.visit_ident(ns);
+                self.visit_idents(ns);
                 if let Some(alias) = alias {
                     self.write(" as ");
                     self.visit_ident(alias);
@@ -710,8 +710,8 @@ impl<W: Write> Visitor<'_> for QSharpGen<W> {
     }
 
     fn visit_path(&mut self, path: &'_ Path) {
-        for ns in &path.namespace {
-            self.visit_ident(ns);
+        if let Some(ns) = &path.namespace {
+            self.visit_idents(ns);
             self.write(".");
         }
         self.visit_ident(&path.name);
@@ -720,6 +720,10 @@ impl<W: Write> Visitor<'_> for QSharpGen<W> {
     fn visit_ident(&mut self, id: &'_ Ident) {
         self.write(&id.name);
     }
+
+    fn visit_idents(&mut self, idents: &'_ Idents) {
+        self.write(&idents.name());
+    }
 }
 
 fn binop_as_str(op: &BinOp) -> &str {
diff --git a/compiler/qsc_data_structures/Cargo.toml b/compiler/qsc_data_structures/Cargo.toml
index bff76986..a5127b53 100644
--- a/compiler/qsc_data_structures/Cargo.toml
+++ b/compiler/qsc_data_structures/Cargo.toml
@@ -12,6 +12,7 @@ repository.workspace = true
 miette = { workspace = true }
 serde = { workspace = true }
 bitflags = { workspace = true }
+rustc-hash = { workspace = true }
 
 [dev-dependencies]
 expect-test = { workspace = true }
diff --git a/compiler/qsc_data_structures/src/index_map.rs b/compiler/qsc_data_structures/src/index_map.rs
index 657c33c5..557e82d8 100644
--- a/compiler/qsc_data_structures/src/index_map.rs
+++ b/compiler/qsc_data_structures/src/index_map.rs
@@ -14,6 +14,23 @@ pub struct IndexMap<K, V> {
     values: Vec<Option<V>>,
 }
 
+impl<K, V> IndexMap<K, V>
+where
+    K: Into<usize>,
+    V: Default,
+{
+    pub fn get_mut_or_default(&mut self, key: K) -> &mut V {
+        let index: usize = key.into();
+        if index >= self.values.len() {
+            self.values.resize_with(index + 1, Option::default);
+        }
+        self.values
+            .get_mut(index)
+            .expect("IndexMap::get_mut_or_default: index out of bounds")
+            .get_or_insert_with(Default::default)
+    }
+}
+
 impl<K, V> IndexMap<K, V> {
     #[must_use]
     pub fn new() -> Self {
diff --git a/compiler/qsc_data_structures/src/lib.rs b/compiler/qsc_data_structures/src/lib.rs
index 68fc178c..c7a24a9c 100644
--- a/compiler/qsc_data_structures/src/lib.rs
+++ b/compiler/qsc_data_structures/src/lib.rs
@@ -6,5 +6,6 @@ pub mod functors;
 pub mod index_map;
 pub mod language_features;
 pub mod line_column;
+pub mod namespaces;
 pub mod span;
 pub mod target;
diff --git a/compiler/qsc_data_structures/src/namespaces.rs b/compiler/qsc_data_structures/src/namespaces.rs
new file mode 100644
index 00000000..f80eda11
--- /dev/null
+++ b/compiler/qsc_data_structures/src/namespaces.rs
@@ -0,0 +1,293 @@
+// Copyright (c) Microsoft Corporation.
+// Licensed under the MIT License.
+
+#[cfg(test)]
+mod tests;
+
+use rustc_hash::FxHashMap;
+use std::{cell::RefCell, fmt::Display, iter::Peekable, ops::Deref, rc::Rc};
+
+pub const PRELUDE: [[&str; 3]; 4] = [
+    ["Microsoft", "Quantum", "Canon"],
+    ["Microsoft", "Quantum", "Core"],
+    ["Microsoft", "Quantum", "Intrinsic"],
+    ["Microsoft", "Quantum", "Measurement"],
+];
+
+/// An ID that corresponds to a namespace in the global scope.
+#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, Default)]
+pub struct NamespaceId(usize);
+impl NamespaceId {
+    /// Create a new namespace ID.
+    #[must_use]
+    pub fn new(value: usize) -> Self {
+        Self(value)
+    }
+}
+
+impl From<usize> for NamespaceId {
+    fn from(value: usize) -> Self {
+        Self::new(value)
+    }
+}
+
+impl From<NamespaceId> for usize {
+    fn from(value: NamespaceId) -> Self {
+        value.0
+    }
+}
+
+impl From<&NamespaceId> for usize {
+    fn from(value: &NamespaceId) -> Self {
+        value.0
+    }
+}
+
+impl Deref for NamespaceId {
+    type Target = usize;
+    fn deref(&self) -> &Self::Target {
+        &self.0
+    }
+}
+
+impl Display for NamespaceId {
+    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
+        write!(f, "Namespace {}", self.0)
+    }
+}
+
+/// A reference counted cell that supports interior mutability for namespace tree nodes.
+/// Interior mutability is required to update the tree when inserting new data structures.
+type NamespaceTreeCell = Rc<RefCell<NamespaceTreeNode>>;
+
+/// An entry in the memoization table for namespace ID lookups.
+type MemoEntry = (Vec<Rc<str>>, NamespaceTreeCell);
+
+/// The root of the data structure that represents the namespaces in a program.
+/// The tree is a trie (prefix tree) where each node is a namespace and the children are the sub-namespaces.
+/// For example, the namespace `Microsoft.Quantum.Canon` would be represented as a traversal from the root node:
+/// ```
+/// root
+/// └ Microsoft
+///   └ Quantum
+///     └ Canon
+/// ```
+/// This data structure is optimized for looking up namespace IDs by a given name. Looking up a namespace name by ID is
+/// less efficient, as it performs a breadth-first search. Because of this inefficiency, the results of this lookup are memoized.
+/// [`NamespaceTreeNode`]s are all stored in [`NamespaceTreeCell`]s, which are reference counted and support interior mutability for namespace
+/// insertions and clone-free lookups.
+#[derive(Debug, Clone)]
+pub struct NamespaceTreeRoot {
+    assigner: usize,
+    tree: NamespaceTreeCell,
+    memo: RefCell<FxHashMap<NamespaceId, MemoEntry>>,
+}
+
+impl NamespaceTreeRoot {
+    /// Create a new namespace tree root. The assigner is used to assign new namespace IDs.
+    #[must_use]
+    pub fn new_from_parts(assigner: usize, tree: NamespaceTreeNode) -> Self {
+        Self {
+            assigner,
+            tree: Rc::new(RefCell::new(tree)),
+            memo: RefCell::new(FxHashMap::default()),
+        }
+    }
+
+    /// Get the namespace tree field. This is the root of the namespace tree.
+    #[must_use]
+    pub fn tree(&self) -> NamespaceTreeCell {
+        self.tree.clone()
+    }
+
+    /// Insert a namespace into the tree. If the namespace already exists, return its ID.
+    /// Panics if the `ns` iterator is empty.
+    #[must_use]
+    pub fn insert_or_find_namespace(
+        &mut self,
+        ns: impl IntoIterator<Item = Rc<str>>,
+    ) -> NamespaceId {
+        self.tree
+            .borrow_mut()
+            .insert_or_find_namespace(ns.into_iter().peekable(), &mut self.assigner)
+            .expect("namespace creation should not fail")
+    }
+
+    /// Get the ID of a namespace given its name.
+    pub fn get_namespace_id<'a>(
+        &self,
+        ns: impl IntoIterator<Item = &'a str>,
+    ) -> Option<NamespaceId> {
+        self.tree.borrow().get_namespace_id(ns)
+    }
+
+    /// Given a [`NamespaceId`], find the namespace in the tree. Note that this function is not
+    /// particularly efficient, as it performs a breadth-first search. The results of this search
+    /// are memoized to avoid repeated lookups, reducing the impact of the BFS.
+    #[must_use]
+    pub fn find_namespace_by_id(&self, id: &NamespaceId) -> (Vec<Rc<str>>, NamespaceTreeCell) {
+        if let Some(res) = self.memo.borrow().get(id) {
+            return res.clone();
+        }
+        let (names, node) = self
+            .tree
+            .borrow()
+            .find_namespace_by_id(*id, &[])
+            .unwrap_or_else(|| (vec![], self.tree.clone()));
+
+        self.memo
+            .borrow_mut()
+            .insert(*id, (names.clone(), node.clone()));
+        (names, node.clone())
+    }
+
+    #[must_use]
+    pub fn root_id(&self) -> NamespaceId {
+        self.tree.borrow().id
+    }
+}
+
+impl Default for NamespaceTreeRoot {
+    fn default() -> Self {
+        let mut tree = Self {
+            assigner: 0,
+            tree: Rc::new(RefCell::new(NamespaceTreeNode {
+                children: FxHashMap::default(),
+                id: NamespaceId::new(0),
+            })),
+            memo: RefCell::new(FxHashMap::default()),
+        };
+        // insert the prelude namespaces using the `NamespaceTreeRoot` API
+        for ns in &PRELUDE {
+            let iter = ns.iter().map(|s| Rc::from(*s)).peekable();
+            let _ = tree.insert_or_find_namespace(iter);
+        }
+        tree
+    }
+}
+
+/// A node in the namespace tree. Each node has a unique ID and a map of children.
+/// Supports interior mutability of children for inserting new nodes.
+#[derive(Debug, Clone)]
+pub struct NamespaceTreeNode {
+    pub children: FxHashMap<Rc<str>, NamespaceTreeCell>,
+    pub id: NamespaceId,
+}
+impl NamespaceTreeNode {
+    /// Create a new namespace tree node with the given ID and children. The `id` should come from the `NamespaceTreeRoot` assigner.
+    #[must_use]
+    fn new(id: NamespaceId, children: FxHashMap<Rc<str>, NamespaceTreeCell>) -> Self {
+        Self { children, id }
+    }
+
+    /// Get a reference to the children of the namespace tree node.
+    #[must_use]
+    pub fn children(&self) -> &FxHashMap<Rc<str>, NamespaceTreeCell> {
+        &self.children
+    }
+
+    /// See [`FxHashMap::get`] for more information.
+    fn get(&self, component: &Rc<str>) -> Option<NamespaceTreeCell> {
+        self.children.get(component).cloned()
+    }
+
+    /// Get the ID of this namespace tree node.
+    #[must_use]
+    pub fn id(&self) -> NamespaceId {
+        self.id
+    }
+
+    /// Check if this namespace tree node contains a given namespace as a child.
+    #[must_use]
+    pub fn contains<'a>(&self, ns: impl IntoIterator<Item = &'a str>) -> bool {
+        self.get_namespace_id(ns).is_some()
+    }
+
+    /// Finds the ID of a namespace given its string name. This function is generally more efficient
+    /// than [`NamespaceTreeNode::find_namespace_by_id`], as it utilizes the prefix tree structure to
+    /// find the ID in `O(n)` time, where `n` is the number of components in the namespace name.
+    pub fn get_namespace_id<'a>(
+        &self,
+        ns: impl IntoIterator<Item = &'a str>,
+    ) -> Option<NamespaceId> {
+        let mut buf: Option<NamespaceTreeCell> = None;
+        for component in ns {
+            if let Some(next_ns) = match buf {
+                None => self.get(&Rc::from(component)),
+                Some(buf) => buf.borrow().get(&Rc::from(component)),
+            } {
+                buf = Some(next_ns);
+            } else {
+                return None;
+            }
+        }
+        Some(buf.map_or_else(|| self.id, |x| x.borrow().id))
+    }
+
+    /// Inserts a new namespace into the tree, if it does not yet exist.
+    /// Returns the ID of the namespace.
+    /// Returns `None` if an empty iterator is passed in.
+    pub fn insert_or_find_namespace<I>(
+        &mut self,
+        mut iter: Peekable<I>,
+        assigner: &mut usize,
+    ) -> Option<NamespaceId>
+    where
+        I: Iterator<Item = Rc<str>>,
+    {
+        let next_item = iter.next()?;
+        let next_node = self.children.get_mut(&next_item);
+        match (next_node, iter.peek()) {
+            (Some(next_node), Some(_)) => {
+                return next_node
+                    .borrow_mut()
+                    .insert_or_find_namespace(iter, assigner);
+            }
+            (Some(next_node), None) => {
+                return Some(next_node.borrow().id);
+            }
+            _ => {}
+        }
+        *assigner += 1;
+        let mut new_node =
+            NamespaceTreeNode::new(NamespaceId::new(*assigner), FxHashMap::default());
+        if iter.peek().is_none() {
+            let new_node_id = new_node.id;
+            self.children
+                .insert(next_item, Rc::new(RefCell::new(new_node)));
+            Some(new_node_id)
+        } else {
+            let id = new_node.insert_or_find_namespace(iter, assigner);
+            self.children
+                .insert(next_item, Rc::new(RefCell::new(new_node)));
+            id
+        }
+    }
+
+    fn find_namespace_by_id(
+        &self,
+        id: NamespaceId,
+        names_buf: &[Rc<str>],
+    ) -> Option<(Vec<Rc<str>>, NamespaceTreeCell)> {
+        // first, check if any children are the one we are looking for
+        for (name, node) in &self.children {
+            if node.borrow().id == id {
+                let mut names = names_buf.to_vec();
+                names.push(name.clone());
+                return Some((names, node.clone()));
+            }
+        }
+
+        // if it wasn't found, recurse into children
+        for (name, node) in &self.children {
+            let mut names = names_buf.to_vec();
+            names.push(name.clone());
+            let Some((names, node)) = node.borrow().find_namespace_by_id(id, &names) else {
+                continue;
+            };
+            return Some((names, node));
+        }
+
+        None
+    }
+}
diff --git a/compiler/qsc_doc_gen/src/generate_docs.rs b/compiler/qsc_doc_gen/src/generate_docs.rs
index 48a22ef3..fc39ced3 100644
--- a/compiler/qsc_doc_gen/src/generate_docs.rs
+++ b/compiler/qsc_doc_gen/src/generate_docs.rs
@@ -195,10 +195,10 @@ fn get_namespace(package: &Package, item: &Item) -> Option<Rc<str>> {
                 .expect("Could not resolve parent item id");
             match &parent.kind {
                 ItemKind::Namespace(name, _) => {
-                    if name.name.starts_with("QIR") {
+                    if name.starts_with("QIR") {
                         None // We ignore "QIR" namespaces
                     } else {
-                        Some(name.name.clone())
+                        Some(name.name())
                     }
                 }
                 _ => None,
diff --git a/compiler/qsc_fir/src/global.rs b/compiler/qsc_fir/src/global.rs
index 4591597c..30fc4b9b 100644
--- a/compiler/qsc_fir/src/global.rs
+++ b/compiler/qsc_fir/src/global.rs
@@ -40,7 +40,7 @@ pub struct Table {
 impl Table {
     #[must_use]
     pub fn resolve_ty(&self, namespace: &str, name: &str) -> Option<&Ty> {
-        self.tys.get(namespace).and_then(|terms| terms.get(name))
+        self.tys.get(namespace).and_then(|ty| ty.get(name))
     }
 
     #[must_use]
diff --git a/compiler/qsc_frontend/src/compile.rs b/compiler/qsc_frontend/src/compile.rs
index 86e816a4..8eb91adb 100644
--- a/compiler/qsc_frontend/src/compile.rs
+++ b/compiler/qsc_frontend/src/compile.rs
@@ -30,7 +30,7 @@ use qsc_data_structures::{
 };
 use qsc_hir::{
     assigner::Assigner as HirAssigner,
-    global,
+    global::{self},
     hir::{self, PackageId},
     validate::Validator as HirValidator,
     visit::Visitor as _,
@@ -475,7 +475,7 @@ fn resolve_all(
     let mut errors = globals.add_local_package(assigner, package);
     let mut resolver = Resolver::new(globals, dropped_names);
     resolver.with(assigner).visit_package(package);
-    let (names, locals, mut resolver_errors) = resolver.into_result();
+    let (names, locals, mut resolver_errors, _namespaces) = resolver.into_result();
     errors.append(&mut resolver_errors);
     (names, locals, errors)
 }
diff --git a/compiler/qsc_frontend/src/compile/preprocess.rs b/compiler/qsc_frontend/src/compile/preprocess.rs
index 081dadf8..f3c03567 100644
--- a/compiler/qsc_frontend/src/compile/preprocess.rs
+++ b/compiler/qsc_frontend/src/compile/preprocess.rs
@@ -54,12 +54,12 @@ impl MutVisitor for Conditional {
                         ItemKind::Callable(callable) => {
                             self.included_names.push(TrackedName {
                                 name: callable.name.name.clone(),
-                                namespace: namespace.name.name.clone(),
+                                namespace: namespace.name.name(),
                             });
                         }
                         ItemKind::Ty(ident, _) => self.included_names.push(TrackedName {
                             name: ident.name.clone(),
-                            namespace: namespace.name.name.clone(),
+                            namespace: namespace.name.name(),
                         }),
                         _ => {}
                     }
@@ -69,12 +69,12 @@ impl MutVisitor for Conditional {
                         ItemKind::Callable(callable) => {
                             self.dropped_names.push(TrackedName {
                                 name: callable.name.name.clone(),
-                                namespace: namespace.name.name.clone(),
+                                namespace: namespace.name.name(),
                             });
                         }
                         ItemKind::Ty(ident, _) => self.dropped_names.push(TrackedName {
                             name: ident.name.clone(),
-                            namespace: namespace.name.name.clone(),
+                            namespace: namespace.name.name(),
                         }),
                         _ => {}
                     }
diff --git a/compiler/qsc_frontend/src/lower.rs b/compiler/qsc_frontend/src/lower.rs
index a5ecfa45..a65a9312 100644
--- a/compiler/qsc_frontend/src/lower.rs
+++ b/compiler/qsc_frontend/src/lower.rs
@@ -124,7 +124,7 @@ impl With<'_> {
 
     pub(super) fn lower_namespace(&mut self, namespace: &ast::Namespace) {
         let Some(&resolve::Res::Item(hir::ItemId { item: id, .. }, _)) =
-            self.names.get(namespace.name.id)
+            self.names.get(namespace.id)
         else {
             panic!("namespace should have item ID");
         };
@@ -136,7 +136,7 @@ impl With<'_> {
             .filter_map(|i| self.lower_item(ItemScope::Global, i))
             .collect();
 
-        let name = self.lower_ident(&namespace.name);
+        let name = self.lower_vec_ident(&namespace.name);
         self.lowerer.items.push(hir::Item {
             id,
             span: namespace.span,
@@ -736,6 +736,10 @@ impl With<'_> {
             new_id
         })
     }
+
+    fn lower_vec_ident(&mut self, name: &ast::Idents) -> hir::Idents {
+        name.iter().map(|i| self.lower_ident(i)).collect()
+    }
 }
 
 fn lower_visibility(visibility: &ast::Visibility) -> hir::Visibility {
diff --git a/compiler/qsc_frontend/src/resolve.rs b/compiler/qsc_frontend/src/resolve.rs
index 15978857..07f110ef 100644
--- a/compiler/qsc_frontend/src/resolve.rs
+++ b/compiler/qsc_frontend/src/resolve.rs
@@ -6,10 +6,17 @@ mod tests;
 
 use miette::Diagnostic;
 use qsc_ast::{
-    ast::{self, CallableBody, CallableDecl, Ident, NodeId, SpecBody, SpecGen, TopLevelNode},
+    ast::{
+        self, CallableBody, CallableDecl, Ident, Idents, NodeId, SpecBody, SpecGen, TopLevelNode,
+    },
     visit::{self as ast_visit, walk_attr, Visitor as AstVisitor},
 };
-use qsc_data_structures::{index_map::IndexMap, span::Span};
+
+use qsc_data_structures::{
+    index_map::IndexMap,
+    namespaces::{NamespaceId, NamespaceTreeRoot, PRELUDE},
+    span::Span,
+};
 use qsc_hir::{
     assigner::Assigner,
     global,
@@ -17,18 +24,12 @@ use qsc_hir::{
     ty::{ParamId, Prim},
 };
 use rustc_hash::{FxHashMap, FxHashSet};
+use std::cmp::Ordering;
 use std::{collections::hash_map::Entry, rc::Rc, str::FromStr, vec};
 use thiserror::Error;
 
 use crate::compile::preprocess::TrackedName;
 
-const PRELUDE: &[&str] = &[
-    "Microsoft.Quantum.Canon",
-    "Microsoft.Quantum.Core",
-    "Microsoft.Quantum.Intrinsic",
-    "Microsoft.Quantum.Measurement",
-];
-
 // All AST Path nodes get mapped
 // All AST Ident nodes get mapped, except those under AST Path nodes
 pub(super) type Names = IndexMap<NodeId, Res>;
@@ -116,7 +117,7 @@ pub struct Scope {
     span: Span,
     kind: ScopeKind,
     /// Open statements. The key is the namespace name or alias.
-    opens: FxHashMap<Rc<str>, Vec<Open>>,
+    opens: FxHashMap<Vec<Rc<str>>, Vec<Open>>,
     /// Local newtype declarations.
     tys: FxHashMap<Rc<str>, ItemId>,
     /// Local callable and newtype declarations.
@@ -238,25 +239,35 @@ pub enum LocalKind {
 
 #[derive(Debug, Clone, Default)]
 pub struct GlobalScope {
-    tys: FxHashMap<Rc<str>, FxHashMap<Rc<str>, Res>>,
-    terms: FxHashMap<Rc<str>, FxHashMap<Rc<str>, Res>>,
-    namespaces: FxHashSet<Rc<str>>,
+    tys: IndexMap<NamespaceId, FxHashMap<Rc<str>, Res>>,
+    terms: IndexMap<NamespaceId, FxHashMap<Rc<str>, Res>>,
+    namespaces: NamespaceTreeRoot,
     intrinsics: FxHashSet<Rc<str>>,
 }
 
 impl GlobalScope {
-    fn get(&self, kind: NameKind, namespace: &str, name: &str) -> Option<&Res> {
-        let namespaces = match kind {
+    fn find_namespace<'a>(&self, ns: impl IntoIterator<Item = &'a str>) -> Option<NamespaceId> {
+        self.namespaces.get_namespace_id(ns)
+    }
+
+    fn get(&self, kind: NameKind, namespace: NamespaceId, name: &str) -> Option<&Res> {
+        let items = match kind {
             NameKind::Ty => &self.tys,
             NameKind::Term => &self.terms,
         };
-        namespaces.get(namespace).and_then(|items| items.get(name))
+        items.get(namespace).and_then(|items| items.get(name))
+    }
+
+    /// Creates a namespace in the namespace mapping. Note that namespaces are tracked separately from their
+    /// item contents. This returns a [`NamespaceId`] which you can use to add more tys and terms to the scope.
+    fn insert_or_find_namespace(&mut self, name: impl Into<Vec<Rc<str>>>) -> NamespaceId {
+        self.namespaces.insert_or_find_namespace(name.into())
     }
 }
 
 #[derive(Debug, Clone, Eq, PartialEq)]
 enum ScopeKind {
-    Namespace(Rc<str>),
+    Namespace(NamespaceId),
     Callable,
     Block,
 }
@@ -269,10 +280,32 @@ enum NameKind {
 
 #[derive(Debug, Clone)]
 struct Open {
-    namespace: Rc<str>,
+    namespace: NamespaceId,
     span: Span,
 }
 
+impl Eq for Open {}
+
+impl PartialEq<Self> for Open {
+    fn eq(&self, other: &Self) -> bool {
+        self.namespace == other.namespace
+    }
+}
+
+impl PartialOrd<Self> for Open {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
+impl Ord for Open {
+    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
+        let a: usize = self.namespace.into();
+        let b: usize = other.namespace.into();
+        a.cmp(&b)
+    }
+}
+
 pub(super) struct Resolver {
     names: Names,
     dropped_names: Vec<TrackedName>,
@@ -338,8 +371,13 @@ impl Resolver {
         }
     }
 
-    pub(super) fn into_result(self) -> (Names, Locals, Vec<Error>) {
-        (self.names, self.locals, self.errors)
+    pub(super) fn into_result(self) -> (Names, Locals, Vec<Error>, NamespaceTreeRoot) {
+        (
+            self.names,
+            self.locals,
+            self.errors,
+            self.globals.namespaces,
+        )
     }
 
     pub(super) fn extend_dropped_names(&mut self, dropped_names: Vec<TrackedName>) {
@@ -349,7 +387,7 @@ impl Resolver {
     pub(super) fn bind_fragments(&mut self, ast: &ast::Package, assigner: &mut Assigner) {
         for node in &mut ast.nodes.iter() {
             match node {
-                ast::TopLevelNode::Namespace(namespace) => {
+                TopLevelNode::Namespace(namespace) => {
                     bind_global_items(
                         &mut self.names,
                         &mut self.globals,
@@ -358,7 +396,7 @@ impl Resolver {
                         &mut self.errors,
                     );
                 }
-                ast::TopLevelNode::Stmt(stmt) => {
+                TopLevelNode::Stmt(stmt) => {
                     if let ast::StmtKind::Item(item) = stmt.kind.as_ref() {
                         self.bind_local_item(assigner, item);
                     }
@@ -374,14 +412,12 @@ impl Resolver {
     }
 
     fn resolve_ident(&mut self, kind: NameKind, name: &Ident) {
-        let namespace = None;
-
         match resolve(
             kind,
             &self.globals,
             self.locals.get_scopes(&self.curr_scope_chain),
             name,
-            &namespace,
+            &None,
         ) {
             Ok(res) => {
                 self.check_item_status(res, name.name.to_string(), name.span);
@@ -463,26 +499,50 @@ impl Resolver {
         }
     }
 
-    fn bind_open(&mut self, name: &ast::Ident, alias: &Option<Box<ast::Ident>>) {
-        let alias = alias.as_ref().map_or("".into(), |a| Rc::clone(&a.name));
-        if self.globals.namespaces.contains(&name.name) {
-            self.current_scope_mut()
-                .opens
-                .entry(alias)
-                .or_default()
-                .push(Open {
-                    namespace: Rc::clone(&name.name),
-                    span: name.span,
-                });
+    fn bind_open(
+        &mut self,
+        name: &Idents,
+        alias: &Option<Box<Ident>>,
+        current_namespace: NamespaceId,
+    ) {
+        let (_current_ns_name, current_namespace) = self
+            .globals
+            .namespaces
+            .find_namespace_by_id(&current_namespace);
+        // try scoping from the current namespace, and then use the absolute namespace as the backup
+
+        let id = if let Some(id) = (*current_namespace)
+            .borrow()
+            .get_namespace_id(name.str_iter())
+        {
+            id
+        } else if let Some(id) = self.globals.namespaces.get_namespace_id(name.str_iter()) {
+            id
         } else {
-            self.errors
-                .push(Error::NotFound(name.name.to_string(), name.span));
-        }
+            return self
+                .errors
+                .push(Error::NotFound(name.name().to_string(), name.span()));
+        };
+
+        let alias = alias
+            .as_ref()
+            .map_or(name.into(), |a| vec![Rc::clone(&a.name)]);
+
+        self.current_scope_mut()
+            .opens
+            .entry(alias)
+            .or_default()
+            .push(Open {
+                namespace: id,
+                span: name.span(),
+            });
     }
 
     pub(super) fn bind_local_item(&mut self, assigner: &mut Assigner, item: &ast::Item) {
         match &*item.kind {
-            ast::ItemKind::Open(name, alias) => self.bind_open(name, alias),
+            ast::ItemKind::Open(name, alias) => {
+                self.bind_open(name, alias, self.globals.namespaces.root_id());
+            }
             ast::ItemKind::Callable(decl) => {
                 let id = intrapackage(assigner.next_item());
                 self.names.insert(
@@ -593,14 +653,25 @@ impl With<'_> {
 
 impl AstVisitor<'_> for With<'_> {
     fn visit_namespace(&mut self, namespace: &ast::Namespace) {
-        let kind = ScopeKind::Namespace(Rc::clone(&namespace.name.name));
+        let ns = self
+            .resolver
+            .globals
+            .find_namespace(namespace.name.str_iter())
+            .expect("namespace should exist by this point");
+
+        let root_id = self.resolver.globals.namespaces.root_id();
+
+        let kind = ScopeKind::Namespace(ns);
         self.with_scope(namespace.span, kind, |visitor| {
+            // the below line ensures that this namespace opens itself, in case
+            // we are re-opening a namespace. This is important, as without this,
+            // a re-opened namespace would only have knowledge of its scopes.
+            visitor.resolver.bind_open(&namespace.name, &None, root_id);
             for item in &*namespace.items {
                 if let ast::ItemKind::Open(name, alias) = &*item.kind {
-                    visitor.resolver.bind_open(name, alias);
+                    visitor.resolver.bind_open(name, alias, ns);
                 }
             }
-
             ast_visit::walk_namespace(visitor, namespace);
         });
     }
@@ -612,7 +683,7 @@ impl AstVisitor<'_> for With<'_> {
         }
     }
 
-    fn visit_callable_decl(&mut self, decl: &ast::CallableDecl) {
+    fn visit_callable_decl(&mut self, decl: &CallableDecl) {
         fn collect_param_names(pat: &ast::Pat, names: &mut FxHashSet<Rc<str>>) {
             match &*pat.kind {
                 ast::PatKind::Bind(name, _) => {
@@ -639,7 +710,7 @@ impl AstVisitor<'_> for With<'_> {
     }
 
     fn visit_spec_decl(&mut self, decl: &ast::SpecDecl) {
-        if let ast::SpecBody::Impl(input, block) = &decl.body {
+        if let SpecBody::Impl(input, block) = &decl.body {
             self.with_spec_pat(block.span, ScopeKind::Block, input, |visitor| {
                 visitor.visit_block(block);
             });
@@ -756,15 +827,23 @@ impl GlobalTable {
         for (name, res) in builtins {
             core.insert(name, res);
         }
-        let mut tys: FxHashMap<Rc<str>, FxHashMap<Rc<str>, Res>> = FxHashMap::default();
-        tys.insert("Microsoft.Quantum.Core".into(), core);
+
+        let mut scope = GlobalScope::default();
+        let ns = scope.insert_or_find_namespace(vec![
+            Rc::from("Microsoft"),
+            Rc::from("Quantum"),
+            Rc::from("Core"),
+        ]);
+
+        let mut tys = IndexMap::default();
+        tys.insert(ns, core);
 
         Self {
             names: IndexMap::new(),
             scope: GlobalScope {
                 tys,
-                terms: FxHashMap::default(),
-                namespaces: FxHashSet::default(),
+                terms: IndexMap::default(),
+                namespaces: NamespaceTreeRoot::default(),
                 intrinsics: FxHashSet::default(),
             },
         }
@@ -800,20 +879,22 @@ impl GlobalTable {
             global.visibility == hir::Visibility::Public
                 || matches!(&global.kind, global::Kind::Term(t) if t.intrinsic)
         }) {
+            let namespace = self
+                .scope
+                .insert_or_find_namespace(global.namespace.clone());
+
             match (global.kind, global.visibility) {
                 (global::Kind::Ty(ty), hir::Visibility::Public) => {
                     self.scope
                         .tys
-                        .entry(global.namespace)
-                        .or_default()
+                        .get_mut_or_default(namespace)
                         .insert(global.name, Res::Item(ty.id, global.status));
                 }
                 (global::Kind::Term(term), visibility) => {
                     if visibility == hir::Visibility::Public {
                         self.scope
                             .terms
-                            .entry(global.namespace)
-                            .or_default()
+                            .get_mut_or_default(namespace)
                             .insert(global.name.clone(), Res::Item(term.id, global.status));
                     }
                     if term.intrinsic {
@@ -821,7 +902,7 @@ impl GlobalTable {
                     }
                 }
                 (global::Kind::Namespace, hir::Visibility::Public) => {
-                    self.scope.namespaces.insert(global.name);
+                    self.scope.insert_or_find_namespace(global.namespace);
                 }
                 (_, hir::Visibility::Internal) => {}
             }
@@ -829,6 +910,7 @@ impl GlobalTable {
     }
 }
 
+/// Given some namespace `namespace`, add all the globals declared within it to the global scope.
 fn bind_global_items(
     names: &mut IndexMap<NodeId, Res>,
     scope: &mut GlobalScope,
@@ -837,16 +919,17 @@ fn bind_global_items(
     errors: &mut Vec<Error>,
 ) {
     names.insert(
-        namespace.name.id,
+        namespace.id,
         Res::Item(intrapackage(assigner.next_item()), ItemStatus::Available),
     );
-    scope.namespaces.insert(Rc::clone(&namespace.name.name));
+
+    let namespace_id = scope.insert_or_find_namespace(&namespace.name);
 
     for item in &*namespace.items {
         match bind_global_item(
             names,
             scope,
-            &namespace.name.name,
+            namespace_id,
             || intrapackage(assigner.next_item()),
             item,
         ) {
@@ -901,7 +984,7 @@ fn ast_attrs_as_hir_attrs(attrs: &[Box<ast::Attr>]) -> Vec<hir::Attr> {
 fn bind_global_item(
     names: &mut Names,
     scope: &mut GlobalScope,
-    namespace: &Rc<str>,
+    namespace: NamespaceId,
     next_id: impl FnOnce() -> ItemId,
     item: &ast::Item,
 ) -> Result<(), Vec<Error>> {
@@ -914,15 +997,21 @@ fn bind_global_item(
             let mut errors = Vec::new();
             match scope
                 .terms
-                .entry(Rc::clone(namespace))
-                .or_default()
+                .get_mut_or_default(namespace)
                 .entry(Rc::clone(&decl.name.name))
             {
-                Entry::Occupied(_) => errors.push(Error::Duplicate(
-                    decl.name.name.to_string(),
-                    namespace.to_string(),
-                    decl.name.span,
-                )),
+                Entry::Occupied(_) => {
+                    let namespace_name = scope
+                        .namespaces
+                        .find_namespace_by_id(&namespace)
+                        .0
+                        .join(".");
+                    errors.push(Error::Duplicate(
+                        decl.name.name.to_string(),
+                        namespace_name.to_string(),
+                        decl.name.span,
+                    ));
+                }
                 Entry::Vacant(entry) => {
                     entry.insert(res);
                 }
@@ -949,20 +1038,25 @@ fn bind_global_item(
             match (
                 scope
                     .terms
-                    .entry(Rc::clone(namespace))
-                    .or_default()
+                    .get_mut_or_default(namespace)
                     .entry(Rc::clone(&name.name)),
                 scope
                     .tys
-                    .entry(Rc::clone(namespace))
-                    .or_default()
+                    .get_mut_or_default(namespace)
                     .entry(Rc::clone(&name.name)),
             ) {
-                (Entry::Occupied(_), _) | (_, Entry::Occupied(_)) => Err(vec![Error::Duplicate(
-                    name.name.to_string(),
-                    namespace.to_string(),
-                    name.span,
-                )]),
+                (Entry::Occupied(_), _) | (_, Entry::Occupied(_)) => {
+                    let namespace_name = scope
+                        .namespaces
+                        .find_namespace_by_id(&namespace)
+                        .0
+                        .join(".");
+                    Err(vec![Error::Duplicate(
+                        name.name.to_string(),
+                        namespace_name,
+                        name.span,
+                    )])
+                }
                 (Entry::Vacant(term_entry), Entry::Vacant(ty_entry)) => {
                     term_entry.insert(res);
                     ty_entry.insert(res);
@@ -974,7 +1068,7 @@ fn bind_global_item(
     }
 }
 
-fn decl_is_intrinsic(decl: &ast::CallableDecl) -> bool {
+fn decl_is_intrinsic(decl: &CallableDecl) -> bool {
     if let CallableBody::Specs(specs) = decl.body.as_ref() {
         specs
             .iter()
@@ -984,49 +1078,57 @@ fn decl_is_intrinsic(decl: &ast::CallableDecl) -> bool {
     }
 }
 
+/// Resolves a given symbol and namespace name, according to the Q# shadowing rules.
+/// Shadowing rules are as follows:
+/// - Local variables shadow everything. They are the first priority.
+/// - Next, we check open statements for a non-prelude open.
+/// - Then, we check the prelude.
+/// - Lastly, we check the global namespace.
+/// In the example `Foo.Bar.Baz()` -- the `provided_namespace_name` would be
+///`Foo.Bar` and the `provided_symbol_name` would be `Baz`.
+///
+/// In the example `Foo()` -- the `provided_namespace_name` would be `None` and the
+/// `provided_symbol_name` would be `Foo`.
+/// returns the resolution if successful, or an error if not.
 fn resolve<'a>(
     kind: NameKind,
     globals: &GlobalScope,
     scopes: impl Iterator<Item = &'a Scope>,
-    name: &Ident,
-    namespace: &Option<Box<Ident>>,
+    provided_symbol_name: &Ident,
+    provided_namespace_name: &Option<Idents>,
 ) -> Result<Res, Error> {
-    let scopes = scopes.collect::<Vec<_>>();
-    let mut candidates = FxHashMap::default();
-    let mut vars = true;
-    let name_str = &(*name.name);
-    let namespace = namespace.as_ref().map_or("", |i| &i.name);
-    for scope in scopes {
-        if namespace.is_empty() {
-            if let Some(res) = resolve_scope_locals(kind, globals, scope, vars, name_str) {
-                // Local declarations shadow everything.
-                return Ok(res);
-            }
-        }
-
-        if let Some(namespaces) = scope.opens.get(namespace) {
-            candidates = resolve_explicit_opens(kind, globals, namespaces, name_str);
-            if !candidates.is_empty() {
-                // Explicit opens shadow prelude and unopened globals.
-                break;
-            }
-        }
-
-        if scope.kind == ScopeKind::Callable {
-            // Since local callables are not closures, hide local variables in parent scopes.
-            vars = false;
-        }
+    if let Some(value) = check_all_scopes(
+        kind,
+        globals,
+        provided_symbol_name,
+        provided_namespace_name,
+        scopes,
+    ) {
+        return value;
     }
 
-    if candidates.is_empty() && namespace.is_empty() {
-        // Prelude shadows unopened globals.
-        let candidates = resolve_implicit_opens(kind, globals, PRELUDE, name_str);
-        if candidates.len() > 1 {
-            let mut candidates: Vec<_> = candidates.into_iter().collect();
-            candidates.sort_by_key(|x| x.1);
+    // check the prelude
+    if provided_namespace_name.is_none() {
+        let prelude_candidates = find_symbol_in_namespaces(
+            kind,
+            globals,
+            provided_namespace_name,
+            provided_symbol_name,
+            prelude_namespaces(globals).into_iter().map(|(a, b)| (b, a)),
+            // there are no aliases in the prelude
+            &FxHashMap::default(),
+        );
+
+        if prelude_candidates.len() > 1 {
+            // If there are multiple candidates, sort them by namespace and return an error.
+            let candidates: Vec<_> = prelude_candidates.into_iter().collect();
             let mut candidates = candidates
                 .into_iter()
-                .map(|candidate| candidate.1.to_string());
+                .map(|(_candidate, ns_name)| ns_name)
+                .collect::<Vec<_>>();
+            candidates.sort();
+
+            let mut candidates = candidates.into_iter();
             let candidate_a = candidates
                 .next()
                 .expect("infallible as per length check above");
@@ -1034,56 +1136,262 @@ fn resolve<'a>(
                 .next()
                 .expect("infallible as per length check above");
             return Err(Error::AmbiguousPrelude {
-                span: name.span,
-                name: name.name.to_string(),
+                span: provided_symbol_name.span,
+                name: provided_symbol_name.name.to_string(),
                 candidate_a,
                 candidate_b,
             });
         }
-        if let Some((res, _)) = single(candidates) {
+        // if there is a candidate, return it
+        if let Some((res, _)) = single(prelude_candidates) {
             return Ok(res);
         }
     }
 
-    if candidates.is_empty() {
-        if let Some(&res) = globals.get(kind, namespace, name_str) {
-            // An unopened global is the last resort.
-            return Ok(res);
+    // lastly, check unopened globals
+    let global_candidates = find_symbol_in_namespaces(
+        kind,
+        globals,
+        provided_namespace_name,
+        provided_symbol_name,
+        std::iter::once((globals.namespaces.root_id(), ())),
+        // there are no aliases in globals
+        &FxHashMap::default(),
+    );
+
+    // we don't have to throw an error if there are extra candidates here, as we are only looking at the root,
+    // and that's only one namespace. individual namespaces cannot have duplicate declarations.
+    if let Some(res) = single(global_candidates.into_keys()) {
+        return Ok(res);
+    }
+
+    Err(Error::NotFound(
+        provided_symbol_name.name.to_string(),
+        provided_symbol_name.span,
+    ))
+}
+/// Checks all given scopes, in the correct order, for a resolution.
+/// Calls `check_scoped_resolutions` on each scope, and tracks if we should allow local variables in closures in parent scopes
+/// using the `vars` parameter.
+fn check_all_scopes<'a>(
+    kind: NameKind,
+    globals: &GlobalScope,
+    provided_symbol_name: &Ident,
+    provided_namespace_name: &Option<Idents>,
+    scopes: impl Iterator<Item = &'a Scope>,
+) -> Option<Result<Res, Error>> {
+    let mut vars = true;
+
+    for scope in scopes {
+        if let Some(value) = check_scoped_resolutions(
+            kind,
+            globals,
+            provided_symbol_name,
+            provided_namespace_name,
+            &mut vars,
+            scope,
+        ) {
+            return Some(value);
         }
     }
+    None
+}
 
-    if candidates.len() > 1 {
-        // If there are multiple candidates, remove unimplemented items. This allows resolution to
-        // succeed in cases where both an older, unimplemented API and newer, implemented API with the
-        // same name are both in scope without forcing the user to fully qualify the name.
-        let mut removals = Vec::new();
-        for res in candidates.keys() {
-            if let Res::Item(_, ItemStatus::Unimplemented) = res {
-                removals.push(*res);
+/// This function checks scopes for a given symbol and namespace name.
+/// In a given [Scope], check:
+/// 1. if any locally declared symbols match `provided_symbol_name`
+/// 2. if any aliases in this scope match the provided namespace, and if they contain `provided_symbol_name`
+/// 3. if any opens in this scope contain the `provided_symbol_name`
+/// It follows the Q# shadowing rules:
+/// - Local variables shadow everything. They are the first priority.
+/// - Next, we check open statements for an explicit open.
+/// - Then, we check the prelude.
+/// - Lastly, we check the global namespace.
+///
+/// # Parameters
+///
+/// * `kind` - The [`NameKind`] of the name
+/// * `globals` - The global scope to resolve the name against.
+/// * `provided_symbol_name` - The symbol name to resolve.
+/// * `provided_namespace_name` - The namespace of the symbol, if any.
+/// * `vars` - A mutable reference to a boolean indicating whether to allow local variables in closures in parent scopes.
+/// * `scope` - The scope to check for resolutions.
+fn check_scoped_resolutions(
+    kind: NameKind,
+    globals: &GlobalScope,
+    provided_symbol_name: &Ident,
+    provided_namespace_name: &Option<Idents>,
+    vars: &mut bool,
+    scope: &Scope,
+) -> Option<Result<Res, Error>> {
+    if provided_namespace_name.is_none() {
+        if let Some(res) =
+            resolve_scope_locals(kind, globals, scope, *vars, &provided_symbol_name.name)
+        {
+            // Local declarations shadow everything.
+            return Some(Ok(res));
+        }
+    }
+    let aliases = scope
+        .opens
+        .iter()
+        .map(|(alias, opens)| {
+            (
+                alias.clone(),
+                opens.iter().map(|x| (x.namespace, x)).collect(),
+            )
+        })
+        .collect::<FxHashMap<_, _>>();
+
+    let explicit_open_candidates = find_symbol_in_namespaces(
+        kind,
+        globals,
+        provided_namespace_name,
+        provided_symbol_name,
+        scope
+            .opens
+            .iter()
+            .flat_map(|(_, open)| open)
+            .map(|open @ Open { namespace, .. }| (*namespace, open)),
+        &aliases,
+    );
+    match explicit_open_candidates.len() {
+        1 => {
+            return Some(Ok(single(explicit_open_candidates.into_keys())
+                .expect("we asserted on the length, so this is infallible")))
+        }
+        len if len > 1 => {
+            return Some(Err(ambiguous_symbol_error(
+                globals,
+                provided_symbol_name,
+                explicit_open_candidates
+                    .into_iter()
+                    .map(|(a, b)| (a, b.clone()))
+                    .collect(),
+            )))
+        }
+        _ => (),
+    }
+    if scope.kind == ScopeKind::Callable {
+        // Since local callables are not closures, hide local variables in parent scopes.
+        *vars = false;
+    }
+    None
+}
+
+/// This function returns type `Error::Ambiguous` and contains
+/// the name of the ambiguous symbol and the namespaces that contain the conflicting entities.
+/// # Arguments
+///
+/// * `globals` - The global scope to resolve the name against.
+/// * `provided_symbol_name` - The symbol name that is ambiguous.
+/// * `candidates` - A map of possible resolutions for the symbol, each associated with the `Open`
+/// statement that brought it into scope. Note that only the first two opens in
+/// the candidates are actually used in the error message.
+fn ambiguous_symbol_error(
+    globals: &GlobalScope,
+    provided_symbol_name: &Ident,
+    candidates: FxHashMap<Res, Open>,
+) -> Error {
+    let mut opens: Vec<_> = candidates.into_values().collect();
+    opens.sort_unstable_by_key(|open| open.span);
+    let (first_open_ns, _) = globals.namespaces.find_namespace_by_id(&opens[0].namespace);
+    let (second_open_ns, _) = globals.namespaces.find_namespace_by_id(&opens[1].namespace);
+    Error::Ambiguous {
+        name: provided_symbol_name.name.to_string(),
+        first_open: first_open_ns.join("."),
+        second_open: second_open_ns.join("."),
+        name_span: provided_symbol_name.span,
+        first_open_span: opens[0].span,
+        second_open_span: opens[1].span,
+    }
+}
+
+fn find_symbol_in_namespaces<T, O>(
+    kind: NameKind,
+    globals: &GlobalScope,
+    provided_namespace_name: &Option<Idents>,
+    provided_symbol_name: &Ident,
+    namespaces_to_search: T,
+    aliases: &FxHashMap<Vec<Rc<str>>, Vec<(NamespaceId, O)>>,
+) -> FxHashMap<Res, O>
+where
+    T: Iterator<Item = (NamespaceId, O)>,
+    O: Clone + std::fmt::Debug,
+{
+    // check aliases to see if the provided namespace is actually an alias
+    if let Some(provided_namespace_name) = provided_namespace_name {
+        if let Some(opens) = aliases.get(&(Into::<Vec<Rc<_>>>::into(provided_namespace_name))) {
+            let candidates: FxHashMap<_, _> = opens
+                .iter()
+                .filter_map(|(ns_id, open)| {
+                    globals
+                        .get(kind, *ns_id, &provided_symbol_name.name)
+                        .map(|res| (*res, open.clone()))
+                })
+                .collect();
+            if !candidates.is_empty() {
+                return candidates;
             }
         }
-        for res in removals {
-            candidates.remove(&res);
+    }
+
+    let mut candidates = FxHashMap::default();
+    for (candidate_namespace_id, open) in namespaces_to_search {
+        // Retrieve the namespace associated with the candidate_namespace_id from the global namespaces
+        let candidate_namespace = globals
+            .namespaces
+            .find_namespace_by_id(&candidate_namespace_id)
+            .1;
+
+        // Attempt to find a namespace within the candidate_namespace that matches the provided_namespace_name
+        let namespace = provided_namespace_name.as_ref().and_then(|name| {
+            candidate_namespace
+                .borrow()
+                .get_namespace_id(name.str_iter())
+        });
+
+        // if a namespace was provided, but not found, then this is not the correct namespace.
+        if provided_namespace_name.is_some() && namespace.is_none() {
+            continue;
+        }
+
+        // Attempt to get the symbol from the global scope. If the namespace is None, use the candidate_namespace_id as a fallback
+        let res = namespace
+            .or(Some(candidate_namespace_id))
+            .and_then(|ns_id| globals.get(kind, ns_id, &provided_symbol_name.name));
+
+        // If a symbol was found, insert it into the candidates map
+        if let Some(res) = res {
+            candidates.insert(*res, open);
         }
     }
 
     if candidates.len() > 1 {
-        let mut opens: Vec<_> = candidates.into_values().collect();
-        opens.sort_unstable_by_key(|open| open.span);
-        Err(Error::Ambiguous {
-            name: name_str.to_string(),
-            first_open: opens[0].namespace.to_string(),
-            second_open: opens[1].namespace.to_string(),
-            name_span: name.span,
-            first_open_span: opens[0].span,
-            second_open_span: opens[1].span,
-        })
-    } else {
-        single(candidates.into_keys())
-            .ok_or_else(|| Error::NotFound(name_str.to_string(), name.span))
+        // If there are multiple candidates, remove unimplemented items. This allows resolution to
+        // succeed in cases where both an older, unimplemented API and newer, implemented API with the
+        // same name are both in scope without forcing the user to fully qualify the name.
+        candidates.retain(|&res, _| !matches!(res, Res::Item(_, ItemStatus::Unimplemented)));
     }
+    candidates
 }
 
+/// Fetch the name and namespace ID of all prelude namespaces.
+fn prelude_namespaces(globals: &GlobalScope) -> Vec<(String, NamespaceId)> {
+    let mut prelude = Vec::with_capacity(PRELUDE.len());
+
+    // add prelude to the list of candidate namespaces last, as they are the final fallback for a symbol
+    for prelude_namespace in PRELUDE {
+        prelude.push((
+            prelude_namespace.join("."),
+            globals
+                .namespaces
+                .get_namespace_id(prelude_namespace)
+                .expect("prelude should always exist in the namespace map"),
+        ));
+    }
+    prelude
+}
 /// Implements shadowing rules within a single scope.
 /// A local variable always wins out against an item with the same name, even if they're declared in
 /// the same scope. It is implemented in a way that resembles Rust:
@@ -1119,7 +1427,7 @@ fn resolve_scope_locals(
     }
 
     if let ScopeKind::Namespace(namespace) = &scope.kind {
-        if let Some(&res) = globals.get(kind, namespace, name) {
+        if let Some(&res) = globals.get(kind, *namespace, name) {
             return Some(res);
         }
     }
@@ -1162,39 +1470,7 @@ fn get_scope_locals(scope: &Scope, offset: u32, vars: bool) -> Vec<Local> {
     names
 }
 
-/// The return type represents the resolution of implicit opens, but also
-/// retains the namespace that the resolution comes from.
-/// This retained namespace string is used for error reporting.
-fn resolve_implicit_opens<'a, 'b>(
-    kind: NameKind,
-    globals: &'b GlobalScope,
-    namespaces: impl IntoIterator<Item = &'a &'a str>,
-    name: &'b str,
-) -> FxHashMap<Res, &'a str> {
-    let mut candidates = FxHashMap::default();
-    for namespace in namespaces {
-        if let Some(&res) = globals.get(kind, namespace, name) {
-            candidates.insert(res, *namespace);
-        }
-    }
-    candidates
-}
-
-fn resolve_explicit_opens<'a>(
-    kind: NameKind,
-    globals: &GlobalScope,
-    opens: impl IntoIterator<Item = &'a Open>,
-    name: &str,
-) -> FxHashMap<Res, &'a Open> {
-    let mut candidates = FxHashMap::default();
-    for open in opens {
-        if let Some(&res) = globals.get(kind, &open.namespace, name) {
-            candidates.insert(res, open);
-        }
-    }
-    candidates
-}
-
+/// Creates an [`ItemId`] for an item that is local to this package (internal to it).
 fn intrapackage(item: LocalItemId) -> ItemId {
     ItemId {
         package: None,
diff --git a/compiler/qsc_hir/src/global.rs b/compiler/qsc_hir/src/global.rs
index 2d51e9a6..cc9f230d 100644
--- a/compiler/qsc_hir/src/global.rs
+++ b/compiler/qsc_hir/src/global.rs
@@ -5,12 +5,16 @@ use crate::{
     hir::{Item, ItemId, ItemKind, ItemStatus, Package, PackageId, SpecBody, SpecGen, Visibility},
     ty::Scheme,
 };
-use qsc_data_structures::index_map;
+use qsc_data_structures::{
+    index_map,
+    namespaces::{NamespaceId, NamespaceTreeRoot},
+};
 use rustc_hash::FxHashMap;
 use std::rc::Rc;
 
+#[derive(Debug)]
 pub struct Global {
-    pub namespace: Rc<str>,
+    pub namespace: Vec<Rc<str>>,
     pub name: Rc<str>,
     pub visibility: Visibility,
     pub status: ItemStatus,
@@ -23,6 +27,16 @@ pub enum Kind {
     Term(Term),
 }
 
+impl std::fmt::Debug for Kind {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match self {
+            Kind::Namespace => write!(f, "Namespace"),
+            Kind::Ty(ty) => write!(f, "Ty({})", ty.id),
+            Kind::Term(term) => write!(f, "Term({})", term.id),
+        }
+    }
+}
+
 pub struct Ty {
     pub id: ItemId,
 }
@@ -33,21 +47,31 @@ pub struct Term {
     pub intrinsic: bool,
 }
 
+/// A lookup table used for looking up global core items for insertion in `qsc_passes`.
 #[derive(Default)]
 pub struct Table {
-    tys: FxHashMap<Rc<str>, FxHashMap<Rc<str>, Ty>>,
-    terms: FxHashMap<Rc<str>, FxHashMap<Rc<str>, Term>>,
+    tys: FxHashMap<NamespaceId, FxHashMap<Rc<str>, Ty>>,
+    terms: FxHashMap<NamespaceId, FxHashMap<Rc<str>, Term>>,
+    namespaces: NamespaceTreeRoot,
 }
 
 impl Table {
     #[must_use]
-    pub fn resolve_ty(&self, namespace: &str, name: &str) -> Option<&Ty> {
-        self.tys.get(namespace).and_then(|terms| terms.get(name))
+    pub fn resolve_ty(&self, namespace: NamespaceId, name: &str) -> Option<&Ty> {
+        self.tys.get(&namespace).and_then(|terms| terms.get(name))
     }
 
     #[must_use]
-    pub fn resolve_term(&self, namespace: &str, name: &str) -> Option<&Term> {
-        self.terms.get(namespace).and_then(|terms| terms.get(name))
+    pub fn resolve_term(&self, namespace: NamespaceId, name: &str) -> Option<&Term> {
+        self.terms.get(&namespace).and_then(|terms| terms.get(name))
+    }
+
+    pub fn find_namespace<'a>(
+        &self,
+        query: impl IntoIterator<Item = &'a str>,
+    ) -> Option<NamespaceId> {
+        // find a namespace if it exists and return its id
+        self.namespaces.get_namespace_id(query)
     }
 }
 
@@ -55,16 +79,16 @@ impl FromIterator<Global> for Table {
     fn from_iter<T: IntoIterator<Item = Global>>(iter: T) -> Self {
         let mut tys: FxHashMap<_, FxHashMap<_, _>> = FxHashMap::default();
         let mut terms: FxHashMap<_, FxHashMap<_, _>> = FxHashMap::default();
+        let mut namespaces = NamespaceTreeRoot::default();
         for global in iter {
+            let namespace = namespaces.insert_or_find_namespace(global.namespace.into_iter());
             match global.kind {
                 Kind::Ty(ty) => {
-                    tys.entry(global.namespace)
-                        .or_default()
-                        .insert(global.name, ty);
+                    tys.entry(namespace).or_default().insert(global.name, ty);
                 }
                 Kind::Term(term) => {
                     terms
-                        .entry(global.namespace)
+                        .entry(namespace)
                         .or_default()
                         .insert(global.name, term);
                 }
@@ -72,7 +96,11 @@ impl FromIterator<Global> for Table {
             }
         }
 
-        Self { tys, terms }
+        Self {
+            tys,
+            terms,
+            namespaces,
+        }
     }
 }
 
@@ -101,7 +129,7 @@ impl PackageIter<'_> {
 
         match (&item.kind, &parent) {
             (ItemKind::Callable(decl), Some(ItemKind::Namespace(namespace, _))) => Some(Global {
-                namespace: Rc::clone(&namespace.name),
+                namespace: namespace.into(),
                 name: Rc::clone(&decl.name.name),
                 visibility: item.visibility,
                 status,
@@ -113,7 +141,7 @@ impl PackageIter<'_> {
             }),
             (ItemKind::Ty(name, def), Some(ItemKind::Namespace(namespace, _))) => {
                 self.next = Some(Global {
-                    namespace: Rc::clone(&namespace.name),
+                    namespace: namespace.into(),
                     name: Rc::clone(&name.name),
                     visibility: item.visibility,
                     status,
@@ -125,7 +153,7 @@ impl PackageIter<'_> {
                 });
 
                 Some(Global {
-                    namespace: Rc::clone(&namespace.name),
+                    namespace: namespace.into(),
                     name: Rc::clone(&name.name),
                     visibility: item.visibility,
                     status,
@@ -133,8 +161,8 @@ impl PackageIter<'_> {
                 })
             }
             (ItemKind::Namespace(ident, _), None) => Some(Global {
-                namespace: "".into(),
-                name: Rc::clone(&ident.name),
+                namespace: ident.into(),
+                name: "".into(),
                 visibility: Visibility::Public,
                 status,
                 kind: Kind::Namespace,
diff --git a/compiler/qsc_hir/src/hir.rs b/compiler/qsc_hir/src/hir.rs
index 10422ec1..7d31aea1 100644
--- a/compiler/qsc_hir/src/hir.rs
+++ b/compiler/qsc_hir/src/hir.rs
@@ -4,7 +4,6 @@
 //! The high-level intermediate representation for Q#. HIR is lowered from the AST.
 
 #![warn(missing_docs)]
-
 use crate::ty::{Arrow, FunctorSet, FunctorSetValue, GenericArg, GenericParam, Scheme, Ty, Udt};
 use indenter::{indented, Indented};
 use num_bigint::BigInt;
@@ -333,7 +332,7 @@ pub enum ItemKind {
     /// A `function` or `operation` declaration.
     Callable(CallableDecl),
     /// A `namespace` declaration.
-    Namespace(Ident, Vec<LocalItemId>),
+    Namespace(Idents, Vec<LocalItemId>),
     /// A `newtype` declaration.
     Ty(Ident, Udt),
 }
@@ -1135,6 +1134,116 @@ impl Display for QubitInitKind {
     }
 }
 
+/// A [`Idents`] represents a sequence of idents. It provides a helpful abstraction
+/// that is more powerful than a simple `Vec<Ident>`, and is primarily used to represent
+/// dot-separated paths.
+#[derive(Clone, Debug, Eq, Hash, PartialEq, Default)]
+pub struct Idents(pub Box<[Ident]>);
+
+impl<'a> IntoIterator for &'a Idents {
+    type IntoIter = std::slice::Iter<'a, Ident>;
+    type Item = &'a Ident;
+    fn into_iter(self) -> Self::IntoIter {
+        self.iter()
+    }
+}
+impl From<Idents> for Vec<Rc<str>> {
+    fn from(v: Idents) -> Self {
+        v.0.iter().map(|i| i.name.clone()).collect()
+    }
+}
+
+impl From<&Idents> for Vec<Rc<str>> {
+    fn from(v: &Idents) -> Self {
+        v.0.iter().map(|i| i.name.clone()).collect()
+    }
+}
+
+impl From<Vec<Ident>> for Idents {
+    fn from(v: Vec<Ident>) -> Self {
+        Idents(v.into_boxed_slice())
+    }
+}
+
+impl From<Idents> for Vec<Ident> {
+    fn from(v: Idents) -> Self {
+        v.0.into_vec()
+    }
+}
+
+impl FromIterator<Ident> for Idents {
+    fn from_iter<T: IntoIterator<Item = Ident>>(iter: T) -> Self {
+        Idents(iter.into_iter().collect())
+    }
+}
+
+impl Display for Idents {
+    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
+        let mut buf = Vec::with_capacity(self.0.len());
+
+        for ident in self.0.iter() {
+            buf.push(format!("{ident}"));
+        }
+        if buf.len() > 1 {
+            // use square brackets only if there are more than one ident
+            write!(f, "[{}]", buf.join(", "))
+        } else {
+            write!(f, "{}", buf[0])
+        }
+    }
+}
+impl Idents {
+    /// constructs an iter over the [Ident]s that this contains.
+    pub fn iter(&self) -> std::slice::Iter<'_, Ident> {
+        self.0.iter()
+    }
+
+    /// the conjoined span of all idents in the `VecIdent`
+    #[must_use]
+    pub fn span(&self) -> Span {
+        Span {
+            lo: self.0.first().map(|i| i.span.lo).unwrap_or_default(),
+            hi: self.0.last().map(|i| i.span.hi).unwrap_or_default(),
+        }
+    }
+
+    /// Whether or not the first ident in this [`Idents`] matches `arg`
+    #[must_use]
+    pub fn starts_with(&self, arg: &str) -> bool {
+        self.0.first().is_some_and(|i| &*i.name == arg)
+    }
+
+    /// Whether or not the first `n` idents in this [`Idents`] match `arg`
+    #[must_use]
+    pub fn starts_with_sequence(&self, arg: &[&str]) -> bool {
+        if arg.len() > self.0.len() {
+            return false;
+        }
+        for (i, s) in arg.iter().enumerate() {
+            if &*self.0[i].name != *s {
+                return false;
+            }
+        }
+        true
+    }
+
+    /// The stringified dot-separated path of the idents in this [`Idents`]
+    /// E.g. `a.b.c`
+    #[must_use]
+    pub fn name(&self) -> Rc<str> {
+        if self.0.len() == 1 {
+            return self.0[0].name.clone();
+        }
+        let mut buf = String::new();
+        for ident in self.0.iter() {
+            if !buf.is_empty() {
+                buf.push('.');
+            }
+            buf.push_str(&ident.name);
+        }
+        Rc::from(buf)
+    }
+}
 /// An identifier.
 #[derive(Clone, Debug, Eq, Hash, PartialEq)]
 pub struct Ident {
diff --git a/compiler/qsc_hir/src/mut_visit.rs b/compiler/qsc_hir/src/mut_visit.rs
index 00333b70..9a07f2bf 100644
--- a/compiler/qsc_hir/src/mut_visit.rs
+++ b/compiler/qsc_hir/src/mut_visit.rs
@@ -48,6 +48,10 @@ pub trait MutVisitor: Sized {
         walk_ident(self, ident);
     }
 
+    fn visit_idents(&mut self, ident: &mut crate::hir::Idents) {
+        walk_idents(self, ident);
+    }
+
     fn visit_span(&mut self, _: &mut Span) {}
 }
 
@@ -62,7 +66,8 @@ pub fn walk_item(vis: &mut impl MutVisitor, item: &mut Item) {
 
     match &mut item.kind {
         ItemKind::Callable(decl) => vis.visit_callable_decl(decl),
-        ItemKind::Namespace(name, _) | ItemKind::Ty(name, _) => vis.visit_ident(name),
+        ItemKind::Namespace(name, _) => vis.visit_idents(name),
+        ItemKind::Ty(name, _) => vis.visit_ident(name),
     }
 }
 
@@ -228,3 +233,9 @@ pub fn walk_qubit_init(vis: &mut impl MutVisitor, init: &mut QubitInit) {
 pub fn walk_ident(vis: &mut impl MutVisitor, ident: &mut Ident) {
     vis.visit_span(&mut ident.span);
 }
+
+pub fn walk_idents(vis: &mut impl MutVisitor, ident: &mut crate::hir::Idents) {
+    for ref mut ident in ident.0.iter_mut() {
+        vis.visit_ident(ident);
+    }
+}
diff --git a/compiler/qsc_hir/src/visit.rs b/compiler/qsc_hir/src/visit.rs
index 6f9655c2..01f3679e 100644
--- a/compiler/qsc_hir/src/visit.rs
+++ b/compiler/qsc_hir/src/visit.rs
@@ -2,8 +2,8 @@
 // Licensed under the MIT License.
 
 use crate::hir::{
-    Block, CallableDecl, Expr, ExprKind, Ident, Item, ItemKind, Package, Pat, PatKind, QubitInit,
-    QubitInitKind, SpecBody, SpecDecl, Stmt, StmtKind, StringComponent,
+    Block, CallableDecl, Expr, ExprKind, Ident, Idents, Item, ItemKind, Package, Pat, PatKind,
+    QubitInit, QubitInitKind, SpecBody, SpecDecl, Stmt, StmtKind, StringComponent,
 };
 
 pub trait Visitor<'a>: Sized {
@@ -44,6 +44,10 @@ pub trait Visitor<'a>: Sized {
     }
 
     fn visit_ident(&mut self, _: &'a Ident) {}
+
+    fn visit_idents(&mut self, idents: &'a Idents) {
+        walk_idents(self, idents);
+    }
 }
 
 pub fn walk_package<'a>(vis: &mut impl Visitor<'a>, package: &'a Package) {
@@ -55,7 +59,8 @@ pub fn walk_package<'a>(vis: &mut impl Visitor<'a>, package: &'a Package) {
 pub fn walk_item<'a>(vis: &mut impl Visitor<'a>, item: &'a Item) {
     match &item.kind {
         ItemKind::Callable(decl) => vis.visit_callable_decl(decl),
-        ItemKind::Namespace(name, _) | ItemKind::Ty(name, _) => vis.visit_ident(name),
+        ItemKind::Namespace(name, _) => vis.visit_idents(name),
+        ItemKind::Ty(name, _) => vis.visit_ident(name),
     }
 }
 
@@ -201,3 +206,7 @@ pub fn walk_qubit_init<'a>(vis: &mut impl Visitor<'a>, init: &'a QubitInit) {
         QubitInitKind::Tuple(inits) => inits.iter().for_each(|i| vis.visit_qubit_init(i)),
     }
 }
+
+pub fn walk_idents<'a>(vis: &mut impl Visitor<'a>, idents: &'a Idents) {
+    idents.iter().for_each(|i| vis.visit_ident(i));
+}
diff --git a/compiler/qsc_lowerer/src/lib.rs b/compiler/qsc_lowerer/src/lib.rs
index 62909495..69be95f8 100644
--- a/compiler/qsc_lowerer/src/lib.rs
+++ b/compiler/qsc_lowerer/src/lib.rs
@@ -163,7 +163,16 @@ impl Lowerer {
     fn lower_item(&mut self, item: &hir::Item) -> fir::Item {
         let kind = match &item.kind {
             hir::ItemKind::Namespace(name, items) => {
-                let name = self.lower_ident(name);
+                let name = fir::Ident {
+                    id: self.lower_local_id(
+                        name.0
+                            .last()
+                            .expect("should have at least one ident in name")
+                            .id,
+                    ),
+                    span: name.span(),
+                    name: name.name(),
+                };
                 let items = items.iter().map(|i| lower_local_item_id(*i)).collect();
                 fir::ItemKind::Namespace(name, items)
             }
diff --git a/compiler/qsc_parse/src/item.rs b/compiler/qsc_parse/src/item.rs
index 14375d5b..7bb742d7 100644
--- a/compiler/qsc_parse/src/item.rs
+++ b/compiler/qsc_parse/src/item.rs
@@ -10,7 +10,7 @@ mod tests;
 use super::{
     expr::expr,
     keyword::Keyword,
-    prim::{dot_ident, ident, many, opt, pat, seq, token},
+    prim::{ident, many, opt, pat, seq, token},
     scan::ParserContext,
     stmt,
     ty::{self, ty},
@@ -18,7 +18,7 @@ use super::{
 };
 use crate::{
     lex::{Delim, TokenKind},
-    prim::{barrier, recovering, recovering_token, shorten},
+    prim::{barrier, path, recovering, recovering_token, shorten},
     stmt::check_semis,
     ty::array_or_arrow,
     ErrorKind,
@@ -136,7 +136,7 @@ fn parse_namespace(s: &mut ParserContext) -> Result<Namespace> {
     let lo = s.peek().span.lo;
     let doc = parse_doc(s).unwrap_or_default();
     token(s, TokenKind::Keyword(Keyword::Namespace))?;
-    let name = dot_ident(s)?;
+    let name = path(s)?;
     token(s, TokenKind::Open(Delim::Brace))?;
     let items = barrier(s, &[TokenKind::Close(Delim::Brace)], parse_many)?;
     recovering_token(s, TokenKind::Close(Delim::Brace));
@@ -144,7 +144,7 @@ fn parse_namespace(s: &mut ParserContext) -> Result<Namespace> {
         id: NodeId::default(),
         span: s.span(lo),
         doc: doc.into(),
-        name,
+        name: (*name).into(),
         items: items.into_boxed_slice(),
     })
 }
@@ -202,14 +202,24 @@ fn parse_visibility(s: &mut ParserContext) -> Result<Visibility> {
 
 fn parse_open(s: &mut ParserContext) -> Result<Box<ItemKind>> {
     token(s, TokenKind::Keyword(Keyword::Open))?;
-    let name = dot_ident(s)?;
+    let mut name = vec![*(ident(s)?)];
+    while let Ok(_dot) = token(s, TokenKind::Dot) {
+        name.push(*(ident(s)?));
+    }
     let alias = if token(s, TokenKind::Keyword(Keyword::As)).is_ok() {
-        Some(dot_ident(s)?)
+        Some(ident(s)?)
     } else {
         None
     };
+
+    // Peek to see if the next token is a dot -- this means it is likely a dot ident alias, and
+    // we want to provide a more helpful error message
+    if s.peek().kind == TokenKind::Dot {
+        return Err(Error(ErrorKind::DotIdentAlias(s.peek().span)));
+    }
+
     token(s, TokenKind::Semi)?;
-    Ok(Box::new(ItemKind::Open(name, alias)))
+    Ok(Box::new(ItemKind::Open(name.into(), alias)))
 }
 
 fn parse_newtype(s: &mut ParserContext) -> Result<Box<ItemKind>> {
diff --git a/compiler/qsc_parse/src/lib.rs b/compiler/qsc_parse/src/lib.rs
index 637efcb8..d8fc0c9c 100644
--- a/compiler/qsc_parse/src/lib.rs
+++ b/compiler/qsc_parse/src/lib.rs
@@ -74,6 +74,9 @@ enum ErrorKind {
     #[error("missing entry in sequence")]
     #[diagnostic(code("Qsc.Parse.MissingSeqEntry"))]
     MissingSeqEntry(#[label] Span),
+    #[error("dotted namespace aliases are not allowed")]
+    #[diagnostic(code("Qsc.Parse.DotIdentAlias"))]
+    DotIdentAlias(#[label] Span),
 }
 
 impl ErrorKind {
@@ -91,6 +94,7 @@ impl ErrorKind {
             Self::FloatingAttr(span) => Self::FloatingAttr(span + offset),
             Self::FloatingVisibility(span) => Self::FloatingVisibility(span + offset),
             Self::MissingSeqEntry(span) => Self::MissingSeqEntry(span + offset),
+            Self::DotIdentAlias(span) => Self::DotIdentAlias(span + offset),
         }
     }
 }
diff --git a/compiler/qsc_parse/src/prim.rs b/compiler/qsc_parse/src/prim.rs
index 96f64734..bdf7ac37 100644
--- a/compiler/qsc_parse/src/prim.rs
+++ b/compiler/qsc_parse/src/prim.rs
@@ -77,24 +77,6 @@ pub(super) fn ident(s: &mut ParserContext) -> Result<Box<Ident>> {
     }
 }
 
-/// This function parses a [Path] from the given context
-/// and converts it into a single ident, which contains dots (`.`)
-pub(super) fn dot_ident(s: &mut ParserContext) -> Result<Box<Ident>> {
-    let p = path(s)?;
-    let mut name = String::new();
-    if let Some(namespace) = p.namespace {
-        name.push_str(&namespace.name);
-        name.push('.');
-    }
-    name.push_str(&p.name.name);
-
-    Ok(Box::new(Ident {
-        id: p.id,
-        span: p.span,
-        name: name.into(),
-    }))
-}
-
 /// A `path` is a dot-separated list of idents like "Foo.Bar.Baz"
 /// this can be either a namespace name (in an open statement or namespace declaration) or
 /// it can be a direct reference to something in a namespace, like `Microsoft.Quantum.Diagnostics.DumpMachine()`
@@ -106,17 +88,20 @@ pub(super) fn path(s: &mut ParserContext) -> Result<Box<Path>> {
     }
 
     let name = parts.pop().expect("path should have at least one part");
-    let namespace = match (parts.first(), parts.last()) {
-        (Some(first), Some(last)) => {
-            let lo = first.span.lo;
-            let hi = last.span.hi;
-            Some(Box::new(Ident {
-                id: NodeId::default(),
-                span: Span { lo, hi },
-                name: join(parts.iter().map(|i| &i.name), ".").into(),
-            }))
-        }
-        _ => None,
+    let namespace = if parts.is_empty() {
+        None
+    } else {
+        Some(
+            parts
+                .iter()
+                .map(|part| Ident {
+                    id: NodeId::default(),
+                    span: part.span,
+                    name: part.name.clone(),
+                })
+                .collect::<Vec<_>>()
+                .into(),
+        )
     };
 
     Ok(Box::new(Path {
@@ -260,18 +245,6 @@ fn advanced(s: &ParserContext, from: u32) -> bool {
     s.peek().span.lo > from
 }
 
-fn join(mut strings: impl Iterator<Item = impl AsRef<str>>, sep: &str) -> String {
-    let mut string = String::new();
-    if let Some(s) = strings.next() {
-        string.push_str(s.as_ref());
-    }
-    for s in strings {
-        string.push_str(sep);
-        string.push_str(s.as_ref());
-    }
-    string
-}
-
 fn map_rule_name(name: &'static str, error: Error) -> Error {
     Error(match error.0 {
         ErrorKind::Rule(_, found, span) => ErrorKind::Rule(name, found, span),
diff --git a/compiler/qsc_partial_eval/src/lib.rs b/compiler/qsc_partial_eval/src/lib.rs
index 4a3c2ffc..d1cc5d05 100644
--- a/compiler/qsc_partial_eval/src/lib.rs
+++ b/compiler/qsc_partial_eval/src/lib.rs
@@ -565,19 +565,14 @@ impl<'a> PartialEvaluator<'a> {
             return Ok(EvalControlFlow::Continue(value));
         }
 
-        // Create the variable ID, create the instruction and insert it.
-        let bin_op_variable_id = self.resource_manager.next_var();
-        let (bin_op_rir_variable, bin_op_rir_ins) =
-            create_instruction_for_binary_operation_with_integer_operands(
+        // Generate the instructions.
+        let bin_op_rir_variable = self
+            .generate_instructions_for_binary_operation_with_integer_operands(
                 bin_op,
                 lhs_operand,
                 rhs_operand,
-                bin_op_variable_id,
                 bin_op_expr_span,
             )?;
-
-        // Insert the instruction.
-        self.get_current_rir_block_mut().0.push(bin_op_rir_ins);
         let value = Value::Var(map_rir_var_to_eval_var(bin_op_rir_variable));
         Ok(EvalControlFlow::Continue(value))
     }
@@ -1576,6 +1571,214 @@ impl<'a> PartialEvaluator<'a> {
         }
     }
 
+    #[allow(clippy::too_many_lines)]
+    fn generate_instructions_for_binary_operation_with_integer_operands(
+        &mut self,
+        bin_op: BinOp,
+        lhs_operand: Operand,
+        rhs_operand: Operand,
+        bin_op_expr_span: Span, // For diagnostic purposes only.
+    ) -> Result<rir::Variable, Error> {
+        let rir_variable = match bin_op {
+            BinOp::Add => {
+                let bin_op_variable_id = self.resource_manager.next_var();
+                let bin_op_rir_variable = rir::Variable::new_integer(bin_op_variable_id);
+                let bin_op_rir_ins =
+                    Instruction::Add(lhs_operand, rhs_operand, bin_op_rir_variable);
+                self.get_current_rir_block_mut().0.push(bin_op_rir_ins);
+                bin_op_rir_variable
+            }
+            BinOp::Sub => {
+                let bin_op_variable_id = self.resource_manager.next_var();
+                let bin_op_rir_variable = rir::Variable::new_integer(bin_op_variable_id);
+                let bin_op_rir_ins =
+                    Instruction::Sub(lhs_operand, rhs_operand, bin_op_rir_variable);
+                self.get_current_rir_block_mut().0.push(bin_op_rir_ins);
+                bin_op_rir_variable
+            }
+            BinOp::Mul => {
+                let bin_op_variable_id = self.resource_manager.next_var();
+                let bin_op_rir_variable = rir::Variable::new_integer(bin_op_variable_id);
+                let bin_op_rir_ins =
+                    Instruction::Mul(lhs_operand, rhs_operand, bin_op_rir_variable);
+                self.get_current_rir_block_mut().0.push(bin_op_rir_ins);
+                bin_op_rir_variable
+            }
+            BinOp::Div => {
+                // Validate that the RHS is not a zero.
+                if let Operand::Literal(Literal::Integer(0)) = rhs_operand {
+                    let error =
+                        Error::EvaluationFailed("division by zero".to_string(), bin_op_expr_span);
+                    return Err(error);
+                }
+                let bin_op_variable_id = self.resource_manager.next_var();
+                let bin_op_rir_variable = rir::Variable::new_integer(bin_op_variable_id);
+                let bin_op_rir_ins =
+                    Instruction::Sdiv(lhs_operand, rhs_operand, bin_op_rir_variable);
+                self.get_current_rir_block_mut().0.push(bin_op_rir_ins);
+                bin_op_rir_variable
+            }
+            BinOp::Mod => {
+                let bin_op_variable_id = self.resource_manager.next_var();
+                let bin_op_rir_variable = rir::Variable::new_integer(bin_op_variable_id);
+                let bin_op_rir_ins =
+                    Instruction::Srem(lhs_operand, rhs_operand, bin_op_rir_variable);
+                self.get_current_rir_block_mut().0.push(bin_op_rir_ins);
+                bin_op_rir_variable
+            }
+            BinOp::Exp => {
+                // Validate the exponent.
+                let Operand::Literal(Literal::Integer(exponent)) = rhs_operand else {
+                    let error = Error::Unexpected(
+                        "exponent must be a classical integer".to_string(),
+                        bin_op_expr_span,
+                    );
+                    return Err(error);
+                };
+                if exponent < 0 {
+                    let error = Error::EvaluationFailed(
+                        "exponent must be non-negative".to_string(),
+                        bin_op_expr_span,
+                    );
+                    return Err(error);
+                }
+
+                // Generate a series of multiplication instructions that represent the exponentiation.
+                let mut current_rir_variable =
+                    rir::Variable::new_integer(self.resource_manager.next_var());
+                let init_ins =
+                    Instruction::Store(Operand::Literal(Literal::Integer(1)), current_rir_variable);
+                self.get_current_rir_block_mut().0.push(init_ins);
+                for _ in 0..exponent {
+                    let mult_variable =
+                        rir::Variable::new_integer(self.resource_manager.next_var());
+                    let mult_ins = Instruction::Mul(
+                        Operand::Variable(current_rir_variable),
+                        lhs_operand,
+                        mult_variable,
+                    );
+                    self.get_current_rir_block_mut().0.push(mult_ins);
+                    current_rir_variable = mult_variable;
+                }
+                current_rir_variable
+            }
+            BinOp::AndB => {
+                let bin_op_variable_id = self.resource_manager.next_var();
+                let bin_op_rir_variable = rir::Variable::new_integer(bin_op_variable_id);
+                let bin_op_rir_ins =
+                    Instruction::BitwiseAnd(lhs_operand, rhs_operand, bin_op_rir_variable);
+                self.get_current_rir_block_mut().0.push(bin_op_rir_ins);
+                bin_op_rir_variable
+            }
+            BinOp::OrB => {
+                let bin_op_variable_id = self.resource_manager.next_var();
+                let bin_op_rir_variable = rir::Variable::new_integer(bin_op_variable_id);
+                let bin_op_rir_ins =
+                    Instruction::BitwiseOr(lhs_operand, rhs_operand, bin_op_rir_variable);
+                self.get_current_rir_block_mut().0.push(bin_op_rir_ins);
+                bin_op_rir_variable
+            }
+            BinOp::XorB => {
+                let bin_op_variable_id = self.resource_manager.next_var();
+                let bin_op_rir_variable = rir::Variable::new_integer(bin_op_variable_id);
+                let bin_op_rir_ins =
+                    Instruction::BitwiseXor(lhs_operand, rhs_operand, bin_op_rir_variable);
+                self.get_current_rir_block_mut().0.push(bin_op_rir_ins);
+                bin_op_rir_variable
+            }
+            BinOp::Shl => {
+                let bin_op_variable_id = self.resource_manager.next_var();
+                let bin_op_rir_variable = rir::Variable::new_integer(bin_op_variable_id);
+                let bin_op_rir_ins =
+                    Instruction::Shl(lhs_operand, rhs_operand, bin_op_rir_variable);
+                self.get_current_rir_block_mut().0.push(bin_op_rir_ins);
+                bin_op_rir_variable
+            }
+            BinOp::Shr => {
+                let bin_op_variable_id = self.resource_manager.next_var();
+                let bin_op_rir_variable = rir::Variable::new_integer(bin_op_variable_id);
+                let bin_op_rir_ins =
+                    Instruction::Ashr(lhs_operand, rhs_operand, bin_op_rir_variable);
+                self.get_current_rir_block_mut().0.push(bin_op_rir_ins);
+                bin_op_rir_variable
+            }
+            BinOp::Eq => {
+                let bin_op_variable_id = self.resource_manager.next_var();
+                let bin_op_rir_variable = rir::Variable::new_boolean(bin_op_variable_id);
+                let bin_op_rir_ins = Instruction::Icmp(
+                    ConditionCode::Eq,
+                    lhs_operand,
+                    rhs_operand,
+                    bin_op_rir_variable,
+                );
+                self.get_current_rir_block_mut().0.push(bin_op_rir_ins);
+                bin_op_rir_variable
+            }
+            BinOp::Neq => {
+                let bin_op_variable_id = self.resource_manager.next_var();
+                let bin_op_rir_variable = rir::Variable::new_boolean(bin_op_variable_id);
+                let bin_op_rir_ins = Instruction::Icmp(
+                    ConditionCode::Ne,
+                    lhs_operand,
+                    rhs_operand,
+                    bin_op_rir_variable,
+                );
+                self.get_current_rir_block_mut().0.push(bin_op_rir_ins);
+                bin_op_rir_variable
+            }
+            BinOp::Gt => {
+                let bin_op_variable_id = self.resource_manager.next_var();
+                let bin_op_rir_variable = rir::Variable::new_boolean(bin_op_variable_id);
+                let bin_op_rir_ins = Instruction::Icmp(
+                    ConditionCode::Sgt,
+                    lhs_operand,
+                    rhs_operand,
+                    bin_op_rir_variable,
+                );
+                self.get_current_rir_block_mut().0.push(bin_op_rir_ins);
+                bin_op_rir_variable
+            }
+            BinOp::Gte => {
+                let bin_op_variable_id = self.resource_manager.next_var();
+                let bin_op_rir_variable = rir::Variable::new_boolean(bin_op_variable_id);
+                let bin_op_rir_ins = Instruction::Icmp(
+                    ConditionCode::Sge,
+                    lhs_operand,
+                    rhs_operand,
+                    bin_op_rir_variable,
+                );
+                self.get_current_rir_block_mut().0.push(bin_op_rir_ins);
+                bin_op_rir_variable
+            }
+            BinOp::Lt => {
+                let bin_op_variable_id = self.resource_manager.next_var();
+                let bin_op_rir_variable = rir::Variable::new_boolean(bin_op_variable_id);
+                let bin_op_rir_ins = Instruction::Icmp(
+                    ConditionCode::Slt,
+                    lhs_operand,
+                    rhs_operand,
+                    bin_op_rir_variable,
+                );
+                self.get_current_rir_block_mut().0.push(bin_op_rir_ins);
+                bin_op_rir_variable
+            }
+            BinOp::Lte => {
+                let bin_op_variable_id = self.resource_manager.next_var();
+                let bin_op_rir_variable = rir::Variable::new_boolean(bin_op_variable_id);
+                let bin_op_rir_ins = Instruction::Icmp(
+                    ConditionCode::Sle,
+                    lhs_operand,
+                    rhs_operand,
+                    bin_op_rir_variable,
+                );
+                self.get_current_rir_block_mut().0.push(bin_op_rir_ins);
+                bin_op_rir_variable
+            }
+            _ => panic!("unsupported binary operation for integers: {bin_op:?}"),
+        };
+        Ok(rir_variable)
+    }
+
     fn get_block(&self, id: BlockId) -> &'a Block {
         let block_id = StoreBlockId::from((self.get_current_package_id(), id));
         self.package_store.get_block(block_id)
@@ -2267,146 +2470,6 @@ impl<'a> PartialEvaluator<'a> {
     }
 }
 
-#[allow(clippy::too_many_lines)]
-fn create_instruction_for_binary_operation_with_integer_operands(
-    bin_op: BinOp,
-    lhs_operand: Operand,
-    rhs_operand: Operand,
-    bin_op_variable_id: rir::VariableId,
-    bin_op_expr_span: Span, // For diagnostic purposes only.
-) -> Result<(rir::Variable, Instruction), Error> {
-    let (rir_variable, rir_ins) = match bin_op {
-        BinOp::Add => {
-            let bin_op_rir_variable = rir::Variable::new_integer(bin_op_variable_id);
-            let bin_op_rir_ins = Instruction::Add(lhs_operand, rhs_operand, bin_op_rir_variable);
-            (bin_op_rir_variable, bin_op_rir_ins)
-        }
-        BinOp::Sub => {
-            let bin_op_rir_variable = rir::Variable::new_integer(bin_op_variable_id);
-            let bin_op_rir_ins = Instruction::Sub(lhs_operand, rhs_operand, bin_op_rir_variable);
-            (bin_op_rir_variable, bin_op_rir_ins)
-        }
-        BinOp::Mul => {
-            let bin_op_rir_variable = rir::Variable::new_integer(bin_op_variable_id);
-            let bin_op_rir_ins = Instruction::Mul(lhs_operand, rhs_operand, bin_op_rir_variable);
-            (bin_op_rir_variable, bin_op_rir_ins)
-        }
-        BinOp::Div => {
-            // Validate that the RHS is not a zero.
-            if let Operand::Literal(Literal::Integer(0)) = rhs_operand {
-                let error =
-                    Error::EvaluationFailed("division by zero".to_string(), bin_op_expr_span);
-                return Err(error);
-            }
-            let bin_op_rir_variable = rir::Variable::new_integer(bin_op_variable_id);
-            let bin_op_rir_ins = Instruction::Sdiv(lhs_operand, rhs_operand, bin_op_rir_variable);
-            (bin_op_rir_variable, bin_op_rir_ins)
-        }
-        BinOp::Mod => {
-            let bin_op_rir_variable = rir::Variable::new_integer(bin_op_variable_id);
-            let bin_op_rir_ins = Instruction::Srem(lhs_operand, rhs_operand, bin_op_rir_variable);
-            (bin_op_rir_variable, bin_op_rir_ins)
-        }
-        BinOp::Exp => {
-            let error = Error::Unimplemented(
-                "exponentiation for integer operands".to_string(),
-                bin_op_expr_span,
-            );
-            return Err(error);
-        }
-        BinOp::AndB => {
-            let bin_op_rir_variable = rir::Variable::new_integer(bin_op_variable_id);
-            let bin_op_rir_ins =
-                Instruction::BitwiseAnd(lhs_operand, rhs_operand, bin_op_rir_variable);
-            (bin_op_rir_variable, bin_op_rir_ins)
-        }
-        BinOp::OrB => {
-            let bin_op_rir_variable = rir::Variable::new_integer(bin_op_variable_id);
-            let bin_op_rir_ins =
-                Instruction::BitwiseOr(lhs_operand, rhs_operand, bin_op_rir_variable);
-            (bin_op_rir_variable, bin_op_rir_ins)
-        }
-        BinOp::XorB => {
-            let bin_op_rir_variable = rir::Variable::new_integer(bin_op_variable_id);
-            let bin_op_rir_ins =
-                Instruction::BitwiseXor(lhs_operand, rhs_operand, bin_op_rir_variable);
-            (bin_op_rir_variable, bin_op_rir_ins)
-        }
-        BinOp::Shl => {
-            let bin_op_rir_variable = rir::Variable::new_integer(bin_op_variable_id);
-            let bin_op_rir_ins = Instruction::Shl(lhs_operand, rhs_operand, bin_op_rir_variable);
-            (bin_op_rir_variable, bin_op_rir_ins)
-        }
-        BinOp::Shr => {
-            let bin_op_rir_variable = rir::Variable::new_integer(bin_op_variable_id);
-            let bin_op_rir_ins = Instruction::Ashr(lhs_operand, rhs_operand, bin_op_rir_variable);
-            (bin_op_rir_variable, bin_op_rir_ins)
-        }
-        BinOp::Eq => {
-            let bin_op_rir_variable = rir::Variable::new_boolean(bin_op_variable_id);
-            let bin_op_rir_ins = Instruction::Icmp(
-                ConditionCode::Eq,
-                lhs_operand,
-                rhs_operand,
-                bin_op_rir_variable,
-            );
-            (bin_op_rir_variable, bin_op_rir_ins)
-        }
-        BinOp::Neq => {
-            let bin_op_rir_variable = rir::Variable::new_boolean(bin_op_variable_id);
-            let bin_op_rir_ins = Instruction::Icmp(
-                ConditionCode::Ne,
-                lhs_operand,
-                rhs_operand,
-                bin_op_rir_variable,
-            );
-            (bin_op_rir_variable, bin_op_rir_ins)
-        }
-        BinOp::Gt => {
-            let bin_op_rir_variable = rir::Variable::new_boolean(bin_op_variable_id);
-            let bin_op_rir_ins = Instruction::Icmp(
-                ConditionCode::Sgt,
-                lhs_operand,
-                rhs_operand,
-                bin_op_rir_variable,
-            );
-            (bin_op_rir_variable, bin_op_rir_ins)
-        }
-        BinOp::Gte => {
-            let bin_op_rir_variable = rir::Variable::new_boolean(bin_op_variable_id);
-            let bin_op_rir_ins = Instruction::Icmp(
-                ConditionCode::Sge,
-                lhs_operand,
-                rhs_operand,
-                bin_op_rir_variable,
-            );
-            (bin_op_rir_variable, bin_op_rir_ins)
-        }
-        BinOp::Lt => {
-            let bin_op_rir_variable = rir::Variable::new_boolean(bin_op_variable_id);
-            let bin_op_rir_ins = Instruction::Icmp(
-                ConditionCode::Slt,
-                lhs_operand,
-                rhs_operand,
-                bin_op_rir_variable,
-            );
-            (bin_op_rir_variable, bin_op_rir_ins)
-        }
-        BinOp::Lte => {
-            let bin_op_rir_variable = rir::Variable::new_boolean(bin_op_variable_id);
-            let bin_op_rir_ins = Instruction::Icmp(
-                ConditionCode::Sle,
-                lhs_operand,
-                rhs_operand,
-                bin_op_rir_variable,
-            );
-            (bin_op_rir_variable, bin_op_rir_ins)
-        }
-        _ => panic!("unsupported binary operation for integers: {bin_op:?}"),
-    };
-    Ok((rir_variable, rir_ins))
-}
-
 fn eval_bin_op_with_bool_literals(
     bin_op: BinOp,
     lhs_literal: Literal,
diff --git a/compiler/qsc_passes/src/common.rs b/compiler/qsc_passes/src/common.rs
index d258baba..8afaea8f 100644
--- a/compiler/qsc_passes/src/common.rs
+++ b/compiler/qsc_passes/src/common.rs
@@ -1,7 +1,7 @@
 // Copyright (c) Microsoft Corporation.
 // Licensed under the MIT License.
 
-use qsc_data_structures::span::Span;
+use qsc_data_structures::{namespaces::NamespaceId, span::Span};
 use qsc_hir::{
     assigner::Assigner,
     global::Table,
@@ -81,7 +81,7 @@ impl IdentTemplate {
 
 pub(crate) fn create_gen_core_ref(
     core: &Table,
-    namespace: &str,
+    namespace: NamespaceId,
     name: &str,
     generics: Vec<GenericArg>,
     span: Span,
diff --git a/compiler/qsc_passes/src/invert_block.rs b/compiler/qsc_passes/src/invert_block.rs
index f89cc062..fa2e1a06 100644
--- a/compiler/qsc_passes/src/invert_block.rs
+++ b/compiler/qsc_passes/src/invert_block.rs
@@ -17,6 +17,7 @@ use rustc_hash::FxHashSet;
 use crate::{
     common::{create_gen_core_ref, generated_name},
     logic_sep::{find_quantum_stmts, Error},
+    CORE_NAMESPACE,
 };
 
 pub(crate) fn adj_invert_block(
@@ -329,6 +330,9 @@ fn make_range_field(range_id: NodeId, field: PrimField) -> Expr {
 }
 
 fn make_array_index_range_reverse(core: &Table, arr_id: NodeId, arr_ty: &Ty) -> Expr {
+    let ns = core
+        .find_namespace(CORE_NAMESPACE.iter().copied())
+        .expect("prelude namespaces should exist");
     let len = Box::new(Expr {
         id: NodeId::default(),
         span: Span::default(),
@@ -336,7 +340,7 @@ fn make_array_index_range_reverse(core: &Table, arr_id: NodeId, arr_ty: &Ty) ->
         kind: ExprKind::Call(
             Box::new(create_gen_core_ref(
                 core,
-                "Microsoft.Quantum.Core",
+                ns,
                 "Length",
                 vec![GenericArg::Ty(arr_ty.clone())],
                 Span::default(),
diff --git a/compiler/qsc_passes/src/lib.rs b/compiler/qsc_passes/src/lib.rs
index aabadc75..948b6f49 100644
--- a/compiler/qsc_passes/src/lib.rs
+++ b/compiler/qsc_passes/src/lib.rs
@@ -36,6 +36,9 @@ use qsc_rca::{PackageComputeProperties, PackageStoreComputeProperties};
 use replace_qubit_allocation::ReplaceQubitAllocation;
 use thiserror::Error;
 
+pub(crate) static CORE_NAMESPACE: &[&str] = &["Microsoft", "Quantum", "Core"];
+pub(crate) static QIR_RUNTIME_NAMESPACE: &[&str] = &["QIR", "Runtime"];
+
 #[derive(Clone, Debug, Diagnostic, Error)]
 #[diagnostic(transparent)]
 #[error(transparent)]
diff --git a/compiler/qsc_passes/src/loop_unification.rs b/compiler/qsc_passes/src/loop_unification.rs
index 7edef042..28427fc1 100644
--- a/compiler/qsc_passes/src/loop_unification.rs
+++ b/compiler/qsc_passes/src/loop_unification.rs
@@ -13,6 +13,7 @@ use qsc_hir::{
 };
 
 use crate::common::{create_gen_core_ref, generated_name, IdentTemplate};
+use crate::CORE_NAMESPACE;
 
 #[cfg(test)]
 mod tests;
@@ -31,7 +32,6 @@ impl LoopUni<'_> {
         span: Span,
     ) -> Expr {
         let cond_span = cond.span;
-
         let continue_cond_id = self.gen_ident("continue_cond", Ty::Prim(Prim::Bool), cond_span);
         let continue_cond_init = continue_cond_id.gen_id_init(
             Mutability::Mutable,
@@ -117,6 +117,7 @@ impl LoopUni<'_> {
         }
     }
 
+    #[allow(clippy::too_many_lines)]
     fn visit_for_array(
         &mut self,
         iter: Pat,
@@ -132,9 +133,13 @@ impl LoopUni<'_> {
         let Ty::Array(item_ty) = &array_id.ty else {
             panic!("iterator should have array type");
         };
+        let ns = self
+            .core
+            .find_namespace(CORE_NAMESPACE.iter().copied())
+            .expect("prelude namespaces should exist");
         let mut len_callee = create_gen_core_ref(
             self.core,
-            "Microsoft.Quantum.Core",
+            ns,
             "Length",
             vec![GenericArg::Ty((**item_ty).clone())],
             array_id.span,
diff --git a/compiler/qsc_passes/src/replace_qubit_allocation.rs b/compiler/qsc_passes/src/replace_qubit_allocation.rs
index 4f92984c..c6e8bc7c 100644
--- a/compiler/qsc_passes/src/replace_qubit_allocation.rs
+++ b/compiler/qsc_passes/src/replace_qubit_allocation.rs
@@ -4,6 +4,7 @@
 #[cfg(test)]
 mod tests;
 
+use qsc_data_structures::namespaces::NamespaceId;
 use qsc_data_structures::span::Span;
 use qsc_hir::{
     assigner::Assigner,
@@ -17,6 +18,7 @@ use qsc_hir::{
 use std::mem::take;
 
 use crate::common::{create_gen_core_ref, generated_name, IdentTemplate};
+use crate::QIR_RUNTIME_NAMESPACE;
 
 #[derive(Debug, Clone)]
 struct QubitIdent {
@@ -238,9 +240,10 @@ impl<'a> ReplaceQubitAllocation<'a> {
     }
 
     fn create_alloc_stmt(&mut self, ident: &IdentTemplate) -> Stmt {
+        let ns = self.get_qir_runtime_namespace();
         let mut call_expr = create_gen_core_ref(
             self.core,
-            "QIR.Runtime",
+            ns,
             "__quantum__rt__qubit_allocate",
             Vec::new(),
             ident.span,
@@ -250,21 +253,18 @@ impl<'a> ReplaceQubitAllocation<'a> {
     }
 
     fn create_array_alloc_stmt(&mut self, ident: &IdentTemplate, array_size: Expr) -> Stmt {
-        let mut call_expr = create_gen_core_ref(
-            self.core,
-            "QIR.Runtime",
-            "AllocateQubitArray",
-            Vec::new(),
-            ident.span,
-        );
+        let ns = self.get_qir_runtime_namespace();
+        let mut call_expr =
+            create_gen_core_ref(self.core, ns, "AllocateQubitArray", Vec::new(), ident.span);
         call_expr.id = self.assigner.next_node();
         create_general_alloc_stmt(self.assigner, ident, call_expr, Some(array_size))
     }
 
     fn create_dealloc_stmt(&mut self, ident: &IdentTemplate) -> Stmt {
+        let ns = self.get_qir_runtime_namespace();
         let mut call_expr = create_gen_core_ref(
             self.core,
-            "QIR.Runtime",
+            ns,
             "__quantum__rt__qubit_release",
             Vec::new(),
             ident.span,
@@ -274,16 +274,17 @@ impl<'a> ReplaceQubitAllocation<'a> {
     }
 
     fn create_array_dealloc_stmt(&mut self, ident: &IdentTemplate) -> Stmt {
-        let mut call_expr = create_gen_core_ref(
-            self.core,
-            "QIR.Runtime",
-            "ReleaseQubitArray",
-            Vec::new(),
-            ident.span,
-        );
+        let ns = self.get_qir_runtime_namespace();
+        let mut call_expr =
+            create_gen_core_ref(self.core, ns, "ReleaseQubitArray", Vec::new(), ident.span);
         call_expr.id = self.assigner.next_node();
         create_general_dealloc_stmt(self.assigner, call_expr, ident)
     }
+    fn get_qir_runtime_namespace(&self) -> NamespaceId {
+        self.core
+            .find_namespace(QIR_RUNTIME_NAMESPACE.iter().copied())
+            .expect("prelude namespaces should exist")
+    }
 }
 
 impl MutVisitor for ReplaceQubitAllocation<'_> {
@@ -412,11 +413,14 @@ fn create_qubit_global_alloc(
     qubit_init: QubitInit,
 ) -> StmtKind {
     fn qubit_alloc_expr(assigner: &mut Assigner, core: &Table, qubit_init: QubitInit) -> Expr {
+        let ns = core
+            .find_namespace(QIR_RUNTIME_NAMESPACE.iter().copied())
+            .expect("prelude namespaces should exist");
         match qubit_init.kind {
             QubitInitKind::Array(mut expr) => {
                 let mut call_expr = create_gen_core_ref(
                     core,
-                    "QIR.Runtime",
+                    ns,
                     "AllocateQubitArray",
                     Vec::new(),
                     qubit_init.span,
@@ -432,7 +436,7 @@ fn create_qubit_global_alloc(
             QubitInitKind::Single => {
                 let mut call_expr = create_gen_core_ref(
                     core,
-                    "QIR.Runtime",
+                    ns,
                     "__quantum__rt__qubit_allocate",
                     Vec::new(),
                     qubit_init.span,
diff --git a/compiler/qsc_rca/src/core.rs b/compiler/qsc_rca/src/core.rs
index f5510543..53c335b8 100644
--- a/compiler/qsc_rca/src/core.rs
+++ b/compiler/qsc_rca/src/core.rs
@@ -15,8 +15,8 @@ use qsc_data_structures::{functors::FunctorApp, index_map::IndexMap};
 use qsc_fir::{
     extensions::InputParam,
     fir::{
-        Block, BlockId, CallableDecl, CallableImpl, CallableKind, Expr, ExprId, ExprKind, Global,
-        Ident, Item, ItemKind, LocalVarId, Mutability, Package, PackageId, PackageLookup,
+        BinOp, Block, BlockId, CallableDecl, CallableImpl, CallableKind, Expr, ExprId, ExprKind,
+        Global, Ident, Item, ItemKind, LocalVarId, Mutability, Package, PackageId, PackageLookup,
         PackageStore, PackageStoreLookup, Pat, PatId, PatKind, Res, SpecDecl, SpecImpl, Stmt,
         StmtId, StmtKind, StoreExprId, StoreItemId, StorePatId, StringComponent,
     },
@@ -265,6 +265,35 @@ impl<'a> Analyzer<'a> {
         compute_kind
     }
 
+    fn analyze_expr_bin_op_exp(&mut self, lhs_expr_id: ExprId, rhs_expr_id: ExprId) -> ComputeKind {
+        // Visit the LHS and RHS expressions to determine their compute kind.
+        self.visit_expr(lhs_expr_id);
+        self.visit_expr(rhs_expr_id);
+
+        // The compute kind of a binary operator expression is the aggregation of its LHS and RHS expressions.
+        let application_instance = self.get_current_application_instance();
+        let lhs_compute_kind = *application_instance.get_expr_compute_kind(lhs_expr_id);
+        let rhs_compute_kind = *application_instance.get_expr_compute_kind(rhs_expr_id);
+        let mut compute_kind = ComputeKind::Classical;
+        compute_kind = compute_kind.aggregate(lhs_compute_kind);
+        compute_kind = compute_kind.aggregate(rhs_compute_kind);
+
+        // As a special case for exp, if the rhs is dynamic the expression gets an extra runtime feature.
+        // This is because we don't emit a native exponential binary operator but unroll it into a sequence
+        // of multiplications, which requires the rhs to be known at compile time.
+        if rhs_compute_kind.is_dynamic() {
+            compute_kind = compute_kind.aggregate_runtime_features(
+                ComputeKind::new_with_runtime_features(
+                    RuntimeFeatureFlags::UseOfDynamicExponent,
+                    ValueKind::Element(RuntimeKind::Static),
+                ),
+                ValueKind::Element(RuntimeKind::Static),
+            );
+        }
+
+        compute_kind
+    }
+
     fn analyze_expr_block(&mut self, block_id: BlockId) -> ComputeKind {
         // Visit the block to determine its compute kind.
         self.visit_block(block_id);
@@ -1639,6 +1668,9 @@ impl<'a> Visitor<'a> for Analyzer<'a> {
                     *index_expr_id,
                     *replacement_value_expr_id,
                 ),
+            ExprKind::BinOp(BinOp::Exp, lhs_expr_id, rhs_expr_id) => {
+                self.analyze_expr_bin_op_exp(*lhs_expr_id, *rhs_expr_id)
+            }
             ExprKind::BinOp(_, lhs_expr_id, rhs_expr_id) => {
                 self.analyze_expr_bin_op(*lhs_expr_id, *rhs_expr_id, &expr.ty)
             }
diff --git a/compiler/qsc_rca/src/errors.rs b/compiler/qsc_rca/src/errors.rs
index efef75ee..39e018a7 100644
--- a/compiler/qsc_rca/src/errors.rs
+++ b/compiler/qsc_rca/src/errors.rs
@@ -65,6 +65,13 @@ pub enum Error {
     #[diagnostic(code("Qsc.CapabilitiesCk.UseOfDynamicString"))]
     UseOfDynamicString(#[label] Span),
 
+    #[error("cannot use a dynamic exponent")]
+    #[diagnostic(help(
+        "using an exponent that depends on a measurement result is not supported by the current target"
+    ))]
+    #[diagnostic(code("Qsc.CapabilitiesCk.UseOfDynamicExponent"))]
+    UseOfDynamicExponent(#[label] Span),
+
     #[error("cannot use a dynamically-sized array")]
     #[diagnostic(help(
         "using an array whose size depends on a measurement result is not supported by the current target"
@@ -191,6 +198,9 @@ pub fn generate_errors_from_runtime_features(
     if runtime_features.contains(RuntimeFeatureFlags::UseOfDynamicString) {
         errors.push(Error::UseOfDynamicString(span));
     }
+    if runtime_features.contains(RuntimeFeatureFlags::UseOfDynamicExponent) {
+        errors.push(Error::UseOfDynamicExponent(span));
+    }
     if runtime_features.contains(RuntimeFeatureFlags::UseOfDynamicallySizedArray) {
         errors.push(Error::UseOfDynamicallySizedArray(span));
     }
diff --git a/compiler/qsc_rca/src/lib.rs b/compiler/qsc_rca/src/lib.rs
index 6fb654aa..719d971f 100644
--- a/compiler/qsc_rca/src/lib.rs
+++ b/compiler/qsc_rca/src/lib.rs
@@ -775,6 +775,8 @@ bitflags! {
         const UseOfDoubleOutput = 1 << 23;
         // Use of an `Int` as output of a computation.
         const UseOfIntOutput = 1 << 24;
+        // Use of a dynamic exponent in a computation.
+        const UseOfDynamicExponent = 1 << 25;
     }
 }
 
@@ -871,6 +873,9 @@ impl RuntimeFeatureFlags {
         if self.contains(RuntimeFeatureFlags::UseOfAdvancedOutput) {
             capabilities |= TargetCapabilityFlags::HigherLevelConstructs;
         }
+        if self.contains(RuntimeFeatureFlags::UseOfDynamicExponent) {
+            capabilities |= TargetCapabilityFlags::BackwardsBranching;
+        }
         capabilities
     }
 }
diff --git a/language_service/src/code_lens.rs b/language_service/src/code_lens.rs
index 057b273f..4456379b 100644
--- a/language_service/src/code_lens.rs
+++ b/language_service/src/code_lens.rs
@@ -42,7 +42,7 @@ pub(crate) fn get_code_lenses(
                     .and_then(|parent_id| user_unit.package.items.get(parent_id))
                     .map(|parent| &parent.kind)
                 {
-                    let namespace = ns.name.to_string();
+                    let namespace = ns.name();
                     let range = into_range(position_encoding, decl.span, &user_unit.sources);
                     let name = decl.name.name.clone();
 
diff --git a/language_service/src/completion.rs b/language_service/src/completion.rs
index 7f068323..b6a54a8e 100644
--- a/language_service/src/completion.rs
+++ b/language_service/src/completion.rs
@@ -7,19 +7,21 @@ mod tests;
 use crate::compilation::{Compilation, CompilationKind};
 use crate::protocol::{CompletionItem, CompletionItemKind, CompletionList, TextEdit};
 use crate::qsc_utils::{into_range, span_contains};
+
 use qsc::ast::visit::{self, Visitor};
 use qsc::display::{CodeDisplay, Lookup};
+
 use qsc::hir::{ItemKind, Package, PackageId, Visibility};
 use qsc::line_column::{Encoding, Position, Range};
-use qsc::resolve::{Local, LocalKind};
+use qsc::{
+    resolve::{Local, LocalKind},
+    PRELUDE,
+};
 use rustc_hash::FxHashSet;
 use std::rc::Rc;
 
-const PRELUDE: [&str; 3] = [
-    "Microsoft.Quantum.Canon",
-    "Microsoft.Quantum.Core",
-    "Microsoft.Quantum.Intrinsic",
-];
+type NamespaceName = Vec<Rc<str>>;
+type NamespaceAlias = Rc<str>;
 
 pub(crate) fn get_completions(
     compilation: &Compilation,
@@ -68,10 +70,13 @@ pub(crate) fn get_completions(
         None => String::new(),
     };
 
+    let mut prelude_ns_ids: Vec<_> = PRELUDE
+        .into_iter()
+        .map(|ns| (ns.into_iter().map(Rc::from).collect(), None))
+        .collect();
+
     // The PRELUDE namespaces are always implicitly opened.
-    context_finder
-        .opens
-        .extend(PRELUDE.into_iter().map(|ns| (Rc::from(ns), None)));
+    context_finder.opens.append(&mut prelude_ns_ids);
 
     let mut builder = CompletionListBuilder::new();
 
@@ -272,9 +277,9 @@ impl CompletionListBuilder {
     fn push_globals(
         &mut self,
         compilation: &Compilation,
-        opens: &[(Rc<str>, Option<Rc<str>>)],
+        opens: &[(NamespaceName, Option<NamespaceAlias>)],
         insert_open_range: Option<Range>,
-        current_namespace_name: &Option<Rc<str>>,
+        current_namespace_name: &Option<Vec<Rc<str>>>,
         indent: &String,
     ) {
         let core = &compilation
@@ -391,12 +396,16 @@ impl CompletionListBuilder {
         self.current_sort_group += 1;
     }
 
+    /// Get all callables in a package
     fn get_callables<'a>(
         compilation: &'a Compilation,
         package_id: PackageId,
-        opens: &'a [(Rc<str>, Option<Rc<str>>)],
+        // name and alias
+        opens: &'a [(NamespaceName, Option<NamespaceAlias>)],
+        // The range at which to insert an open statement if one is needed
         insert_open_at: Option<Range>,
-        current_namespace_name: Option<Rc<str>>,
+        // The name of the current namespace, if any --
+        current_namespace_name: Option<Vec<Rc<str>>>,
         indent: &'a String,
     ) -> impl Iterator<Item = (CompletionItem, u32)> + 'a {
         let package = &compilation
@@ -413,7 +422,7 @@ impl CompletionListBuilder {
             if let Some(item_id) = i.parent {
                 if let Some(parent) = package.items.get(item_id) {
                     if let ItemKind::Namespace(namespace, _) = &parent.kind {
-                        if namespace.name.starts_with("Microsoft.Quantum.Unstable") {
+                        if namespace.starts_with_sequence(&["Microsoft", "Quantum", "Unstable"]) {
                             return None;
                         }
                         // If the item's visibility is internal, the item may be ignored
@@ -424,7 +433,7 @@ impl CompletionListBuilder {
                             // ignore item if the user is not in the item's namespace
                             match &current_namespace_name {
                                 Some(curr_ns) => {
-                                    if *curr_ns != namespace.name {
+                                    if *curr_ns != Into::<Vec<Rc<_>>>::into(namespace) {
                                         return None;
                                     }
                                 }
@@ -441,35 +450,35 @@ impl CompletionListBuilder {
                                 // Everything that starts with a __ goes last in the list
                                 let sort_group = u32::from(name.starts_with("__"));
                                 let mut additional_edits = vec![];
-                                let mut qualification: Option<Rc<str>> = None;
+                                let mut qualification: Option<Vec<Rc<str>>> = None;
                                 match &current_namespace_name {
-                                    Some(curr_ns) if *curr_ns == namespace.name => {}
+                                    Some(curr_ns)
+                                        if *curr_ns == Into::<Vec<_>>::into(namespace) => {}
                                     _ => {
                                         // open is an option of option of Rc<str>
                                         // the first option tells if it found an open with the namespace name
                                         // the second, nested option tells if that open has an alias
                                         let open = opens.iter().find_map(|(name, alias)| {
-                                            if *name == namespace.name {
+                                            if *name == Into::<Vec<_>>::into(namespace) {
                                                 Some(alias)
                                             } else {
                                                 None
                                             }
                                         });
                                         qualification = match open {
-                                            Some(alias) => alias.clone(),
+                                            Some(alias) => alias.clone().map(|x| vec![x]),
                                             None => match insert_open_at {
                                                 Some(start) => {
                                                     additional_edits.push(TextEdit {
                                                         new_text: format!(
-                                                            "open {};{}",
-                                                            namespace.name.clone(),
-                                                            indent,
+                                                            "open {};{indent}",
+                                                            namespace.name()
                                                         ),
                                                         range: start,
                                                     });
                                                     None
                                                 }
-                                                None => Some(namespace.name.clone()),
+                                                None => Some(namespace.into()),
                                             },
                                         }
                                     }
@@ -482,7 +491,7 @@ impl CompletionListBuilder {
                                 };
 
                                 let label = if let Some(qualification) = qualification {
-                                    format!("{qualification}.{name}")
+                                    format!("{}.{name}", qualification.join("."))
                                 } else {
                                     name.to_owned()
                                 };
@@ -506,6 +515,7 @@ impl CompletionListBuilder {
         })
     }
 
+    /// Get all callables in the core package
     fn get_core_callables<'a>(
         compilation: &'a Compilation,
         package: &'a Package,
@@ -536,10 +546,10 @@ impl CompletionListBuilder {
     fn get_namespaces(package: &'_ Package) -> impl Iterator<Item = CompletionItem> + '_ {
         package.items.values().filter_map(|i| match &i.kind {
             ItemKind::Namespace(namespace, _)
-                if !namespace.name.starts_with("Microsoft.Quantum.Unstable") =>
+                if !namespace.starts_with_sequence(&["Microsoft", "Quantum", "Unstable"]) =>
             {
                 Some(CompletionItem::new(
-                    namespace.name.to_string(),
+                    namespace.name().to_string(),
                     CompletionItemKind::Module,
                 ))
             }
@@ -548,6 +558,7 @@ impl CompletionListBuilder {
     }
 }
 
+/// Convert a local into a completion item
 fn local_completion(
     candidate: &Local,
     compilation: &Compilation,
@@ -610,9 +621,9 @@ fn local_completion(
 struct ContextFinder {
     offset: u32,
     context: Context,
-    opens: Vec<(Rc<str>, Option<Rc<str>>)>,
+    opens: Vec<(NamespaceName, Option<NamespaceAlias>)>,
     start_of_namespace: Option<u32>,
-    current_namespace_name: Option<Rc<str>>,
+    current_namespace_name: Option<Vec<Rc<str>>>,
 }
 
 #[derive(Debug, PartialEq)]
@@ -627,7 +638,7 @@ enum Context {
 impl Visitor<'_> for ContextFinder {
     fn visit_namespace(&mut self, namespace: &'_ qsc::ast::Namespace) {
         if span_contains(namespace.span, self.offset) {
-            self.current_namespace_name = Some(namespace.name.name.clone());
+            self.current_namespace_name = Some(namespace.name.clone().into());
             self.context = Context::Namespace;
             self.opens = vec![];
             self.start_of_namespace = None;
@@ -641,10 +652,8 @@ impl Visitor<'_> for ContextFinder {
         }
 
         if let qsc::ast::ItemKind::Open(name, alias) = &*item.kind {
-            self.opens.push((
-                name.name.clone(),
-                alias.as_ref().map(|alias| alias.name.clone()),
-            ));
+            self.opens
+                .push((name.into(), alias.as_ref().map(|alias| alias.name.clone())));
         }
 
         if span_contains(item.span, self.offset) {
diff --git a/language_service/src/hover.rs b/language_service/src/hover.rs
index a4c62855..830387e2 100644
--- a/language_service/src/hover.rs
+++ b/language_service/src/hover.rs
@@ -82,7 +82,7 @@ impl<'a> Handler<'a> for HoverGenerator<'a> {
             .map_or_else(
                 || Rc::from(""),
                 |parent| match &parent.kind {
-                    qsc::hir::ItemKind::Namespace(namespace, _) => namespace.name.clone(),
+                    hir::ItemKind::Namespace(namespace, _) => namespace.name(),
                     _ => Rc::from(""),
                 },
             );
diff --git a/language_service/src/name_locator.rs b/language_service/src/name_locator.rs
index d0d1676b..ab1dc286 100644
--- a/language_service/src/name_locator.rs
+++ b/language_service/src/name_locator.rs
@@ -128,7 +128,7 @@ impl<'inner, 'package, T> Locator<'inner, 'package, T> {
 impl<'inner, 'package, T: Handler<'package>> Visitor<'package> for Locator<'inner, 'package, T> {
     fn visit_namespace(&mut self, namespace: &'package ast::Namespace) {
         if span_contains(namespace.span, self.offset) {
-            self.context.current_namespace = namespace.name.name.clone();
+            self.context.current_namespace = namespace.name.name();
             walk_namespace(self, namespace);
         }
     }
diff --git a/language_service/src/references.rs b/language_service/src/references.rs
index 6ec3bb6d..f2ae1dd9 100644
--- a/language_service/src/references.rs
+++ b/language_service/src/references.rs
@@ -188,7 +188,8 @@ impl<'a> ReferenceFinder<'a> {
         if self.include_declaration {
             let def_span = match &def.kind {
                 hir::ItemKind::Callable(decl) => decl.name.span,
-                hir::ItemKind::Namespace(name, _) | hir::ItemKind::Ty(name, _) => name.span,
+                hir::ItemKind::Namespace(name, _) => name.span(),
+                hir::ItemKind::Ty(name, _) => name.span,
             };
             locations.push(
                 self.location(


Test patch:
diff --git a/compiler/qsc/src/interpret/tests.rs b/compiler/qsc/src/interpret/tests.rs
index b291521e..3ecba807 100644
--- a/compiler/qsc/src/interpret/tests.rs
+++ b/compiler/qsc/src/interpret/tests.rs
@@ -1877,11 +1877,14 @@ mod given_interpreter {
             let path = Path {
                 id: NodeId::default(),
                 span: Span::default(),
-                namespace: Some(Box::new(qsc_ast::ast::Ident {
-                    id: NodeId::default(),
-                    span: Span::default(),
-                    name: ns.into(),
-                })),
+                namespace: Some(
+                    std::iter::once(qsc_ast::ast::Ident {
+                        id: NodeId::default(),
+                        span: Span::default(),
+                        name: ns.into(),
+                    })
+                    .collect(),
+                ),
                 name: Box::new(qsc_ast::ast::Ident {
                     id: NodeId::default(),
                     span: Span::default(),
diff --git a/compiler/qsc_circuit/src/operations/tests.rs b/compiler/qsc_circuit/src/operations/tests.rs
index dcbd4604..f84fcfd9 100644
--- a/compiler/qsc_circuit/src/operations/tests.rs
+++ b/compiler/qsc_circuit/src/operations/tests.rs
@@ -32,7 +32,7 @@ fn compile_one_operation(code: &str) -> (Item, String) {
     });
     let mut namespaces = unit.package.items.values().filter_map(|i| {
         if let ItemKind::Namespace(ident, _) = &i.kind {
-            Some(ident.name.clone())
+            Some(ident.clone())
         } else {
             None
         }
@@ -46,7 +46,7 @@ fn compile_one_operation(code: &str) -> (Item, String) {
     );
     (
         only_callable.clone(),
-        format!("{only_namespace}.{callable_name}"),
+        format!("{}.{callable_name}", only_namespace.name()),
     )
 }
 
diff --git a/compiler/qsc_data_structures/src/namespaces/tests.rs b/compiler/qsc_data_structures/src/namespaces/tests.rs
new file mode 100644
index 00000000..baed9abc
--- /dev/null
+++ b/compiler/qsc_data_structures/src/namespaces/tests.rs
@@ -0,0 +1,574 @@
+// Copyright (c) Microsoft Corporation.
+// Licensed under the MIT License.
+
+// allowing needless raw hashes here because we auto-update these expected outputs
+// and don't want to risk weird breakages
+
+#![allow(clippy::needless_raw_string_hashes)]
+
+use expect_test::expect;
+
+use super::*;
+
+#[allow(clippy::too_many_lines)]
+#[test]
+fn test_tree_construction() {
+    let mut root = NamespaceTreeRoot::default();
+    for i in 0..3 {
+        for j in 'a'..'d' {
+            let _ = root.insert_or_find_namespace(
+                vec![Rc::from(format!("ns{i}")), Rc::from(format!("ns{j}"))].into_iter(),
+            );
+        }
+    }
+    expect![[r#"
+        NamespaceTreeRoot {
+            assigner: 18,
+            tree: RefCell {
+                value: NamespaceTreeNode {
+                    children: {
+                        "ns1": RefCell {
+                            value: NamespaceTreeNode {
+                                children: {
+                                    "nsc": RefCell {
+                                        value: NamespaceTreeNode {
+                                            children: {},
+                                            id: NamespaceId(
+                                                14,
+                                            ),
+                                        },
+                                    },
+                                    "nsb": RefCell {
+                                        value: NamespaceTreeNode {
+                                            children: {},
+                                            id: NamespaceId(
+                                                13,
+                                            ),
+                                        },
+                                    },
+                                    "nsa": RefCell {
+                                        value: NamespaceTreeNode {
+                                            children: {},
+                                            id: NamespaceId(
+                                                12,
+                                            ),
+                                        },
+                                    },
+                                },
+                                id: NamespaceId(
+                                    11,
+                                ),
+                            },
+                        },
+                        "ns0": RefCell {
+                            value: NamespaceTreeNode {
+                                children: {
+                                    "nsc": RefCell {
+                                        value: NamespaceTreeNode {
+                                            children: {},
+                                            id: NamespaceId(
+                                                10,
+                                            ),
+                                        },
+                                    },
+                                    "nsb": RefCell {
+                                        value: NamespaceTreeNode {
+                                            children: {},
+                                            id: NamespaceId(
+                                                9,
+                                            ),
+                                        },
+                                    },
+                                    "nsa": RefCell {
+                                        value: NamespaceTreeNode {
+                                            children: {},
+                                            id: NamespaceId(
+                                                8,
+                                            ),
+                                        },
+                                    },
+                                },
+                                id: NamespaceId(
+                                    7,
+                                ),
+                            },
+                        },
+                        "Microsoft": RefCell {
+                            value: NamespaceTreeNode {
+                                children: {
+                                    "Quantum": RefCell {
+                                        value: NamespaceTreeNode {
+                                            children: {
+                                                "Canon": RefCell {
+                                                    value: NamespaceTreeNode {
+                                                        children: {},
+                                                        id: NamespaceId(
+                                                            3,
+                                                        ),
+                                                    },
+                                                },
+                                                "Measurement": RefCell {
+                                                    value: NamespaceTreeNode {
+                                                        children: {},
+                                                        id: NamespaceId(
+                                                            6,
+                                                        ),
+                                                    },
+                                                },
+                                                "Core": RefCell {
+                                                    value: NamespaceTreeNode {
+                                                        children: {},
+                                                        id: NamespaceId(
+                                                            4,
+                                                        ),
+                                                    },
+                                                },
+                                                "Intrinsic": RefCell {
+                                                    value: NamespaceTreeNode {
+                                                        children: {},
+                                                        id: NamespaceId(
+                                                            5,
+                                                        ),
+                                                    },
+                                                },
+                                            },
+                                            id: NamespaceId(
+                                                2,
+                                            ),
+                                        },
+                                    },
+                                },
+                                id: NamespaceId(
+                                    1,
+                                ),
+                            },
+                        },
+                        "ns2": RefCell {
+                            value: NamespaceTreeNode {
+                                children: {
+                                    "nsc": RefCell {
+                                        value: NamespaceTreeNode {
+                                            children: {},
+                                            id: NamespaceId(
+                                                18,
+                                            ),
+                                        },
+                                    },
+                                    "nsb": RefCell {
+                                        value: NamespaceTreeNode {
+                                            children: {},
+                                            id: NamespaceId(
+                                                17,
+                                            ),
+                                        },
+                                    },
+                                    "nsa": RefCell {
+                                        value: NamespaceTreeNode {
+                                            children: {},
+                                            id: NamespaceId(
+                                                16,
+                                            ),
+                                        },
+                                    },
+                                },
+                                id: NamespaceId(
+                                    15,
+                                ),
+                            },
+                        },
+                    },
+                    id: NamespaceId(
+                        0,
+                    ),
+                },
+            },
+            memo: RefCell {
+                value: {},
+            },
+        }
+    "#]]
+    .assert_debug_eq(&root);
+}
+
+#[allow(clippy::too_many_lines)]
+#[test]
+fn test_find_id() {
+    let mut root = NamespaceTreeRoot::default();
+    let mut id_buf = vec![];
+    for i in 0..3 {
+        for j in 'a'..'d' {
+            id_buf.push(root.insert_or_find_namespace(
+                vec![Rc::from(format!("ns{i}")), Rc::from(format!("ns{j}"))].into_iter(),
+            ));
+        }
+        id_buf.push(root.insert_or_find_namespace(vec![Rc::from(format!("ns{i}"))].into_iter()));
+    }
+    let mut result_buf = vec![];
+    for id in id_buf {
+        result_buf.push(root.find_namespace_by_id(&id));
+    }
+    expect![[r#"
+        [
+            (
+                [
+                    "ns0",
+                    "nsa",
+                ],
+                RefCell {
+                    value: NamespaceTreeNode {
+                        children: {},
+                        id: NamespaceId(
+                            8,
+                        ),
+                    },
+                },
+            ),
+            (
+                [
+                    "ns0",
+                    "nsb",
+                ],
+                RefCell {
+                    value: NamespaceTreeNode {
+                        children: {},
+                        id: NamespaceId(
+                            9,
+                        ),
+                    },
+                },
+            ),
+            (
+                [
+                    "ns0",
+                    "nsc",
+                ],
+                RefCell {
+                    value: NamespaceTreeNode {
+                        children: {},
+                        id: NamespaceId(
+                            10,
+                        ),
+                    },
+                },
+            ),
+            (
+                [
+                    "ns0",
+                ],
+                RefCell {
+                    value: NamespaceTreeNode {
+                        children: {
+                            "nsc": RefCell {
+                                value: NamespaceTreeNode {
+                                    children: {},
+                                    id: NamespaceId(
+                                        10,
+                                    ),
+                                },
+                            },
+                            "nsb": RefCell {
+                                value: NamespaceTreeNode {
+                                    children: {},
+                                    id: NamespaceId(
+                                        9,
+                                    ),
+                                },
+                            },
+                            "nsa": RefCell {
+                                value: NamespaceTreeNode {
+                                    children: {},
+                                    id: NamespaceId(
+                                        8,
+                                    ),
+                                },
+                            },
+                        },
+                        id: NamespaceId(
+                            7,
+                        ),
+                    },
+                },
+            ),
+            (
+                [
+                    "ns1",
+                    "nsa",
+                ],
+                RefCell {
+                    value: NamespaceTreeNode {
+                        children: {},
+                        id: NamespaceId(
+                            12,
+                        ),
+                    },
+                },
+            ),
+            (
+                [
+                    "ns1",
+                    "nsb",
+                ],
+                RefCell {
+                    value: NamespaceTreeNode {
+                        children: {},
+                        id: NamespaceId(
+                            13,
+                        ),
+                    },
+                },
+            ),
+            (
+                [
+                    "ns1",
+                    "nsc",
+                ],
+                RefCell {
+                    value: NamespaceTreeNode {
+                        children: {},
+                        id: NamespaceId(
+                            14,
+                        ),
+                    },
+                },
+            ),
+            (
+                [
+                    "ns1",
+                ],
+                RefCell {
+                    value: NamespaceTreeNode {
+                        children: {
+                            "nsc": RefCell {
+                                value: NamespaceTreeNode {
+                                    children: {},
+                                    id: NamespaceId(
+                                        14,
+                                    ),
+                                },
+                            },
+                            "nsb": RefCell {
+                                value: NamespaceTreeNode {
+                                    children: {},
+                                    id: NamespaceId(
+                                        13,
+                                    ),
+                                },
+                            },
+                            "nsa": RefCell {
+                                value: NamespaceTreeNode {
+                                    children: {},
+                                    id: NamespaceId(
+                                        12,
+                                    ),
+                                },
+                            },
+                        },
+                        id: NamespaceId(
+                            11,
+                        ),
+                    },
+                },
+            ),
+            (
+                [
+                    "ns2",
+                    "nsa",
+                ],
+                RefCell {
+                    value: NamespaceTreeNode {
+                        children: {},
+                        id: NamespaceId(
+                            16,
+                        ),
+                    },
+                },
+            ),
+            (
+                [
+                    "ns2",
+                    "nsb",
+                ],
+                RefCell {
+                    value: NamespaceTreeNode {
+                        children: {},
+                        id: NamespaceId(
+                            17,
+                        ),
+                    },
+                },
+            ),
+            (
+                [
+                    "ns2",
+                    "nsc",
+                ],
+                RefCell {
+                    value: NamespaceTreeNode {
+                        children: {},
+                        id: NamespaceId(
+                            18,
+                        ),
+                    },
+                },
+            ),
+            (
+                [
+                    "ns2",
+                ],
+                RefCell {
+                    value: NamespaceTreeNode {
+                        children: {
+                            "nsc": RefCell {
+                                value: NamespaceTreeNode {
+                                    children: {},
+                                    id: NamespaceId(
+                                        18,
+                                    ),
+                                },
+                            },
+                            "nsb": RefCell {
+                                value: NamespaceTreeNode {
+                                    children: {},
+                                    id: NamespaceId(
+                                        17,
+                                    ),
+                                },
+                            },
+                            "nsa": RefCell {
+                                value: NamespaceTreeNode {
+                                    children: {},
+                                    id: NamespaceId(
+                                        16,
+                                    ),
+                                },
+                            },
+                        },
+                        id: NamespaceId(
+                            15,
+                        ),
+                    },
+                },
+            ),
+        ]
+    "#]]
+    .assert_debug_eq(&result_buf);
+}
+// test that after inserting lots of namespaces, all ids are unique and sequential
+#[test]
+fn test_insert_or_find_namespace() {
+    let mut root = NamespaceTreeRoot::default();
+    let mut ids: Vec<usize> = vec![];
+    for i in 0..3 {
+        for j in 'a'..'d' {
+            let id = root.insert_or_find_namespace(
+                vec![Rc::from(format!("ns{i}")), Rc::from(format!("ns{j}"))].into_iter(),
+            );
+            ids.push(id.into());
+        }
+    }
+    let mut ids_sorted = ids.clone();
+    ids_sorted.sort_unstable();
+    ids_sorted.dedup();
+    // there should be no duplicate or out-of-order ids
+    assert_eq!(ids_sorted, ids);
+    expect![[r"
+        [
+            8,
+            9,
+            10,
+            12,
+            13,
+            14,
+            16,
+            17,
+            18,
+        ]
+    "]]
+    .assert_debug_eq(&ids);
+}
+
+// test for get_namespace_id
+#[test]
+fn test_get_namespace_id() {
+    let mut root = NamespaceTreeRoot::default();
+    let mut names_to_query_buf = vec![];
+    for i in 0..3 {
+        for j in 'a'..'d' {
+            let name = vec![Rc::from(format!("ns{i}")), Rc::from(format!("ns{j}"))];
+            let _ = root.insert_or_find_namespace(name.clone());
+            names_to_query_buf.push(name);
+        }
+        let name = vec![Rc::from(format!("ns{i}"))];
+        let _ = root.insert_or_find_namespace(name.clone());
+        names_to_query_buf.push(name);
+    }
+    let mut result_buf = vec![];
+    for name in names_to_query_buf {
+        result_buf.push(root.get_namespace_id(name.iter().map(|x| &**x)));
+    }
+    expect![[r#"
+        [
+            Some(
+                NamespaceId(
+                    8,
+                ),
+            ),
+            Some(
+                NamespaceId(
+                    9,
+                ),
+            ),
+            Some(
+                NamespaceId(
+                    10,
+                ),
+            ),
+            Some(
+                NamespaceId(
+                    7,
+                ),
+            ),
+            Some(
+                NamespaceId(
+                    12,
+                ),
+            ),
+            Some(
+                NamespaceId(
+                    13,
+                ),
+            ),
+            Some(
+                NamespaceId(
+                    14,
+                ),
+            ),
+            Some(
+                NamespaceId(
+                    11,
+                ),
+            ),
+            Some(
+                NamespaceId(
+                    16,
+                ),
+            ),
+            Some(
+                NamespaceId(
+                    17,
+                ),
+            ),
+            Some(
+                NamespaceId(
+                    18,
+                ),
+            ),
+            Some(
+                NamespaceId(
+                    15,
+                ),
+            ),
+        ]
+    "#]]
+    .assert_debug_eq(&result_buf);
+}
diff --git a/compiler/qsc_frontend/src/compile/tests.rs b/compiler/qsc_frontend/src/compile/tests.rs
index 32c611a4..81a30350 100644
--- a/compiler/qsc_frontend/src/compile/tests.rs
+++ b/compiler/qsc_frontend/src/compile/tests.rs
@@ -3,9 +3,9 @@
 
 #![allow(clippy::needless_raw_string_hashes)]
 
+use super::{compile, CompileUnit, Error, PackageStore, SourceMap};
 use crate::compile::TargetCapabilityFlags;
 
-use super::{compile, CompileUnit, Error, PackageStore, SourceMap};
 use expect_test::expect;
 use indoc::indoc;
 use miette::Diagnostic;
@@ -339,9 +339,13 @@ fn insert_core_call() {
 
     impl MutVisitor for Inserter<'_> {
         fn visit_block(&mut self, block: &mut Block) {
+            let ns = self
+                .core
+                .find_namespace(["QIR", "Runtime"].iter().copied())
+                .expect("QIR runtime should be inserted at instantiation of core Table");
             let allocate = self
                 .core
-                .resolve_term("QIR.Runtime", "__quantum__rt__qubit_allocate")
+                .resolve_term(ns, "__quantum__rt__qubit_allocate")
                 .expect("qubit allocation should be in core");
             let allocate_ty = allocate
                 .scheme
@@ -1255,3 +1259,35 @@ fn accept_use_qubit_block_syntax_if_preview_feature_is_off() {
     );
     assert!(unit.errors.is_empty(), "{:#?}", unit.errors);
 }
+
+#[test]
+fn hierarchical_namespace_basic() {
+    let lib_sources = SourceMap::new(
+        [(
+            "lib".into(),
+            indoc! {"
+                namespace Foo.Bar {
+                    operation Baz() : Unit {}
+                }
+                namespace Main {
+                    open Foo;
+                    operation Main() : Unit {
+                        Bar.Baz();
+                    }
+                }
+            "}
+            .into(),
+        )],
+        None,
+    );
+
+    let store = PackageStore::new(super::core());
+    let lib = compile(
+        &store,
+        &[],
+        lib_sources,
+        TargetCapabilityFlags::all(),
+        LanguageFeatures::default(),
+    );
+    assert!(lib.errors.is_empty(), "{:#?}", lib.errors);
+}
diff --git a/compiler/qsc_frontend/src/incremental/tests.rs b/compiler/qsc_frontend/src/incremental/tests.rs
index ac077e60..44d906e7 100644
--- a/compiler/qsc_frontend/src/incremental/tests.rs
+++ b/compiler/qsc_frontend/src/incremental/tests.rs
@@ -43,7 +43,7 @@ fn one_callable() {
                             output: Type 7 [35-39]: Path: Path 8 [35-39] (Ident 9 [35-39] "Unit")
                             body: Block: Block 10 [40-42]: <empty>
             names:
-            node_id:2,node_id:5,node_id:8,
+            node_id:1,node_id:5,node_id:8,
             terms:
             node_id:6,node_id:10,
             locals:
@@ -67,9 +67,25 @@ fn one_callable() {
                             hi: 44,
                         },
                         kind: Namespace(
-                            "Foo",
+                            NamespaceId(
+                                9,
+                            ),
                         ),
-                        opens: {},
+                        opens: {
+                            [
+                                "Foo",
+                            ]: [
+                                Open {
+                                    namespace: NamespaceId(
+                                        9,
+                                    ),
+                                    span: Span {
+                                        lo: 10,
+                                        hi: 13,
+                                    },
+                                },
+                            ],
+                        },
                         tys: {},
                         terms: {},
                         vars: {},
diff --git a/compiler/qsc_frontend/src/resolve/tests.rs b/compiler/qsc_frontend/src/resolve/tests.rs
index 34222770..0666dae2 100644
--- a/compiler/qsc_frontend/src/resolve/tests.rs
+++ b/compiler/qsc_frontend/src/resolve/tests.rs
@@ -10,42 +10,73 @@ use crate::{
 };
 use expect_test::{expect, Expect};
 use indoc::indoc;
+use qsc_ast::ast::{Idents, Item, ItemKind};
 use qsc_ast::{
     assigner::Assigner as AstAssigner,
     ast::{Ident, NodeId, Package, Path, TopLevelNode},
     mut_visit::MutVisitor,
     visit::{self, Visitor},
 };
+
 use qsc_data_structures::{
-    language_features::LanguageFeatures, span::Span, target::TargetCapabilityFlags,
+    language_features::LanguageFeatures,
+    namespaces::{NamespaceId, NamespaceTreeRoot},
+    span::Span,
+    target::TargetCapabilityFlags,
 };
 use qsc_hir::assigner::Assigner as HirAssigner;
+use rustc_hash::FxHashMap;
 use std::fmt::Write;
+use std::rc::Rc;
+
+enum Change {
+    Res(Res),
+    NamespaceId(NamespaceId),
+}
+
+impl From<Res> for Change {
+    fn from(res: Res) -> Self {
+        Self::Res(res)
+    }
+}
+
+impl From<NamespaceId> for Change {
+    fn from(ns_id: NamespaceId) -> Self {
+        Self::NamespaceId(ns_id)
+    }
+}
 
 struct Renamer<'a> {
     names: &'a Names,
-    changes: Vec<(Span, Res)>,
+    changes: Vec<(Span, Change)>,
+    namespaces: NamespaceTreeRoot,
+    aliases: FxHashMap<Vec<std::rc::Rc<str>>, NamespaceId>,
 }
 
 impl<'a> Renamer<'a> {
-    fn new(names: &'a Names) -> Self {
+    fn new(names: &'a Names, namespaces: NamespaceTreeRoot) -> Self {
         Self {
             names,
             changes: Vec::new(),
+            namespaces,
+            aliases: FxHashMap::default(),
         }
     }
 
     fn rename(&self, input: &mut String) {
-        for (span, res) in self.changes.iter().rev() {
-            let name = match res {
-                Res::Item(item, _) => match item.package {
-                    None => format!("item{}", item.item),
-                    Some(package) => format!("package{package}_item{}", item.item),
+        for (span, change) in self.changes.iter().rev() {
+            let name = match change {
+                Change::Res(res) => match res {
+                    Res::Item(item, _) => match item.package {
+                        None => format!("item{}", item.item),
+                        Some(package) => format!("package{package}_item{}", item.item),
+                    },
+                    Res::Local(node) => format!("local{node}"),
+                    Res::PrimTy(prim) => format!("{prim:?}"),
+                    Res::UnitTy => "Unit".to_string(),
+                    Res::Param(id) => format!("param{id}"),
                 },
-                Res::Local(node) => format!("local{node}"),
-                Res::PrimTy(prim) => format!("{prim:?}"),
-                Res::UnitTy => "Unit".to_string(),
-                Res::Param(id) => format!("param{id}"),
+                Change::NamespaceId(ns_id) => format!("namespace{}", Into::<usize>::into(ns_id)),
             };
             input.replace_range((span.lo as usize)..(span.hi as usize), &name);
         }
@@ -55,7 +86,7 @@ impl<'a> Renamer<'a> {
 impl Visitor<'_> for Renamer<'_> {
     fn visit_path(&mut self, path: &Path) {
         if let Some(&id) = self.names.get(path.id) {
-            self.changes.push((path.span, id));
+            self.changes.push((path.span, id.into()));
         } else {
             visit::walk_path(self, path);
         }
@@ -63,9 +94,34 @@ impl Visitor<'_> for Renamer<'_> {
 
     fn visit_ident(&mut self, ident: &Ident) {
         if let Some(&id) = self.names.get(ident.id) {
-            self.changes.push((ident.span, id));
+            self.changes.push((ident.span, id.into()));
         }
     }
+
+    fn visit_item(&mut self, item: &'_ Item) {
+        if let ItemKind::Open(namespace, Some(alias)) = &*item.kind {
+            let Some(ns_id) = self.namespaces.get_namespace_id(namespace.str_iter()) else {
+                return;
+            };
+            self.aliases.insert(vec![alias.name.clone()], ns_id);
+        }
+        visit::walk_item(self, item);
+    }
+
+    fn visit_idents(&mut self, vec_ident: &Idents) {
+        let ns_id = match self.namespaces.get_namespace_id(vec_ident.str_iter()) {
+            Some(x) => x,
+            None => match self
+                .aliases
+                .get(&(Into::<Vec<Rc<str>>>::into(vec_ident)))
+                .copied()
+            {
+                Some(x) => x,
+                None => return,
+            },
+        };
+        self.changes.push((vec_ident.span(), ns_id.into()));
+    }
 }
 
 fn check(input: &str, expect: &Expect) {
@@ -73,8 +129,8 @@ fn check(input: &str, expect: &Expect) {
 }
 
 fn resolve_names(input: &str) -> String {
-    let (package, names, _, errors) = compile(input, LanguageFeatures::default());
-    let mut renamer = Renamer::new(&names);
+    let (package, names, _, errors, namespaces) = compile(input, LanguageFeatures::default());
+    let mut renamer = Renamer::new(&names, namespaces);
     renamer.visit_package(&package);
     let mut output = input.to_string();
     renamer.rename(&mut output);
@@ -90,7 +146,7 @@ fn resolve_names(input: &str) -> String {
 fn compile(
     input: &str,
     language_features: LanguageFeatures,
-) -> (Package, Names, Locals, Vec<Error>) {
+) -> (Package, Names, Locals, Vec<Error>, NamespaceTreeRoot) {
     let (namespaces, parse_errors) = qsc_parse::namespaces(input, language_features);
     assert!(parse_errors.is_empty(), "parse failed: {parse_errors:#?}");
     let mut package = Package {
@@ -114,9 +170,9 @@ fn compile(
     let mut errors = globals.add_local_package(&mut assigner, &package);
     let mut resolver = Resolver::new(globals, dropped_names);
     resolver.with(&mut assigner).visit_package(&package);
-    let (names, locals, mut resolve_errors) = resolver.into_result();
+    let (names, locals, mut resolve_errors, namespaces) = resolver.into_result();
     errors.append(&mut resolve_errors);
-    (package, names, locals, errors)
+    (package, names, locals, errors, namespaces)
 }
 
 #[test]
@@ -132,7 +188,7 @@ fn global_callable() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {}
 
                 function item2() : Unit {
@@ -154,7 +210,7 @@ fn global_callable_recursive() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {
                     item1();
                 }
@@ -176,7 +232,7 @@ fn global_callable_internal() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 internal function item1() : Unit {}
 
                 function item2() : Unit {
@@ -197,7 +253,7 @@ fn global_callable_duplicate_error() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {}
                 operation item2() : Unit {}
             }
@@ -222,11 +278,11 @@ fn global_path() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {}
             }
 
-            namespace item2 {
+            namespace namespace8 {
                 function item3() : Unit {
                     item1();
                 }
@@ -252,12 +308,12 @@ fn open_namespace() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {}
             }
 
-            namespace item2 {
-                open Foo;
+            namespace namespace8 {
+                open namespace7;
 
                 function item3() : Unit {
                     item1();
@@ -284,12 +340,12 @@ fn open_alias() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {}
             }
 
-            namespace item2 {
-                open Foo as F;
+            namespace namespace8 {
+                open namespace7 as F;
 
                 function item3() : Unit {
                     item1();
@@ -314,11 +370,11 @@ fn prelude_callable() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace4 {
                 function item1() : Unit {}
             }
 
-            namespace item2 {
+            namespace namespace7 {
                 function item3() : Unit {
                     item1();
                 }
@@ -344,11 +400,11 @@ fn parent_namespace_shadows_prelude() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace4 {
                 function item1() : Unit {}
             }
 
-            namespace item2 {
+            namespace namespace7 {
                 function item3() : Unit {}
 
                 function item4() : Unit {
@@ -380,16 +436,16 @@ fn open_shadows_prelude() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace4 {
                 function item1() : Unit {}
             }
 
-            namespace item2 {
+            namespace namespace7 {
                 function item3() : Unit {}
             }
 
-            namespace item4 {
-                open Foo;
+            namespace namespace8 {
+                open namespace7;
 
                 function item5() : Unit {
                     item3();
@@ -418,15 +474,15 @@ fn ambiguous_prelude() {
         }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace3 {
                 function item1() : Unit {}
             }
 
-            namespace item2 {
+            namespace namespace4 {
                 function item3() : Unit {}
             }
 
-            namespace item4 {
+            namespace namespace7 {
                 function item5() : Unit {
                     A();
                 }
@@ -449,7 +505,7 @@ fn local_var() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Int {
                     let local13 = 0;
                     local13
@@ -475,7 +531,7 @@ fn shadow_local() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Int {
                     let local13 = 0;
                     let local17 = {
@@ -500,7 +556,7 @@ fn callable_param() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1(local8 : Int) : Int {
                     local8
                 }
@@ -522,7 +578,7 @@ fn spec_param() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 operation item1(local8 : Qubit) : (Qubit[], Qubit) {
                     controlled (local23, ...) {
                         (local23, local8)
@@ -549,7 +605,7 @@ fn spec_param_shadow_disallowed() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 operation item1(local8 : Qubit[]) : Qubit[] {
                     controlled (local20, ...) {
                         local20
@@ -580,7 +636,7 @@ fn local_shadows_global() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {}
 
                 function item2() : Int {
@@ -606,7 +662,7 @@ fn shadow_same_block() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Int {
                     let local13 = 0;
                     let local17 = local13 + 1;
@@ -636,12 +692,12 @@ fn parent_namespace_shadows_open() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {}
             }
 
-            namespace item2 {
-                open Foo;
+            namespace namespace8 {
+                open namespace7;
 
                 function item3() : Unit {}
 
@@ -674,16 +730,16 @@ fn open_alias_shadows_global() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {}
             }
 
-            namespace item2 {
+            namespace namespace8 {
                 function item3() : Unit {}
             }
 
-            namespace item4 {
-                open Foo as Bar;
+            namespace namespace9 {
+                open namespace7 as Bar;
 
                 function item5() : Unit {
                     item1();
@@ -702,7 +758,7 @@ fn shadowing_disallowed_within_parameters() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 operation item1(local8: Int, local13: Double, local18: Bool) : Unit {}
             }
 
@@ -722,7 +778,7 @@ fn shadowing_disallowed_within_local_binding() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 operation item1() : Unit {
                     let (local14, local16, local18) = (1, 2, 3);
                 }
@@ -744,7 +800,7 @@ fn shadowing_disallowed_within_for_loop() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 operation item1() : Unit {
                     for (local15, local17, local19) in [(1, 1, 1)] {}
                 }
@@ -766,7 +822,7 @@ fn shadowing_disallowed_within_lambda_param() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 operation item1() : Unit {
                     let local13 = (local17, local19, local21) -> local21 + local19 + 1;
                 }
@@ -800,17 +856,17 @@ fn merged_aliases() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {}
             }
 
-            namespace item2 {
+            namespace namespace8 {
                 function item3() : Unit {}
             }
 
-            namespace item4 {
-                open Foo as Alias;
-                open Bar as Alias;
+            namespace namespace9 {
+                open namespace7 as Alias;
+                open namespace8 as Alias;
 
                 function item5() : Unit {
                     item1();
@@ -831,7 +887,7 @@ fn ty_decl() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 newtype item1 = Unit;
                 function item2(local14 : item1) : Unit {}
             }
@@ -849,7 +905,7 @@ fn ty_decl_duplicate_error() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 newtype item1 = Unit;
                 newtype item2 = Bool;
             }
@@ -868,7 +924,7 @@ fn ty_decl_duplicate_error_on_built_in_ty() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace4 {
                 newtype item1 = Unit;
             }
 
@@ -887,7 +943,7 @@ fn ty_decl_in_ty_decl() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 newtype item1 = Unit;
                 newtype item2 = item1;
             }
@@ -904,7 +960,7 @@ fn ty_decl_recursive() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 newtype item1 = item1;
             }
         "#]],
@@ -924,7 +980,7 @@ fn ty_decl_cons() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 newtype item1 = Unit;
 
                 function item2() : item1 {
@@ -946,7 +1002,7 @@ fn unknown_term() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {
                     B();
                 }
@@ -966,7 +1022,7 @@ fn unknown_ty() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1(local8 : B) : Unit {}
             }
 
@@ -997,17 +1053,17 @@ fn open_ambiguous_terms() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {}
             }
 
-            namespace item2 {
+            namespace namespace8 {
                 function item3() : Unit {}
             }
 
-            namespace item4 {
-                open Foo;
-                open Bar;
+            namespace namespace9 {
+                open namespace7;
+                open namespace8;
 
                 function item5() : Unit {
                     A();
@@ -1039,17 +1095,17 @@ fn open_ambiguous_tys() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 newtype item1 = Unit;
             }
 
-            namespace item2 {
+            namespace namespace8 {
                 newtype item3 = Unit;
             }
 
-            namespace item4 {
-                open Foo;
-                open Bar;
+            namespace namespace9 {
+                open namespace7;
+                open namespace8;
 
                 function item5(local28 : A) : Unit {}
             }
@@ -1081,20 +1137,20 @@ fn merged_aliases_ambiguous_terms() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {}
             }
 
-            namespace item2 {
+            namespace namespace8 {
                 function item3() : Unit {}
             }
 
-            namespace item4 {
-                open Foo as Alias;
-                open Bar as Alias;
+            namespace namespace9 {
+                open namespace7 as Alias;
+                open namespace8 as Alias;
 
                 function item5() : Unit {
-                    Alias.A();
+                    namespace8.A();
                 }
             }
 
@@ -1123,19 +1179,19 @@ fn merged_aliases_ambiguous_tys() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 newtype item1 = Unit;
             }
 
-            namespace item2 {
+            namespace namespace8 {
                 newtype item3 = Unit;
             }
 
-            namespace item4 {
-                open Foo as Alias;
-                open Bar as Alias;
+            namespace namespace9 {
+                open namespace7 as Alias;
+                open namespace8 as Alias;
 
-                function item5(local30 : Alias.A) : Unit {}
+                function item5(local30 : namespace8.A) : Unit {}
             }
 
             // Ambiguous { name: "A", first_open: "Foo", second_open: "Bar", name_span: Span { lo: 170, hi: 171 }, first_open_span: Span { lo: 107, hi: 110 }, second_open_span: Span { lo: 130, hi: 133 } }
@@ -1154,7 +1210,7 @@ fn lambda_param() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {
                     let local13 = local16 -> local16 + 1;
                 }
@@ -1176,7 +1232,7 @@ fn lambda_shadows_local() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Int {
                     let local13 = 1;
                     let local17 = local20 -> local20 + 1;
@@ -1200,7 +1256,7 @@ fn for_loop_range() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {
                     for local14 in 0..9 {
                         let _ = local14;
@@ -1224,7 +1280,7 @@ fn for_loop_var() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1(local8 : Int[]) : Unit {
                     for local20 in local8 {
                         let _ = local20;
@@ -1249,7 +1305,7 @@ fn repeat_until() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 operation item1() : Unit {
                     mutable local13 = false;
                     repeat {
@@ -1278,7 +1334,7 @@ fn repeat_until_fixup() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 operation item1() : Unit {
                     mutable local13 = false;
                     repeat {
@@ -1309,7 +1365,7 @@ fn repeat_until_fixup_scoping() {
             }
         }"},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 operation item1() : Unit {
                     repeat {
                         mutable local16 = false;
@@ -1341,7 +1397,7 @@ fn use_qubit() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 operation item1(local8 : Qubit) : Unit {
                     body intrinsic;
                 }
@@ -1370,7 +1426,7 @@ fn use_qubit_block() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 operation item1(local8 : Qubit) : Unit {
                     body intrinsic;
                 }
@@ -1401,7 +1457,7 @@ fn use_qubit_block_qubit_restricted_to_block_scope() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 operation item1(local8 : Qubit) : Unit {
                     body intrinsic;
                 }
@@ -1430,7 +1486,7 @@ fn local_function() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Int {
                     function item2() : Int { 2 }
                     item2() + 1
@@ -1452,7 +1508,7 @@ fn local_function_use_before_declare() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : () {
                     item2();
                     function item2() : () {}
@@ -1476,7 +1532,7 @@ fn local_function_is_really_local() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : () {
                     function item3() : () {}
                     item3();
@@ -1502,7 +1558,7 @@ fn local_function_is_not_closure() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : () {
                     let local11 = 2;
                     function item2() : Int { x }
@@ -1526,7 +1582,7 @@ fn local_type() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : () {
                     newtype item2 = Int;
                     let local18 = item2(5);
@@ -1544,8 +1600,8 @@ fn local_open() {
             namespace B { function Bar() : () {} }
         "},
         &expect![[r#"
-            namespace item0 { function item1() : () { open B; item3(); } }
-            namespace item2 { function item3() : () {} }
+            namespace namespace7 { function item1() : () { open namespace8; item3(); } }
+            namespace namespace8 { function item3() : () {} }
         "#]],
     );
 }
@@ -1562,12 +1618,12 @@ fn local_open_shadows_parent_item() {
             namespace B { function Bar() : () {} }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : () {}
-                function item2() : () { open B; item4(); }
+                function item2() : () { open namespace8; item4(); }
             }
 
-            namespace item3 { function item4() : () {} }
+            namespace namespace8 { function item4() : () {} }
         "#]],
     );
 }
@@ -1585,13 +1641,13 @@ fn local_open_shadows_parent_open() {
             namespace C { function Bar() : () {} }
         "},
         &expect![[r#"
-            namespace item0 {
-                open B;
-                function item1() : () { open C; item5(); }
+            namespace namespace7 {
+                open namespace8;
+                function item1() : () { open namespace9; item5(); }
             }
 
-            namespace item2 { function item3() : () {} }
-            namespace item4 { function item5() : () {} }
+            namespace namespace8 { function item3() : () {} }
+            namespace namespace9 { function item5() : () {} }
         "#]],
     );
 }
@@ -1609,7 +1665,7 @@ fn update_array_index_var() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : () {
                     let local11 = [2];
                     let local16 = 0;
@@ -1633,7 +1689,7 @@ fn update_array_index_expr() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : () {
                     let local11 = [2];
                     let local16 = 0;
@@ -1658,7 +1714,7 @@ fn update_udt_known_field_name() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 newtype item1 = (First : Int, Second : Int);
 
                 function item2() : () {
@@ -1684,7 +1740,7 @@ fn update_udt_known_field_name_expr() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 newtype item1 = (First : Int, Second : Int);
 
                 function item2() : () {
@@ -1712,7 +1768,7 @@ fn update_udt_unknown_field_name() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 newtype item1 = (First : Int, Second : Int);
 
                 function item2() : () {
@@ -1740,7 +1796,7 @@ fn update_udt_unknown_field_name_known_global() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 newtype item1 = (First : Int, Second : Int);
 
                 function item2() : () {}
@@ -1763,7 +1819,7 @@ fn unknown_namespace() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 open Microsoft.Quantum.Fake;
             }
 
@@ -1783,11 +1839,11 @@ fn empty_namespace_works() {
             namespace B {}
         "},
         &expect![[r#"
-            namespace item0 {
-                open B;
+            namespace namespace7 {
+                open namespace8;
                 function item1(): Unit{}
             }
-            namespace item2 {}
+            namespace namespace8 {}
         "#]],
     );
 }
@@ -1810,14 +1866,14 @@ fn cyclic_namespace_dependency_supported() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
-                open B;
+            namespace namespace7 {
+                open namespace8;
                 operation item1() : Unit {
                     item3();
                 }
             }
-            namespace item2 {
-                open A;
+            namespace namespace8 {
+                open namespace7;
                 operation item3() : Unit {
                     item1();
                 }
@@ -1842,7 +1898,7 @@ fn bind_items_in_repeat() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 operation item1() : Unit {
                     repeat {
                         function item2() : Unit {}
@@ -1869,7 +1925,7 @@ fn bind_items_in_qubit_use_block() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 operation item1() : Unit {
                     use local13 = Qubit() {
                         function item2() : Unit {}
@@ -1894,7 +1950,7 @@ fn use_bound_item_in_another_bound_item() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {
                     function item2() : Unit {
                         item3();
@@ -1917,7 +1973,7 @@ fn use_unbound_generic() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1<param0>(local9: 'U) : 'U {
                     local9
                 }
@@ -1928,6 +1984,7 @@ fn use_unbound_generic() {
         "#]],
     );
 }
+
 #[test]
 fn resolve_local_generic() {
     check(
@@ -1939,7 +1996,7 @@ fn resolve_local_generic() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1<param0>(local9: param0) : param0 {
                     local9
                 }
@@ -1962,7 +2019,7 @@ fn dropped_callable() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 @Config(Base)
                 function Dropped() : Unit {}
 
@@ -2003,7 +2060,7 @@ fn multiple_definition_dropped_is_not_found() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 @Config(Adaptive)
                 operation item1() : Unit {}
                 @Config(Base)
@@ -2013,13 +2070,13 @@ fn multiple_definition_dropped_is_not_found() {
                 @Config(Adaptive)
                 operation item2() : Unit {}
             }
-            namespace item3 {
+            namespace namespace8 {
                 operation item4() : Unit {
                     B();
                     C();
                 }
                 operation item5() : Unit {
-                    open A;
+                    open namespace7;
                     item1();
                     item2();
                 }
@@ -2047,12 +2104,12 @@ fn disallow_duplicate_intrinsic() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 operation item1() : Unit {
                     body intrinsic;
                 }
             }
-            namespace item2 {
+            namespace namespace8 {
                 operation item3() : Unit {
                     body intrinsic;
                 }
@@ -2082,15 +2139,15 @@ fn disallow_duplicate_intrinsic_and_non_intrinsic_collision() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 internal operation item1() : Unit {
                     body intrinsic;
                 }
             }
-            namespace item2 {
+            namespace namespace8 {
                 operation item3() : Unit {}
             }
-            namespace item4 {
+            namespace namespace8 {
                 operation item5() : Unit {
                     body intrinsic;
                 }
@@ -2113,7 +2170,7 @@ fn check_locals(input: &str, expect: &Expect) {
     let cursor_offset = parts[0].len() as u32;
     let source = parts.join("");
 
-    let (_, _, locals, _) = compile(&source, LanguageFeatures::default());
+    let (_, _, locals, _, _) = compile(&source, LanguageFeatures::default());
 
     let locals = locals.get_all_at_offset(cursor_offset);
     let actual = locals.iter().fold(String::new(), |mut output, l| {
@@ -2418,7 +2475,7 @@ fn use_after_scope() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {
                     {
                         let local16 = 42;
@@ -2447,7 +2504,7 @@ fn nested_function_definition() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {
                     function item2() : Unit {
                         function item3() : Unit {}
@@ -2478,7 +2535,7 @@ fn variable_in_nested_blocks() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {
                     {
                         let local16 = 10;
@@ -2511,11 +2568,11 @@ fn function_call_with_namespace_alias() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {}
             }
-            namespace item2 {
-                open Foo as F;
+            namespace namespace8 {
+                open namespace7 as F;
                 function item3() : Unit {
                     item1();
                 }
@@ -2539,7 +2596,7 @@ fn type_alias_in_function_scope() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {
                     newtype item3 = Int;
                     let local20 : item3 = item3(5);
@@ -2570,7 +2627,7 @@ fn lambda_inside_lambda() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {
                     let local13 = () -> {
                         let local20 = (local24) -> local24 + 1;
@@ -2599,10 +2656,10 @@ fn nested_namespaces_with_same_function_name() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 function item1() : Unit {}
             }
-            namespace item2 {
+            namespace namespace8 {
                 function item3() : Unit {}
                 function item4() : Unit {
                     item1();
@@ -2622,7 +2679,7 @@ fn newtype_with_invalid_field_type() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 newtype item1 = (Re: Real, Im: Imaginary); // Imaginary is not a valid type
             }
 
@@ -2645,7 +2702,7 @@ fn newtype_with_tuple_destructuring() {
             }
         "},
         &expect![[r#"
-            namespace item0 {
+            namespace namespace7 {
                 newtype item1 = (First: Int, Second: Int);
                 function item2(local21: item1) : Int {
                     let (local32, local34) = local21;
@@ -2655,3 +2712,150 @@ fn newtype_with_tuple_destructuring() {
         "#]],
     );
 }
+
+#[test]
+fn items_resolve_according_to_implicit_hierarchy() {
+    check(
+        indoc! {"
+namespace Foo {
+  @EntryPoint()
+  function Main(): Int {
+    Foo()
+  }
+
+  function Foo() : Int {
+    Bar.Baz.Quux()
+  }
+}
+
+namespace Foo.Bar.Baz {
+  function Quux() : Int { 6 }
+}
+"},
+        &expect![[r#"
+            namespace namespace7 {
+              @EntryPoint()
+              function item1(): Int {
+                item2()
+              }
+
+              function item2() : Int {
+                item4()
+              }
+            }
+
+            namespace namespace9 {
+              function item4() : Int { 6 }
+            }
+        "#]],
+    );
+}
+
+#[test]
+fn basic_hierarchical_namespace() {
+    check(
+        indoc! {"
+    namespace Foo.Bar.Baz {
+        operation Quux() : Unit {}
+    }
+    namespace A {
+        open Foo;
+        operation Main() : Unit {
+            Bar.Baz.Quux();
+        }
+    }
+    namespace B {
+        open Foo.Bar;
+        operation Main() : Unit {
+            Baz.Quux();
+        }
+    }"},
+        &expect![[r#"
+            namespace namespace9 {
+                operation item1() : Unit {}
+            }
+            namespace namespace10 {
+                open namespace7;
+                operation item3() : Unit {
+                    item1();
+                }
+            }
+            namespace namespace11 {
+                open namespace8;
+                operation item5() : Unit {
+                    item1();
+                }
+            }"#]],
+    );
+}
+
+#[test]
+fn test_katas_shadowing_use_case() {
+    check(
+        indoc! {"namespace Kata {
+    operation ApplyX() : Unit {
+        // Do nothing.
+    }
+}
+
+namespace Kata.Verification {
+    operation CheckSolution() : Bool {
+        let _ = Kata.ApplyX();
+        let _ = ApplyX();
+    }
+
+    operation ApplyX() : Unit {}
+}
+" },
+        &expect![[r#"
+            namespace namespace7 {
+                operation item1() : Unit {
+                    // Do nothing.
+                }
+            }
+
+            namespace namespace8 {
+                operation item3() : Bool {
+                    let _ = item1();
+                    let _ = item4();
+                }
+
+                operation item4() : Unit {}
+            }
+        "#]],
+    );
+}
+
+#[test]
+fn open_can_access_parent_scope() {
+    check(
+        indoc! {r#"
+namespace Foo.Bar {
+    operation Hello() : Unit {
+
+    }
+}
+
+namespace Foo {
+    open Bar;
+    @EntryPoint()
+    operation Main() : Unit {
+        Hello();
+    }
+}"#},
+        &expect![[r#"
+            namespace namespace8 {
+                operation item1() : Unit {
+
+                }
+            }
+
+            namespace namespace7 {
+                open Bar;
+                @EntryPoint()
+                operation item3() : Unit {
+                    item1();
+                }
+            }"#]],
+    );
+}
diff --git a/compiler/qsc_frontend/src/typeck/tests.rs b/compiler/qsc_frontend/src/typeck/tests.rs
index 1bc0886f..9a28600a 100644
--- a/compiler/qsc_frontend/src/typeck/tests.rs
+++ b/compiler/qsc_frontend/src/typeck/tests.rs
@@ -88,9 +88,8 @@ fn compile(input: &str, entry_expr: &str) -> (Package, super::Table, Vec<compile
     let mut errors = globals.add_local_package(&mut assigner, &package);
     let mut resolver = Resolver::new(globals, Vec::new());
     resolver.with(&mut assigner).visit_package(&package);
-    let (names, _, mut resolve_errors) = resolver.into_result();
+    let (names, _, mut resolve_errors, _namespaces) = resolver.into_result();
     errors.append(&mut resolve_errors);
-
     let mut checker = Checker::new(super::GlobalTable::new());
     checker.check_package(&names, &package);
     let (tys, ty_errors) = checker.into_table();
@@ -284,15 +283,15 @@ fn call_generic_length() {
         "},
         "Length([true, false, true])",
         &expect![[r#"
-            #7 58-69 "(xs : 'T[])" : ?
-            #8 59-68 "xs : 'T[]" : ?
-            #17 98-125 "Length([true, false, true])" : Int
-            #18 98-104 "Length" : (Bool[] -> Int)
-            #21 104-125 "([true, false, true])" : Bool[]
-            #22 105-124 "[true, false, true]" : Bool[]
-            #23 106-110 "true" : Bool
-            #24 112-117 "false" : Bool
-            #25 119-123 "true" : Bool
+            #9 58-69 "(xs : 'T[])" : ?
+            #10 59-68 "xs : 'T[]" : ?
+            #19 98-125 "Length([true, false, true])" : Int
+            #20 98-104 "Length" : (Bool[] -> Int)
+            #23 104-125 "([true, false, true])" : Bool[]
+            #24 105-124 "[true, false, true]" : Bool[]
+            #25 106-110 "true" : Bool
+            #26 112-117 "false" : Bool
+            #27 119-123 "true" : Bool
         "#]],
     );
 }
@@ -328,12 +327,12 @@ fn int_as_double_error() {
         "},
         "Microsoft.Quantum.Convert.IntAsDouble(false)",
         &expect![[r#"
-            #6 62-71 "(a : Int)" : ?
-            #7 63-70 "a : Int" : ?
-            #16 103-147 "Microsoft.Quantum.Convert.IntAsDouble(false)" : Double
-            #17 103-140 "Microsoft.Quantum.Convert.IntAsDouble" : (Int -> Double)
-            #21 140-147 "(false)" : Bool
-            #22 141-146 "false" : Bool
+            #8 62-71 "(a : Int)" : ?
+            #9 63-70 "a : Int" : ?
+            #18 103-147 "Microsoft.Quantum.Convert.IntAsDouble(false)" : Double
+            #19 103-140 "Microsoft.Quantum.Convert.IntAsDouble" : (Int -> Double)
+            #25 140-147 "(false)" : Bool
+            #26 141-146 "false" : Bool
             Error(Type(Error(TyMismatch("Int", "Bool", Span { lo: 103, hi: 147 }))))
         "#]],
     );
@@ -349,15 +348,15 @@ fn length_type_error() {
         "},
         "Length((1, 2, 3))",
         &expect![[r#"
-            #7 58-69 "(xs : 'T[])" : ?
-            #8 59-68 "xs : 'T[]" : ?
-            #17 98-115 "Length((1, 2, 3))" : Int
-            #18 98-104 "Length" : (?0[] -> Int)
-            #21 104-115 "((1, 2, 3))" : (Int, Int, Int)
-            #22 105-114 "(1, 2, 3)" : (Int, Int, Int)
-            #23 106-107 "1" : Int
-            #24 109-110 "2" : Int
-            #25 112-113 "3" : Int
+            #9 58-69 "(xs : 'T[])" : ?
+            #10 59-68 "xs : 'T[]" : ?
+            #19 98-115 "Length((1, 2, 3))" : Int
+            #20 98-104 "Length" : (?0[] -> Int)
+            #23 104-115 "((1, 2, 3))" : (Int, Int, Int)
+            #24 105-114 "(1, 2, 3)" : (Int, Int, Int)
+            #25 106-107 "1" : Int
+            #26 109-110 "2" : Int
+            #27 112-113 "3" : Int
             Error(Type(Error(TyMismatch("?[]", "(Int, Int, Int)", Span { lo: 98, hi: 115 }))))
             Error(Type(Error(AmbiguousTy(Span { lo: 98, hi: 104 }))))
         "#]],
@@ -377,18 +376,18 @@ fn single_arg_for_tuple() {
             Ry(q);
         }"},
         &expect![[r#"
-            #6 56-87 "(theta : Double, qubit : Qubit)" : (Double, Qubit)
-            #7 57-71 "theta : Double" : Double
-            #12 73-86 "qubit : Qubit" : Qubit
-            #21 106-108 "{}" : Unit
-            #22 111-146 "{\n    use q = Qubit();\n    Ry(q);\n}" : Unit
-            #23 111-146 "{\n    use q = Qubit();\n    Ry(q);\n}" : Unit
-            #25 121-122 "q" : Qubit
-            #27 125-132 "Qubit()" : Qubit
-            #29 138-143 "Ry(q)" : Unit
-            #30 138-140 "Ry" : ((Double, Qubit) => Unit is Adj + Ctl)
-            #33 140-143 "(q)" : Qubit
-            #34 141-142 "q" : Qubit
+            #8 56-87 "(theta : Double, qubit : Qubit)" : (Double, Qubit)
+            #9 57-71 "theta : Double" : Double
+            #14 73-86 "qubit : Qubit" : Qubit
+            #23 106-108 "{}" : Unit
+            #24 111-146 "{\n    use q = Qubit();\n    Ry(q);\n}" : Unit
+            #25 111-146 "{\n    use q = Qubit();\n    Ry(q);\n}" : Unit
+            #27 121-122 "q" : Qubit
+            #29 125-132 "Qubit()" : Qubit
+            #31 138-143 "Ry(q)" : Unit
+            #32 138-140 "Ry" : ((Double, Qubit) => Unit is Adj + Ctl)
+            #35 140-143 "(q)" : Qubit
+            #36 141-142 "q" : Qubit
             Error(Type(Error(TyMismatch("(Double, Qubit)", "Qubit", Span { lo: 138, hi: 143 }))))
         "#]],
     );
@@ -1700,7 +1699,7 @@ fn return_with_satisfying_specialization_succeeds() {
             }
         "},
         "",
-        &expect![[r##"
+        &expect![[r#"
             #6 32-34 "()" : Unit
             #10 42-44 "{}" : Unit
             #14 60-62 "()" : Unit
@@ -1733,7 +1732,7 @@ fn return_with_satisfying_specialization_succeeds() {
             #166 592-594 "()" : Unit
             #175 612-617 "{ E }" : (Unit => Unit)
             #177 614-615 "E" : (Unit => Unit)
-        "##]],
+        "#]],
     );
 }
 
@@ -1759,7 +1758,7 @@ fn return_with_unsatisfying_specialization_fails() {
             }
         "},
         "",
-        &expect![[r##"
+        &expect![[r#"
             #6 32-34 "()" : Unit
             #10 42-44 "{}" : Unit
             #14 60-62 "()" : Unit
@@ -1796,7 +1795,7 @@ fn return_with_unsatisfying_specialization_fails() {
             Error(Type(Error(FunctorMismatch(Value(CtlAdj), Value(Empty), Span { lo: 463, hi: 464 }))))
             Error(Type(Error(FunctorMismatch(Value(CtlAdj), Value(Adj), Span { lo: 530, hi: 531 }))))
             Error(Type(Error(FunctorMismatch(Value(CtlAdj), Value(Ctl), Span { lo: 597, hi: 598 }))))
-        "##]],
+        "#]],
     );
 }
 
@@ -3763,7 +3762,7 @@ fn lambda_on_array_where_item_used_in_call_should_be_inferred() {
             }
         "},
         "",
-        &expect![[r##"
+        &expect![[r#"
             #6 28-30 "()" : Unit
             #10 38-77 "{\n        let f = qs => C(qs[0]);\n    }" : Unit
             #12 52-53 "f" : (Qubit[] => Unit)
@@ -3778,6 +3777,6 @@ fn lambda_on_array_where_item_used_in_call_should_be_inferred() {
             #30 93-104 "(q : Qubit)" : Qubit
             #31 94-103 "q : Qubit" : Qubit
             #42 125-128 "{ }" : Unit
-        "##]],
+        "#]],
     );
 }
diff --git a/compiler/qsc_parse/src/item/tests.rs b/compiler/qsc_parse/src/item/tests.rs
index d6c1de40..abacbdaf 100644
--- a/compiler/qsc_parse/src/item/tests.rs
+++ b/compiler/qsc_parse/src/item/tests.rs
@@ -108,7 +108,7 @@ fn open_no_alias() {
         "open Foo.Bar.Baz;",
         &expect![[r#"
             Item _id_ [0-17]:
-                Open (Ident _id_ [5-16] "Foo.Bar.Baz")"#]],
+                Open ([Ident _id_ [5-8] "Foo", Ident _id_ [9-12] "Bar", Ident _id_ [13-16] "Baz"])"#]],
     );
 }
 
@@ -119,18 +119,7 @@ fn open_alias() {
         "open Foo.Bar.Baz as Baz;",
         &expect![[r#"
             Item _id_ [0-24]:
-                Open (Ident _id_ [5-16] "Foo.Bar.Baz") (Ident _id_ [20-23] "Baz")"#]],
-    );
-}
-
-#[test]
-fn open_alias_dot() {
-    check(
-        parse,
-        "open Foo.Bar.Baz as Bar.Baz;",
-        &expect![[r#"
-            Item _id_ [0-28]:
-                Open (Ident _id_ [5-16] "Foo.Bar.Baz") (Ident _id_ [20-27] "Bar.Baz")"#]],
+                Open ([Ident _id_ [5-8] "Foo", Ident _id_ [9-12] "Bar", Ident _id_ [13-16] "Baz"]) (Ident _id_ [20-23] "Baz")"#]],
     );
 }
 
@@ -1693,3 +1682,37 @@ fn namespace_with_conflicting_names() {
                         Type _id_ [87-90]: Path: Path _id_ [87-90] (Ident _id_ [87-90] "Int")"#]],
     );
 }
+
+// We technically broke this syntax as of May 2024. Although we don't think anybody was using it,
+// we want to make sure we provide a helpful error message.
+#[test]
+fn helpful_error_on_dotted_alias() {
+    check_vec(
+        parse_namespaces,
+        "namespace A {
+            open Microsoft.Quantum.Math as Foo.Bar.Baz;
+            operation Main() : Unit {}
+        }",
+        &expect![[r#"
+            Namespace _id_ [0-118] (Ident _id_ [10-11] "A"):
+                Item _id_ [26-69]:
+                    Err
+                Item _id_ [82-108]:
+                    Callable _id_ [82-108] (Operation):
+                        name: Ident _id_ [92-96] "Main"
+                        input: Pat _id_ [96-98]: Unit
+                        output: Type _id_ [101-105]: Path: Path _id_ [101-105] (Ident _id_ [101-105] "Unit")
+                        body: Block: Block _id_ [106-108]: <empty>
+
+            [
+                Error(
+                    DotIdentAlias(
+                        Span {
+                            lo: 60,
+                            hi: 61,
+                        },
+                    ),
+                ),
+            ]"#]],
+    );
+}
diff --git a/compiler/qsc_parse/src/prim/tests.rs b/compiler/qsc_parse/src/prim/tests.rs
index 04b664e8..870daee9 100644
--- a/compiler/qsc_parse/src/prim/tests.rs
+++ b/compiler/qsc_parse/src/prim/tests.rs
@@ -100,7 +100,9 @@ fn path_triple() {
     check(
         path,
         "Foo.Bar.Baz",
-        &expect![[r#"Path _id_ [0-11] (Ident _id_ [0-7] "Foo.Bar") (Ident _id_ [8-11] "Baz")"#]],
+        &expect![[
+            r#"Path _id_ [0-11] ([Ident _id_ [0-3] "Foo", Ident _id_ [4-7] "Bar"]) (Ident _id_ [8-11] "Baz")"#
+        ]],
     );
 }
 
diff --git a/compiler/qsc_partial_eval/tests/assigns.rs b/compiler/qsc_partial_eval/tests/assigns.rs
index 85b03c9b..dcf9f63f 100644
--- a/compiler/qsc_partial_eval/tests/assigns.rs
+++ b/compiler/qsc_partial_eval/tests/assigns.rs
@@ -1534,7 +1534,7 @@ fn integer_assign_mod_with_lhs_dynamic_integer_and_rhs_classical_integer() {
 }
 
 #[test]
-fn integer_assign_exp_with_lhs_classical_integer_and_rhs_dynamic_integer() {
+fn integer_assign_exp_with_lhs_classical_integer_and_rhs_dynamic_integer_raises_error() {
     let error = get_partial_evaluation_error(indoc! {
         r#"
         namespace Test {
@@ -1548,41 +1548,202 @@ fn integer_assign_exp_with_lhs_classical_integer_and_rhs_dynamic_integer() {
         }
         "#,
     });
-    // When this binary operation is supported, this error should be different.
     assert_error(
         &error,
         &expect![[
-            r#"Unimplemented("exponentiation for integer operands", Span { lo: 121, hi: 156 })"#
+            r#"Unexpected("exponent must be a classical integer", Span { lo: 121, hi: 156 })"#
         ]],
     );
 }
 
 #[test]
-fn integer_assign_exp_with_lhs_dynamic_integer_and_rhs_classical_integer() {
+fn integer_assign_exp_with_lhs_classical_integer_and_rhs_classical_negative_integer_raises_error() {
     let error = get_partial_evaluation_error(indoc! {
         r#"
         namespace Test {
             @EntryPoint()
             operation Main() : Int {
                 use q = Qubit();
-                mutable i = MResetZ(q) == Zero ? 0 | 1;
-                set i ^= 3;
+                mutable i = 0;
+                set i ^= -1;
                 i
             }
         }
         "#,
     });
-    // When this binary operation is supported, this program should not yield an error.
     assert_error(
         &error,
         &expect![[
-            r#"Unimplemented("exponentiation for integer operands", Span { lo: 146, hi: 156 })"#
+            r#"EvaluationFailed("negative integers cannot be used here: -1", Span { lo: 130, hi: 132 })"#
         ]],
     );
 }
 
 #[test]
-fn integer_assign_exp_with_lhs_dynamic_integer_and_rhs_dynamic_integer() {
+fn integer_assign_exp_with_lhs_dynamic_integer_and_rhs_classical_zero_integer() {
+    let program = get_rir_program(indoc! {
+        r#"
+        namespace Test {
+            @EntryPoint()
+            operation Main() : Int {
+                use q = Qubit();
+                mutable i = MResetZ(q) == Zero ? 0 | 1;
+                set i ^= 0;
+                i
+            }
+        }
+        "#,
+    });
+    let measurement_callable_id = CallableId(1);
+    assert_callable(
+        &program,
+        measurement_callable_id,
+        &expect![[r#"
+            Callable:
+                name: __quantum__qis__mresetz__body
+                call_type: Measurement
+                input_type:
+                    [0]: Qubit
+                    [1]: Result
+                output_type: <VOID>
+                body: <NONE>"#]],
+    );
+    let readout_callable_id = CallableId(2);
+    assert_callable(
+        &program,
+        readout_callable_id,
+        &expect![[r#"
+        Callable:
+            name: __quantum__qis__read_result__body
+            call_type: Readout
+            input_type:
+                [0]: Result
+            output_type: Boolean
+            body: <NONE>"#]],
+    );
+    let output_record_id = CallableId(3);
+    assert_callable(
+        &program,
+        output_record_id,
+        &expect![[r#"
+            Callable:
+                name: __quantum__rt__int_record_output
+                call_type: OutputRecording
+                input_type:
+                    [0]: Integer
+                    [1]: Pointer
+                output_type: <VOID>
+                body: <NONE>"#]],
+    );
+    assert_blocks(
+        &program,
+        &expect![[r#"
+            Blocks:
+            Block 0:Block:
+                Call id(1), args( Qubit(0), Result(0), )
+                Variable(0, Boolean) = Call id(2), args( Result(0), )
+                Variable(1, Boolean) = Icmp Eq, Variable(0, Boolean), Bool(false)
+                Branch Variable(1, Boolean), 2, 3
+            Block 1:Block:
+                Variable(3, Integer) = Store Variable(2, Integer)
+                Variable(4, Integer) = Store Integer(1)
+                Variable(3, Integer) = Store Variable(4, Integer)
+                Call id(3), args( Variable(3, Integer), Pointer, )
+                Return
+            Block 2:Block:
+                Variable(2, Integer) = Store Integer(0)
+                Jump(1)
+            Block 3:Block:
+                Variable(2, Integer) = Store Integer(1)
+                Jump(1)"#]],
+    );
+}
+
+#[test]
+fn integer_assign_exp_with_lhs_dynamic_integer_and_rhs_classical_positive_integer() {
+    let program = get_rir_program(indoc! {
+        r#"
+        namespace Test {
+            @EntryPoint()
+            operation Main() : Int {
+                use q = Qubit();
+                mutable i = MResetZ(q) == Zero ? 0 | 1;
+                set i ^= 3;
+                i
+            }
+        }
+        "#,
+    });
+    let measurement_callable_id = CallableId(1);
+    assert_callable(
+        &program,
+        measurement_callable_id,
+        &expect![[r#"
+            Callable:
+                name: __quantum__qis__mresetz__body
+                call_type: Measurement
+                input_type:
+                    [0]: Qubit
+                    [1]: Result
+                output_type: <VOID>
+                body: <NONE>"#]],
+    );
+    let readout_callable_id = CallableId(2);
+    assert_callable(
+        &program,
+        readout_callable_id,
+        &expect![[r#"
+        Callable:
+            name: __quantum__qis__read_result__body
+            call_type: Readout
+            input_type:
+                [0]: Result
+            output_type: Boolean
+            body: <NONE>"#]],
+    );
+    let output_record_id = CallableId(3);
+    assert_callable(
+        &program,
+        output_record_id,
+        &expect![[r#"
+            Callable:
+                name: __quantum__rt__int_record_output
+                call_type: OutputRecording
+                input_type:
+                    [0]: Integer
+                    [1]: Pointer
+                output_type: <VOID>
+                body: <NONE>"#]],
+    );
+    assert_blocks(
+        &program,
+        &expect![[r#"
+            Blocks:
+            Block 0:Block:
+                Call id(1), args( Qubit(0), Result(0), )
+                Variable(0, Boolean) = Call id(2), args( Result(0), )
+                Variable(1, Boolean) = Icmp Eq, Variable(0, Boolean), Bool(false)
+                Branch Variable(1, Boolean), 2, 3
+            Block 1:Block:
+                Variable(3, Integer) = Store Variable(2, Integer)
+                Variable(4, Integer) = Store Integer(1)
+                Variable(5, Integer) = Mul Variable(4, Integer), Variable(3, Integer)
+                Variable(6, Integer) = Mul Variable(5, Integer), Variable(3, Integer)
+                Variable(7, Integer) = Mul Variable(6, Integer), Variable(3, Integer)
+                Variable(3, Integer) = Store Variable(7, Integer)
+                Call id(3), args( Variable(3, Integer), Pointer, )
+                Return
+            Block 2:Block:
+                Variable(2, Integer) = Store Integer(0)
+                Jump(1)
+            Block 3:Block:
+                Variable(2, Integer) = Store Integer(1)
+                Jump(1)"#]],
+    );
+}
+
+#[test]
+fn integer_assign_exp_with_lhs_dynamic_integer_and_rhs_dynamic_integer_raises_error() {
     let error = get_partial_evaluation_error(indoc! {
         r#"
         namespace Test {
@@ -1596,11 +1757,10 @@ fn integer_assign_exp_with_lhs_dynamic_integer_and_rhs_dynamic_integer() {
         }
         "#,
     });
-    // When this binary operation is supported, this error should be different.
     assert_error(
         &error,
         &expect![[
-            r#"Unimplemented("exponentiation for integer operands", Span { lo: 146, hi: 181 })"#
+            r#"Unexpected("exponent must be a classical integer", Span { lo: 146, hi: 181 })"#
         ]],
     );
 }
diff --git a/compiler/qsc_partial_eval/tests/operators.rs b/compiler/qsc_partial_eval/tests/operators.rs
index a36b2c37..ac6f329f 100644
--- a/compiler/qsc_partial_eval/tests/operators.rs
+++ b/compiler/qsc_partial_eval/tests/operators.rs
@@ -1508,7 +1508,7 @@ fn integer_mod_with_lhs_dynamic_integer_and_rhs_classical_integer() {
 }
 
 #[test]
-fn integer_exponentiation_with_lhs_classical_integer_and_rhs_dynamic_integer() {
+fn integer_exponentiation_with_lhs_classical_integer_and_rhs_dynamic_integer_raises_error() {
     let error = get_partial_evaluation_error(indoc! {
         r#"
         namespace Test {
@@ -1521,17 +1521,17 @@ fn integer_exponentiation_with_lhs_classical_integer_and_rhs_dynamic_integer() {
         }
         "#,
     });
-    // When this binary operation is supported, this error should be different.
     assert_error(
         &error,
         &expect![[
-            r#"Unimplemented("exponentiation for integer operands", Span { lo: 142, hi: 147 })"#
+            r#"Unexpected("exponent must be a classical integer", Span { lo: 142, hi: 147 })"#
         ]],
     );
 }
 
 #[test]
-fn integer_exponentiation_with_lhs_dynamic_integer_and_rhs_classical_integer() {
+fn integer_exponentiation_with_lhs_classical_integer_and_rhs_classical_negative_integer_raises_error(
+) {
     let error = get_partial_evaluation_error(indoc! {
         r#"
         namespace Test {
@@ -1539,22 +1539,178 @@ fn integer_exponentiation_with_lhs_dynamic_integer_and_rhs_classical_integer() {
             operation Main() : Int {
                 use q = Qubit();
                 let i = MResetZ(q) == Zero ? 0 | 1;
-                i ^ 3
+                i ^ -1
             }
         }
         "#,
     });
-    // When this binary operation is supported, this program should not yield an error.
     assert_error(
         &error,
         &expect![[
-            r#"Unimplemented("exponentiation for integer operands", Span { lo: 142, hi: 147 })"#
+            r#"EvaluationFailed("exponent must be non-negative", Span { lo: 142, hi: 148 })"#
         ]],
     );
 }
 
 #[test]
-fn integer_exponentiation_with_lhs_dynamic_integer_and_rhs_dynamic_integer() {
+fn integer_exponentiation_with_lhs_dynamic_integer_and_rhs_classical_zero_integer() {
+    let program = get_rir_program(indoc! {
+        r#"
+        namespace Test {
+            @EntryPoint()
+            operation Main() : Int {
+                use q = Qubit();
+                let i = MResetZ(q) == Zero ? 0 | 1;
+                i ^ 0
+            }
+        }
+        "#,
+    });
+    let measurement_callable_id = CallableId(1);
+    assert_callable(
+        &program,
+        measurement_callable_id,
+        &expect![[r#"
+            Callable:
+                name: __quantum__qis__mresetz__body
+                call_type: Measurement
+                input_type:
+                    [0]: Qubit
+                    [1]: Result
+                output_type: <VOID>
+                body: <NONE>"#]],
+    );
+    let readout_callable_id = CallableId(2);
+    assert_callable(
+        &program,
+        readout_callable_id,
+        &expect![[r#"
+        Callable:
+            name: __quantum__qis__read_result__body
+            call_type: Readout
+            input_type:
+                [0]: Result
+            output_type: Boolean
+            body: <NONE>"#]],
+    );
+    let output_record_id = CallableId(3);
+    assert_callable(
+        &program,
+        output_record_id,
+        &expect![[r#"
+            Callable:
+                name: __quantum__rt__int_record_output
+                call_type: OutputRecording
+                input_type:
+                    [0]: Integer
+                    [1]: Pointer
+                output_type: <VOID>
+                body: <NONE>"#]],
+    );
+    assert_blocks(
+        &program,
+        &expect![[r#"
+            Blocks:
+            Block 0:Block:
+                Call id(1), args( Qubit(0), Result(0), )
+                Variable(0, Boolean) = Call id(2), args( Result(0), )
+                Variable(1, Boolean) = Icmp Eq, Variable(0, Boolean), Bool(false)
+                Branch Variable(1, Boolean), 2, 3
+            Block 1:Block:
+                Variable(3, Integer) = Store Integer(1)
+                Call id(3), args( Variable(3, Integer), Pointer, )
+                Return
+            Block 2:Block:
+                Variable(2, Integer) = Store Integer(0)
+                Jump(1)
+            Block 3:Block:
+                Variable(2, Integer) = Store Integer(1)
+                Jump(1)"#]],
+    );
+}
+
+#[test]
+fn integer_exponentiation_with_lhs_dynamic_integer_and_rhs_classical_positive_integer() {
+    let program = get_rir_program(indoc! {
+        r#"
+        namespace Test {
+            @EntryPoint()
+            operation Main() : Int {
+                use q = Qubit();
+                let i = MResetZ(q) == Zero ? 0 | 1;
+                i ^ 3
+            }
+        }
+        "#,
+    });
+    let measurement_callable_id = CallableId(1);
+    assert_callable(
+        &program,
+        measurement_callable_id,
+        &expect![[r#"
+            Callable:
+                name: __quantum__qis__mresetz__body
+                call_type: Measurement
+                input_type:
+                    [0]: Qubit
+                    [1]: Result
+                output_type: <VOID>
+                body: <NONE>"#]],
+    );
+    let readout_callable_id = CallableId(2);
+    assert_callable(
+        &program,
+        readout_callable_id,
+        &expect![[r#"
+        Callable:
+            name: __quantum__qis__read_result__body
+            call_type: Readout
+            input_type:
+                [0]: Result
+            output_type: Boolean
+            body: <NONE>"#]],
+    );
+    let output_record_id = CallableId(3);
+    assert_callable(
+        &program,
+        output_record_id,
+        &expect![[r#"
+            Callable:
+                name: __quantum__rt__int_record_output
+                call_type: OutputRecording
+                input_type:
+                    [0]: Integer
+                    [1]: Pointer
+                output_type: <VOID>
+                body: <NONE>"#]],
+    );
+    assert_blocks(
+        &program,
+        &expect![[r#"
+            Blocks:
+            Block 0:Block:
+                Call id(1), args( Qubit(0), Result(0), )
+                Variable(0, Boolean) = Call id(2), args( Result(0), )
+                Variable(1, Boolean) = Icmp Eq, Variable(0, Boolean), Bool(false)
+                Branch Variable(1, Boolean), 2, 3
+            Block 1:Block:
+                Variable(3, Integer) = Store Integer(1)
+                Variable(4, Integer) = Mul Variable(3, Integer), Variable(2, Integer)
+                Variable(5, Integer) = Mul Variable(4, Integer), Variable(2, Integer)
+                Variable(6, Integer) = Mul Variable(5, Integer), Variable(2, Integer)
+                Call id(3), args( Variable(6, Integer), Pointer, )
+                Return
+            Block 2:Block:
+                Variable(2, Integer) = Store Integer(0)
+                Jump(1)
+            Block 3:Block:
+                Variable(2, Integer) = Store Integer(1)
+                Jump(1)"#]],
+    );
+}
+
+#[test]
+fn integer_exponentiation_with_lhs_dynamic_integer_and_rhs_dynamic_integer_raises_error() {
     let error = get_partial_evaluation_error(indoc! {
         r#"
         namespace Test {
@@ -1568,11 +1724,10 @@ fn integer_exponentiation_with_lhs_dynamic_integer_and_rhs_dynamic_integer() {
         }
         "#,
     });
-    // When this binary operation is supported, this error should be different.
     assert_error(
         &error,
         &expect![[
-            r#"Unimplemented("exponentiation for integer operands", Span { lo: 186, hi: 191 })"#
+            r#"Unexpected("exponent must be a classical integer", Span { lo: 186, hi: 191 })"#
         ]],
     );
 }
diff --git a/compiler/qsc_passes/src/capabilitiesck/tests_adaptive.rs b/compiler/qsc_passes/src/capabilitiesck/tests_adaptive.rs
index d8cd5395..7e8db51b 100644
--- a/compiler/qsc_passes/src/capabilitiesck/tests_adaptive.rs
+++ b/compiler/qsc_passes/src/capabilitiesck/tests_adaptive.rs
@@ -11,11 +11,11 @@ use super::tests_common::{
     LOOP_WITH_DYNAMIC_CONDITION, MEASUREMENT_WITHIN_DYNAMIC_SCOPE, MINIMAL,
     RETURN_WITHIN_DYNAMIC_SCOPE, USE_CLOSURE_FUNCTION, USE_DYNAMICALLY_SIZED_ARRAY,
     USE_DYNAMIC_BIG_INT, USE_DYNAMIC_BOOLEAN, USE_DYNAMIC_DOUBLE, USE_DYNAMIC_FUNCTION,
-    USE_DYNAMIC_INDEX, USE_DYNAMIC_INT, USE_DYNAMIC_OPERATION, USE_DYNAMIC_PAULI,
-    USE_DYNAMIC_QUBIT, USE_DYNAMIC_RANGE, USE_DYNAMIC_STRING, USE_DYNAMIC_UDT,
-    USE_ENTRY_POINT_INT_ARRAY_IN_TUPLE, USE_ENTRY_POINT_STATIC_BIG_INT,
-    USE_ENTRY_POINT_STATIC_BOOL, USE_ENTRY_POINT_STATIC_DOUBLE, USE_ENTRY_POINT_STATIC_INT,
-    USE_ENTRY_POINT_STATIC_INT_IN_TUPLE, USE_ENTRY_POINT_STATIC_PAULI,
+    USE_DYNAMIC_INDEX, USE_DYNAMIC_INT, USE_DYNAMIC_LHS_EXP_BINOP, USE_DYNAMIC_OPERATION,
+    USE_DYNAMIC_PAULI, USE_DYNAMIC_QUBIT, USE_DYNAMIC_RANGE, USE_DYNAMIC_RHS_EXP_BINOP,
+    USE_DYNAMIC_STRING, USE_DYNAMIC_UDT, USE_ENTRY_POINT_INT_ARRAY_IN_TUPLE,
+    USE_ENTRY_POINT_STATIC_BIG_INT, USE_ENTRY_POINT_STATIC_BOOL, USE_ENTRY_POINT_STATIC_DOUBLE,
+    USE_ENTRY_POINT_STATIC_INT, USE_ENTRY_POINT_STATIC_INT_IN_TUPLE, USE_ENTRY_POINT_STATIC_PAULI,
     USE_ENTRY_POINT_STATIC_RANGE, USE_ENTRY_POINT_STATIC_STRING,
 };
 use expect_test::{expect, Expect};
@@ -476,6 +476,58 @@ fn use_of_dynamic_index_yields_errors() {
     );
 }
 
+#[test]
+fn use_of_dynamic_lhs_exp_binop_yields_errors() {
+    check_profile(
+        USE_DYNAMIC_LHS_EXP_BINOP,
+        &expect![[r#"
+            [
+                UseOfDynamicInt(
+                    Span {
+                        lo: 104,
+                        hi: 124,
+                    },
+                ),
+                UseOfDynamicInt(
+                    Span {
+                        lo: 138,
+                        hi: 143,
+                    },
+                ),
+            ]
+        "#]],
+    );
+}
+
+#[test]
+fn use_of_dynamic_rhs_exp_binop_yields_errors() {
+    check_profile(
+        USE_DYNAMIC_RHS_EXP_BINOP,
+        &expect![[r#"
+            [
+                UseOfDynamicInt(
+                    Span {
+                        lo: 104,
+                        hi: 124,
+                    },
+                ),
+                UseOfDynamicInt(
+                    Span {
+                        lo: 138,
+                        hi: 143,
+                    },
+                ),
+                UseOfDynamicExponent(
+                    Span {
+                        lo: 138,
+                        hi: 143,
+                    },
+                ),
+            ]
+        "#]],
+    );
+}
+
 #[test]
 fn return_within_dynamic_scope_yields_no_errors() {
     check_profile(
diff --git a/compiler/qsc_passes/src/capabilitiesck/tests_adaptive_plus_integers.rs b/compiler/qsc_passes/src/capabilitiesck/tests_adaptive_plus_integers.rs
index 22193eaf..3f13d836 100644
--- a/compiler/qsc_passes/src/capabilitiesck/tests_adaptive_plus_integers.rs
+++ b/compiler/qsc_passes/src/capabilitiesck/tests_adaptive_plus_integers.rs
@@ -13,10 +13,11 @@ use super::tests_common::{
     LOOP_WITH_DYNAMIC_CONDITION, MEASUREMENT_WITHIN_DYNAMIC_SCOPE, MINIMAL,
     RETURN_WITHIN_DYNAMIC_SCOPE, USE_CLOSURE_FUNCTION, USE_DYNAMICALLY_SIZED_ARRAY,
     USE_DYNAMIC_BIG_INT, USE_DYNAMIC_BOOLEAN, USE_DYNAMIC_DOUBLE, USE_DYNAMIC_FUNCTION,
-    USE_DYNAMIC_INDEX, USE_DYNAMIC_INT, USE_DYNAMIC_OPERATION, USE_DYNAMIC_PAULI,
-    USE_DYNAMIC_QUBIT, USE_DYNAMIC_STRING, USE_DYNAMIC_UDT, USE_ENTRY_POINT_INT_ARRAY_IN_TUPLE,
-    USE_ENTRY_POINT_STATIC_BIG_INT, USE_ENTRY_POINT_STATIC_BOOL, USE_ENTRY_POINT_STATIC_DOUBLE,
-    USE_ENTRY_POINT_STATIC_INT, USE_ENTRY_POINT_STATIC_INT_IN_TUPLE, USE_ENTRY_POINT_STATIC_PAULI,
+    USE_DYNAMIC_INDEX, USE_DYNAMIC_INT, USE_DYNAMIC_LHS_EXP_BINOP, USE_DYNAMIC_OPERATION,
+    USE_DYNAMIC_PAULI, USE_DYNAMIC_QUBIT, USE_DYNAMIC_RHS_EXP_BINOP, USE_DYNAMIC_STRING,
+    USE_DYNAMIC_UDT, USE_ENTRY_POINT_INT_ARRAY_IN_TUPLE, USE_ENTRY_POINT_STATIC_BIG_INT,
+    USE_ENTRY_POINT_STATIC_BOOL, USE_ENTRY_POINT_STATIC_DOUBLE, USE_ENTRY_POINT_STATIC_INT,
+    USE_ENTRY_POINT_STATIC_INT_IN_TUPLE, USE_ENTRY_POINT_STATIC_PAULI,
     USE_ENTRY_POINT_STATIC_RANGE, USE_ENTRY_POINT_STATIC_STRING,
 };
 use expect_test::{expect, Expect};
@@ -404,6 +405,33 @@ fn use_of_dynamic_index_yields_errors() {
     );
 }
 
+#[test]
+fn use_of_dynamic_lhs_exp_binop_allowed() {
+    check_profile(
+        USE_DYNAMIC_LHS_EXP_BINOP,
+        &expect![[r#"
+        []
+    "#]],
+    );
+}
+
+#[test]
+fn use_of_dynamic_rhs_exp_binop_yields_errors() {
+    check_profile(
+        USE_DYNAMIC_RHS_EXP_BINOP,
+        &expect![[r#"
+            [
+                UseOfDynamicExponent(
+                    Span {
+                        lo: 138,
+                        hi: 143,
+                    },
+                ),
+            ]
+        "#]],
+    );
+}
+
 #[test]
 fn return_within_dynamic_scope_yields_no_errors() {
     check_profile(
diff --git a/compiler/qsc_passes/src/capabilitiesck/tests_base.rs b/compiler/qsc_passes/src/capabilitiesck/tests_base.rs
index e92e8a2c..38892526 100644
--- a/compiler/qsc_passes/src/capabilitiesck/tests_base.rs
+++ b/compiler/qsc_passes/src/capabilitiesck/tests_base.rs
@@ -11,11 +11,11 @@ use super::tests_common::{
     LOOP_WITH_DYNAMIC_CONDITION, MEASUREMENT_WITHIN_DYNAMIC_SCOPE, MINIMAL,
     RETURN_WITHIN_DYNAMIC_SCOPE, USE_CLOSURE_FUNCTION, USE_DYNAMICALLY_SIZED_ARRAY,
     USE_DYNAMIC_BIG_INT, USE_DYNAMIC_BOOLEAN, USE_DYNAMIC_DOUBLE, USE_DYNAMIC_FUNCTION,
-    USE_DYNAMIC_INDEX, USE_DYNAMIC_INT, USE_DYNAMIC_OPERATION, USE_DYNAMIC_PAULI,
-    USE_DYNAMIC_QUBIT, USE_DYNAMIC_RANGE, USE_DYNAMIC_STRING, USE_DYNAMIC_UDT,
-    USE_ENTRY_POINT_INT_ARRAY_IN_TUPLE, USE_ENTRY_POINT_STATIC_BIG_INT,
-    USE_ENTRY_POINT_STATIC_BOOL, USE_ENTRY_POINT_STATIC_DOUBLE, USE_ENTRY_POINT_STATIC_INT,
-    USE_ENTRY_POINT_STATIC_INT_IN_TUPLE, USE_ENTRY_POINT_STATIC_PAULI,
+    USE_DYNAMIC_INDEX, USE_DYNAMIC_INT, USE_DYNAMIC_LHS_EXP_BINOP, USE_DYNAMIC_OPERATION,
+    USE_DYNAMIC_PAULI, USE_DYNAMIC_QUBIT, USE_DYNAMIC_RANGE, USE_DYNAMIC_RHS_EXP_BINOP,
+    USE_DYNAMIC_STRING, USE_DYNAMIC_UDT, USE_ENTRY_POINT_INT_ARRAY_IN_TUPLE,
+    USE_ENTRY_POINT_STATIC_BIG_INT, USE_ENTRY_POINT_STATIC_BOOL, USE_ENTRY_POINT_STATIC_DOUBLE,
+    USE_ENTRY_POINT_STATIC_INT, USE_ENTRY_POINT_STATIC_INT_IN_TUPLE, USE_ENTRY_POINT_STATIC_PAULI,
     USE_ENTRY_POINT_STATIC_RANGE, USE_ENTRY_POINT_STATIC_STRING,
 };
 use expect_test::{expect, Expect};
@@ -589,6 +589,70 @@ fn use_of_dynamic_index_yields_errors() {
     );
 }
 
+#[test]
+fn use_of_dynamic_lhs_exp_binop_yields_errors() {
+    check_profile(
+        USE_DYNAMIC_LHS_EXP_BINOP,
+        &expect![[r#"
+        [
+            UseOfDynamicBool(
+                Span {
+                    lo: 104,
+                    hi: 116,
+                },
+            ),
+            UseOfDynamicBool(
+                Span {
+                    lo: 138,
+                    hi: 143,
+                },
+            ),
+            UseOfDynamicInt(
+                Span {
+                    lo: 138,
+                    hi: 143,
+                },
+            ),
+        ]
+    "#]],
+    );
+}
+
+#[test]
+fn use_of_dynamic_rhs_exp_binop_yields_errors() {
+    check_profile(
+        USE_DYNAMIC_RHS_EXP_BINOP,
+        &expect![[r#"
+            [
+                UseOfDynamicBool(
+                    Span {
+                        lo: 104,
+                        hi: 116,
+                    },
+                ),
+                UseOfDynamicBool(
+                    Span {
+                        lo: 138,
+                        hi: 143,
+                    },
+                ),
+                UseOfDynamicInt(
+                    Span {
+                        lo: 138,
+                        hi: 143,
+                    },
+                ),
+                UseOfDynamicExponent(
+                    Span {
+                        lo: 138,
+                        hi: 143,
+                    },
+                ),
+            ]
+        "#]],
+    );
+}
+
 #[test]
 fn return_within_dynamic_scope_yields_errors() {
     check_profile(
diff --git a/compiler/qsc_passes/src/capabilitiesck/tests_common.rs b/compiler/qsc_passes/src/capabilitiesck/tests_common.rs
index 1e399d8f..a49bad7a 100644
--- a/compiler/qsc_passes/src/capabilitiesck/tests_common.rs
+++ b/compiler/qsc_passes/src/capabilitiesck/tests_common.rs
@@ -327,6 +327,24 @@ pub const USE_DYNAMIC_INDEX: &str = r#"
         }
     }"#;
 
+pub const USE_DYNAMIC_LHS_EXP_BINOP: &str = r#"
+    namespace Test {
+        operation Foo() : Unit {
+            use q = Qubit();
+            let i = M(q) == Zero ? 0 | 1;
+            i ^ 1;
+        }
+    }"#;
+
+pub const USE_DYNAMIC_RHS_EXP_BINOP: &str = r#"
+    namespace Test {
+        operation Foo() : Unit {
+            use q = Qubit();
+            let i = M(q) == Zero ? 0 | 1;
+            1 ^ i;
+        }
+    }"#;
+
 pub const RETURN_WITHIN_DYNAMIC_SCOPE: &str = r#"
     namespace Test {
         operation Foo() : Int {
diff --git a/compiler/qsc_rca/tests/binops.rs b/compiler/qsc_rca/tests/binops.rs
index 1dcb475f..eea51bce 100644
--- a/compiler/qsc_rca/tests/binops.rs
+++ b/compiler/qsc_rca/tests/binops.rs
@@ -133,3 +133,87 @@ fn check_rca_for_nested_bin_ops_with_a_dynamic_operand() {
         ],
     );
 }
+
+#[test]
+fn check_rca_for_exp_op_with_classical_lhs_and_classical_rhs() {
+    let mut compilation_context = CompilationContext::default();
+    compilation_context.update(r#"2 ^ 3"#);
+    let package_store_compute_properties = compilation_context.get_compute_properties();
+    check_last_statement_compute_properties(
+        package_store_compute_properties,
+        &expect![
+            r#"
+            ApplicationsGeneratorSet:
+                inherent: Classical
+                dynamic_param_applications: <empty>"#
+        ],
+    );
+}
+
+#[test]
+fn check_rca_for_exp_op_with_dynamic_lhs_and_classical_rhs() {
+    let mut compilation_context = CompilationContext::default();
+    compilation_context.update(
+        r#"{
+            use q = Qubit();
+            let i = M(q) == Zero ? 0 | 1;
+            i ^ 2
+        }"#,
+    );
+    let package_store_compute_properties = compilation_context.get_compute_properties();
+    check_last_statement_compute_properties(
+        package_store_compute_properties,
+        &expect![[r#"
+            ApplicationsGeneratorSet:
+                inherent: Quantum: QuantumProperties:
+                    runtime_features: RuntimeFeatureFlags(UseOfDynamicBool | UseOfDynamicInt)
+                    value_kind: Element(Dynamic)
+                dynamic_param_applications: <empty>"#]],
+    );
+}
+
+#[test]
+fn check_rca_for_exp_op_with_classical_lhs_and_dynamic_rhs() {
+    let mut compilation_context = CompilationContext::default();
+    compilation_context.update(
+        r#"{
+            use q = Qubit();
+            let i = M(q) == Zero ? 0 | 1;
+            2 ^ i
+        }"#,
+    );
+    let package_store_compute_properties = compilation_context.get_compute_properties();
+    check_last_statement_compute_properties(
+        package_store_compute_properties,
+        &expect![[r#"
+            ApplicationsGeneratorSet:
+                inherent: Quantum: QuantumProperties:
+                    runtime_features: RuntimeFeatureFlags(UseOfDynamicBool | UseOfDynamicInt | UseOfDynamicExponent)
+                    value_kind: Element(Dynamic)
+                dynamic_param_applications: <empty>"#]],
+    );
+}
+
+#[test]
+fn check_rca_for_exp_op_with_dynamic_lhs_and_dynamic_rhs() {
+    let mut compilation_context = CompilationContext::default();
+    compilation_context.update(
+        r#"{
+            use (a, b) = (Qubit(), Qubit());
+            let (c, d) = (M(a) == Zero, M(b) == Zero);
+            let i = c ? 0 | 1;
+            let j = d ? 0 | 1;
+            i ^ j
+        }"#,
+    );
+    let package_store_compute_properties = compilation_context.get_compute_properties();
+    check_last_statement_compute_properties(
+        package_store_compute_properties,
+        &expect![[r#"
+            ApplicationsGeneratorSet:
+                inherent: Quantum: QuantumProperties:
+                    runtime_features: RuntimeFeatureFlags(UseOfDynamicBool | UseOfDynamicInt | UseOfDynamicExponent)
+                    value_kind: Element(Dynamic)
+                dynamic_param_applications: <empty>"#]],
+    );
+}