  In noisy intermediate-scale quantum computing, the limited scalability of a
single quantum processing unit (QPU) can be extended through distributed
quantum computing (DQC), in which one can implement global operations over two
QPUs by entanglement-assisted local operations and classical communication. To
facilitate this type of DQC in experiments, we need an entanglement-efficient
protocol. To this end, we extend the protocol in [Eisert et. al., PRA,
62:052317(2000)] implementing each nonlocal controlled-unitary gate locally
with one maximally entangled pair to a packing protocol, which can pack
multiple nonlocal controlled-unitary gates locally using one maximally
entangled pair. In particular, two types of packing processes are introduced as
the building blocks, namely the distributing processes and embedding processes.
Each distributing process distributes corresponding gates locally with one
entangled pair. The efficiency of entanglement is then enhanced by embedding
processes, which merge two non-sequential distributing processes and hence save
the entanglement cost. We show that the structure of distributability and
embeddability of a quantum circuit can be fully represented by the
corresponding packing graphs and conflict graphs. Based on these graphs, we
derive heuristic algorithms for finding an entanglement-efficient packing of
distributing processes for a given quantum circuit to be implemented by two
parties. These algorithms can determine the required number of local auxiliary
qubits in the DQC. We apply these algorithms for bipartite DQC of unitary
coupled-cluster circuits and find a significant reduction of entanglement cost
through embeddings. This method can determine a constructive upper bound on the
entanglement cost for the DQC of quantum circuits.
