  Qubit allocation is a process to assign physical qubits to logical qubits in
a quantum program. Since some quantum computers have connectivity constraints
on applications of two-qubit operations, it is mainly concerned with finding an
assignment and inserting instructions to satisfy the connectivity constraints.
Many methods have been proposed for the qubit allocation problem for low-level
quantum programs. This paper presents a type-based framework of qubit
allocation for a quantum programming language with first-order functions. In
our framework, the connectivity constraints are expressed by a simple graph of
qubits called a coupling graph. We formalize (1) the source language, whose
type system verifies that the number of qubits required for a given program to
run does not exceed the number of nodes of the coupling graph, (2) the target
language, whose qualified type system verifies that a well-typed program
satisfies the connectivity constraints, and (3) an algorithm to translate a
source program into a target program. We prove that both languages are
type-safe and that the translation algorithm is type preserving.
