03.65.Ud, 03.67.Lx, 06.20.Dk

# Optimal fermion-to-qubit mapping via ternary trees with applications to
reduced quantum states learning

Zhang Jiang<EMAIL_ADDRESS>Google Research, Venice, CA 90291  Amir Kalev
<EMAIL_ADDRESS>Joint Center for Quantum Information and Computer Science,
University of Maryland, College Park, MD 20742-2420, USA  Wojciech
Mruczkiewicz  Google Research, Venice, CA 90291  Hartmut Neven  Google
Research, Venice, CA 90291

(2020-05-26)

###### Abstract

We introduce a fermion-to-qubit mapping defined on ternary trees, where any
single Majorana operator on an $n$-mode fermionic system is mapped to a multi-
qubit Pauli operator acting nontrivially on $\lceil\log_{3}(2n+1)\rceil$
qubits. The mapping has a simple structure and is optimal in the sense that it
is impossible to construct Pauli operators in any fermion-to-qubit mapping
acting nontrivially on less than $\log_{3}(2n)$ qubits on average. We apply it
to the problem of learning $k$-fermion reduced density matrix (RDM), a problem
relevant in various quantum simulation applications. We show that one can
determine individual elements of all $k$-fermion RDMs in parallel, to
precision $\epsilon$, by repeating a single quantum circuit for
$\lesssim(2n+1)^{k}\epsilon^{-2}$ times. This result is based on a method we
develop here that allows one to determine individual elements of all $k$-qubit
RDMs in parallel, to precision $\epsilon$, by repeating a single quantum
circuit for $\lesssim 3^{k}\epsilon^{-2}$ times, independent of the system
size. This improves over existing schemes for determining qubit RDMs.

##  1 Introduction

Quantum simulation opens an alternative approach to solving hard problems
ubiquitous in physics, chemistry, and material sciences (e.g., high
temperature superconductivity) [Feynman(1982), Lloyd(1996), Georgescu  _et
al._(2014)Georgescu, Ashhab, and Nori, Wecker  _et al._(2015)Wecker, Hastings,
Wiebe, Clark, Nayak, and Troyer, Babbush  _et al._(2018)Babbush, Wiebe,
McClean, McClain, Neven, and Chan, Jiang  _et al._(2018)Jiang, Sung,
Kechedzhi, Smelyanskiy, and Boixo]. With the rapid advances in quantum
computing devices, such as trapped ions [Cirac and Zoller(1995), Kielpinski
_et al._(2002)Kielpinski, Monroe, and Wineland, Häffner  _et
al._(2008)Häffner, Roos, and Blatt] and superconducting qubits [Devoret  _et
al._(2004)Devoret, Wallraff, and Martinis, Wendin(2017)], we are closer today
to realize this goal. An essential step in digital quantum simulation of a
fermionic systems is mapping it onto a qubit system. Having an efficient,
simple, fermion-to-qubit mapping is a key ingredient in any quantum simulation
protocol, e.g., the variational quantum eigensolver (VQE) [Peruzzo  _et
al._(2014)Peruzzo, McClean, Shadbolt, Yung, Zhou, Love, Aspuru-Guzik, and O’
Brien, McClean  _et al._(2016)McClean, Romero, Babbush, and Aspuru-Guzik].

The most common fermion-to-qubit mapping is the Jordan-Wigner transformation
(JWT) [Nielsen(2005)], which maps single fermionic operators on an $n$-mode
fermionic system to qubit operators acting nontrivially on $\mathcal{O}(n)$
qubits. In the JWT, the qubit state $\lvert\hskip 0.4pt0\hskip 0.4pt\rangle$
($\lvert\hskip 0.4pt1\hskip 0.4pt\rangle$) represents an occupied (unoccupied)
fermionic mode, i.e., its occupation information. Instead, one can also store
the parity information of the fermionic system [Seeley  _et al._(2012)Seeley,
Richard, and Love], where the $j$-th qubit state is $\lvert\hskip 0.4pt0\hskip
0.4pt\rangle$ ($\lvert\hskip 0.4pt1\hskip 0.4pt\rangle$) if the total number
of fermions in the first $j$ fermionic modes is even (odd). By balancing the
locality of occupation and parity information, the Bravyi-Kitaev
transformation (BKT) [Bravyi and Kitaev(2002)] maps single fermionic operators
to qubit operators acting nontrivially on $\mathcal{O}(\log_{2}n)$ qubits. The
BKT is important because it avoids operations acting on an extensive number of
qubits. It is also quite involved, and many authors have discussed its
applications in quantum simulation of fermionic systems [Seeley  _et
al._(2012)Seeley, Richard, and Love, Tranter  _et al._(2015)Tranter, Sofia,
Seeley, Kaicher, McClean, Babbush, Coveney, Mintert, Wilhelm, and Love].
Recently [Havlíček  _et al._(2017)Havlíček, Troyer, and Whitfield], the BKT
was reformulated using the Fenwick trees, a classical data structure that
allows for efficient updating elements and calculating prefix sums.

As the possibilities to study fermionic systems on quantum computing devices
materialize [Arute  _et al._(2019)Arute, Arya, Babbush, Bacon, Bardin,
Barends, Biswas, Boixo, Brandao, Buell, Burkett, Chen, Chen, Chiaro, Collins,
Courtney, Dunsworth, Farhi, Foxen, Fowler, Gidney, Giustina, Graff, Guerin,
Habegger, Harrigan, Hartmann, Ho, Hoffmann, Huang, Humble, Isakov, Jeffrey,
Jiang, Kafri, Kechedzhi, Kelly, Klimov, Knysh, Korotkov, Kostritsa, Landhuis,
Lindmark, Lucero, Lyakh, Mandr??, McClean, McEwen, Megrant, Mi, Michielsen,
Mohseni, Mutus, Naaman, Neeley, Neill, Niu, Ostby, Petukhov, Platt, Quintana,
Rieffel, Roushan, Rubin, Sank, Satzinger, Smelyanskiy, Sung, Trevithick,
Vainsencher, Villalonga, White, Yao, Yeh, Zalcman, Neven, and Martinis], it is
well timed to explore other, possibly simpler and more efficient fermion-to-
qubit transformations, beyond existing ones. Here, we present such a
transformation. We construct a simple fermion-to-qubit mapping defined on
ternary trees. It maps any single Majorana operator on an $n$-mode fermionic
system to a multi-qubit Pauli operator acting nontrivially on
$\lceil\log_{3}(2n+1)\rceil$ qubits. For large $n$, it is approximately
$\log_{2}3\simeq 1.58$ times lower than $\lceil\log_{2}n+1\rceil$ in the BKT
[Havlíček  _et al._(2017)Havlíček, Troyer, and Whitfield]. We prove that the
operator weight in the ternary-tree mapping is optimal. The ternary-tree
mapping was also introduced to derive representations of the Clifford algebras
and spin group [Vlasov(2019)].

In quantum simulation, it is often desirable to learn the quantum state
involving only a fixed numbers of qubits (fermions), i.e., reduced density
matrices (RDMs) tomography [Nielsen and Chuang(2000), Sharma  _et
al._(2008)Sharma, Dewhurst, Lathiotakis, and Gross, Fagotti and Essler(2013),
Rubin  _et al._(2018)Rubin, Babbush, and McClean]. Learning the $k$-particle
RDM not only allows one to estimate the ground state energy of a fermionic
system with up to $k$-particle interactions, it also enables one to derive a
large number of important properties of the system, such as multipole moments
[Gidofalvi and Mazziotti(2007)] and derivatives of energy [Overy  _et
al._(2014)Overy, Booth, Blunt, Shepherd, Cleland, and Alavi, O’Brien  _et
al._(2019)O’Brien, Senjean, Sagastizabal, Bonet-Monroig, Dutkiewicz, Buda,
DiCarlo, and Visscher]; moreover, it is an indispensable part in error-
mitigating techniques by relaxing the single-particle orbitals [McClean  _et
al._(2017)McClean, Kimchi-Schwartz, Carter, and de Jong, Takeshita  _et
al._(2020)Takeshita, Rubin, Jiang, Lee, Babbush, and McClean]. Using the
ternary-tree mapping, we show that individual elements of the $k$-particle RDM
of an $n$-mode fermionic state stored in a quantum computer can be determined
in parallel to precision $\epsilon$ by repeating a single quantum circuit for
$\lesssim(2n+1)^{k}/\epsilon^{2}$ times.

The technique to obtain the fermionic RDMs is based on a method we develop
here that allows one to determine individual elements of all $k$-qubit RDMs of
an $n$-qubit system in parallel, to a precision $\epsilon$, by repeating a
single quantum circuit for $\lesssim 3^{k}/\epsilon^{2}$ times, independent of
the system size $n$. Our scheme is based on measuring in the Bell basis of a
system qubit and an ancilla qubit. It improves the scaling of a recent result
[Cotler and Wilczek(2020), Bonet-Monroig  _et al._(2019)Bonet-Monroig,
Babbush, and O’Brien] by a $\log n$ factor. Moreover, it is informationally
complete, implying that one can retrieve the entire quantum state by simply
repeating the same quantum circuit many times.

The paper is organized into two parts. In Sec. 2, we introduce the ternary-
tree mapping and prove its optimality. In Sec. 3, we discuss the Bell-basis
measurement scheme for quantum tomography of qubits, and apply it to fermions
using the ternary-tree mapping. In App. A, we prove that the Bell-basis
measurement scheme for qubits implements a symmetric informationally complete
(SIC) POVM. In App. B, we generalize the Bell-basis measurement scheme to
qudits and prove its informationally completeness and discuss its relation to
SIC POVMs.

##  2 Fermion-to-qubit mapping

In the second quantization formulation to quantum mechanics, the $n$-mode
fermionic operators can be expanded using the Majorana fermion operators

$\displaystyle\gamma_{2j}=c^{\dagger}_{j}+c_{j}\,,\quad\gamma_{2j+1}=i\hskip
0.4pt\big{(}c^{\dagger}_{j}-c_{j}\big{)}\,,$ (1)

for $j=1,2,\ldots,n$, where $c_{j}$ and $c^{\dagger}_{j}$ are the $j$-th
annihilation and creation operators. The Majorana operators satisfy the simple
anticommutation relation ${\\{\hskip 0.4pt\gamma_{u},\,\gamma_{v}\hskip
0.4pt\\}}=2\delta_{uv}$ for $u,\,v=1,\ldots,2n$. In what follows we construct
$2n$ independent multi-qubit Pauli operators that are mutually anticommute,
which can be used to represent the Majorana operators.

Our fermion-to-qubit mapping is defined on a ternary tree, where each node
(except those in the bottom level of the tree) is associated with a qubit. We
start with the case that the tree is complete and come back to the more
general cases later on. The total number of qubits in a complete ternary tree
of height $h$ is

$\displaystyle n=\sum_{\ell=0}^{h-1}\,3^{\ell}=\frac{3^{h}-1}{2}\,.$ (2)

We label the qubit associated with the root node by $0$, the rest of the
qubits are indexed consecutively, as we are going down the tree, see Fig. 1.
The Pauli operators of the $\eta$-th qubit are denoted as
$\sigma^{x,\,y,\,z}_{\eta}$. Each root-to-leaf path on the tree can be
uniquely specified by the vector $\boldsymbol{p}=(p_{0},\ldots,p_{h-1})$,
where $p_{\ell}=0,\,1,\,2$ determines the next node on the path with depth
$\ell+1$ based on the current node with depth $\ell$. We can write the index
of a node of depth $\ell$ on the path $\boldsymbol{p}$ by

$\displaystyle\eta(\hskip 0.4pt\hskip 0.4pt\boldsymbol{p},\hskip
0.4pt\ell)=\frac{3^{\ell}-1}{2}+\sum_{j=0}^{\ell-1}\,3^{\ell-1-j}\,p_{j}\,,\quad\text{for
$\ell\geq 0$}\,,$ (3)

where $(3^{\ell}-1)/2$ is the number of nodes with depth less than $\ell$.
Next, we associate a multi-Pauli operator, $A_{\boldsymbol{p}}$, with each
root-to-leaf path $\boldsymbol{p}$,

$\displaystyle
A_{\boldsymbol{p}}=\prod_{\ell=0}^{h-1}\sigma^{\chi(p_{\ell})}_{\eta(\hskip
0.4pt\hskip 0.4pt\boldsymbol{p},\hskip 0.4pt\ell)}\,,\quad
A_{\boldsymbol{p}}^{2}=\mathbbm{1}\,,$ (4)

where $\chi(p)=x,\,y,\,z$ for $p=0,\,1,\,2$, respectively. By construction
these operators mutually anticommute, i.e., ${\\{\hskip
0.4ptA_{\boldsymbol{p}},\,A_{\boldsymbol{q}}\hskip 0.4pt\\}}=0$ for
$\boldsymbol{p}\neq\boldsymbol{q}$. This is because $\boldsymbol{p}$ and
$\boldsymbol{q}$ have to diverge at some point. Before that point they involve
the same Pauli operators on the same qubits, at the point of divergence
$A_{\boldsymbol{p}}$ and $A_{\boldsymbol{q}}$ associate different Pauli
operator to the same qubit, whereas after that point they involve Pauli
operators on different qubits.

Figure 1: Ternary-tree mapping. An example of the fermion-to-qubit mapping in
a ternary tree of height $2$. The label of the qubit associated with a node is
written inside it. We introduce a Pauli operator for each root-to-leaf path in
the tree. For example, the left-most path corresponds to the Pauli operator
$A_{0,0}=\sigma_{0}^{x}\sigma_{1}^{x}$.

There are $3^{h}=2n+1$ distinct root-to-leaf paths in the ternary tree,
whereas the total number of independent operators $A_{\boldsymbol{p}}$ is
$2n$. This is because the product of $A_{\boldsymbol{p}}$ for all paths
${\boldsymbol{p}}$ is proportional to the identity operator. Therefore, we can
map $2n$ Majorana operators to $2n$ independent Pauli operators that mutually
anticommute. The Pauli weight of $A_{\boldsymbol{p}}$ equals to the tree
height $h=\log_{3}(2n+1)$. In the large $n$ limit, it is approximately
$\log_{2}3\simeq 1.58$ times lower than $\lceil\log_{2}n+1\rceil$ in the BKT
[Havlíček  _et al._(2017)Havlíček, Troyer, and Whitfield]. This reduction is
achieved by balancing all of the three Pauli operators, whereas only Pauli-$x$
and $z$ are balanced in the BKT.

Consider the case that $2n+1$ is not a power of 3, i.e., $3^{h}<2n+1<3^{h+1}$
for some nonnegative integer $h$. We can still construct a ternary-tree
mapping with Pauli weights less or equal to $\lceil\log_{3}(2n+1)\rceil$ by
taking the following steps:

  1. 1.

Introduce a complete ternary tree with height $h$,

  2. 2.

Choose $n-(3^{h}-1)/2$ leaves in the tree and associate a qubit with each of
them,

  3. 3.

Branch the corresponding $A_{\boldsymbol{p}}$ to
$A_{\boldsymbol{p}}\otimes\sigma_{\boldsymbol{p}}^{x,y,z}$, where
$\sigma_{\boldsymbol{p}}^{x,y,z}$ are the Pauli operators on the added qubit,

  4. 4.

Map the resulting Pauli operators, of weights $h$ and $h+1$, to Majorana
operators.

We now prove that the ternary-tree mapping is optimal.

######  Theorem 1.

The averaged weight of the Pauli operators in any map that transforms an
$n$-mode fermionic system onto a qubit system is at least $\log_{3}(2n)$.

###### Proof.

We introduce the real vector ${\mathbf{r}}^{\top}=(r_{1},\ldots,r_{2n})$,
where $r_{u}=\langle\gamma_{u}\rangle=\langle\gamma_{u}^{\dagger}\rangle$ is
the expectation value of the $u$-th Majorana operator. We also introduce the
$2n\times 2n$ Hermitian matrix $G$ whose elements are given by

$\displaystyle
G_{uv}=\big{\langle}(\gamma_{u}-r_{u})(\gamma_{v}-r_{v})\big{\rangle}=\langle\gamma_{u}\gamma_{v}\rangle-
r_{u}\hskip 0.4ptr_{v}\,.$ (5)

Since $G$ is a Gram matrix it is positive semidefinite. Consider the
expectation value

$\displaystyle{\mathbf{r}}^{\top}\\!G\,\mathbf{r}$
$\displaystyle=\sum_{u,\,v}r_{u}\hskip
0.4ptr_{v}\,\langle\gamma_{u}\gamma_{v}\rangle-r_{u}^{2}\,r_{v}^{2}$
$\displaystyle={\mathbf{r}}^{\top}{\mathbf{r}}-({\mathbf{r}}^{\top}\mathbf{r})^{2}\geq
0\,,$ (6)

where we use
$\langle\gamma_{u}\gamma_{v}\rangle=-\langle\gamma_{v}\gamma_{u}\rangle$ for
$u\neq v$ and $\langle\gamma_{u}\gamma_{u}\rangle=1$; therefore, we have
${\mathbf{r}}^{\top}\mathbf{r}\leq 1$ for any fermionic state. We then
consider an $m$-qubit product state $\xi^{\otimes m}$, where $\xi$ is the
single-qubit pure state

$\displaystyle\xi=\frac{1}{2}\bigg{(}\mathbbm{1}+\frac{1}{\sqrt{3}}\big{(}\sigma^{x}+\sigma^{y}+\sigma^{z}\big{)}\bigg{)}\,,$
(7)

which leads to
$\operatorname{Tr}(\sigma^{x}\xi)=\operatorname{Tr}(\sigma^{y}\xi)=\operatorname{Tr}(\sigma^{z}\xi)=1/{\sqrt{3}}$.
This particular pure product state is symmetric with respect to $\sigma_{x}$,
$\sigma_{y}$ and $\sigma_{z}$; therefore, it allows us to treat expectation
values of Pauli operators with the same weight on an equal footing. If
$\gamma_{u}$ is mapped to a Pauli operator with weight $w_{u}$, we have
$\lvert r_{u}\rvert=1/\sqrt{3}^{\,w_{u}}$ under the product state
$\xi^{\otimes m}$, and thus

$\displaystyle
2n\,3^{-\overline{w}}\leq\sum_{u=1}^{2n}3^{-w_{u}}={\mathbf{r}}^{\top}\mathbf{r}\leq
1\,,$ (8)

where $\overline{w}=\frac{1}{2n}\,\sum_{u=1}^{2n}w_{u}$ and we use the fact
that $y=3^{-x}$ is a convex function in the leftmost inequality. As a
consequence, we have

$\displaystyle\overline{w}\geq\log_{3}(2n)\,.$ (9)

When the Pauli weight $w_{u}=w$ is a constant, we have

$\displaystyle w\geq\lceil\log_{3}(2n)\rceil\geq\log_{3}(2n+1)\,.$ (10)

Therefore, the ternary-tree mapping that we have constructed is optimal. ∎

##  3 Reduced density matrices tomography

###  3.1 Qubits

In this section, we first introduce a method of reconstructing RDMs
specifically for qubit systems, and then use this method together with the
ternary-tree mapping to reconstruct RDMs for fermionic systems.

Given an $n$-qubit quantum state $\rho$, the $k$-qubit reduced density matrix
($k$-RDM) may be written as

$\displaystyle\operatorname{Tr}_{\begin{subarray}{c}\neq
j_{1},\ldots,j_{k}\end{subarray}}\big{(}\rho\big{)}=\frac{1}{2^{k}}\\!\sum_{\begin{subarray}{c}\alpha_{1},\ldots,\alpha_{k}\,=\,0,\,x,\,y,\,z\end{subarray}}\\!\\!\rho^{\alpha_{1},\ldots,\alpha_{k}}_{j_{1},\ldots,j_{k}}\operatorname*{\text{\raisebox{1.07639pt}{\scalebox{0.8}{$\bigotimes$}}}}_{i=1}^{k}\sigma^{\alpha_{i}}_{j_{i}}\,,$
(11)

where $\sigma_{j}^{\alpha}$ is the Pauli operator on the $j$-th qubit,
$\sigma^{0}=\mathbbm{1}$ and $\sigma^{x,\,y,\,z}$ are the Pauli-$x$, -$y$, and
-$z$ operators, respectively. The matrix elements of the $k$-RDMs in Eq. (11)
are defined as

$\displaystyle\rho^{\alpha_{1},\ldots,\alpha_{k}}_{j_{1},\ldots,j_{k}}=\operatorname{Tr}\bigg{(}\rho\,\operatorname*{\text{\raisebox{1.07639pt}{\scalebox{0.8}{$\bigotimes$}}}}_{i=1}^{k}\sigma_{j_{i}}^{\alpha_{i}}\bigg{)}\,.$
(12)

Assuming all $(k-1)$-RDMs are known, measuring the $\binom{n}{k}\hskip
0.4pt3^{k}$ different observables,
$\operatorname*{\text{\raisebox{1.07639pt}{\scalebox{0.8}{$\bigotimes$}}}}_{i=1}^{k}\sigma_{j_{i}}^{\alpha_{i}}$
($\alpha_{i}\neq 0$), provides us with the required information to reconstruct
all $k$-RDMs. Under the assumption that only single-qubit operations are
allowed, Cotler and Wilczek [Cotler and Wilczek(2020)] showed that elements in
all $k$-RDMs can be sampled by implementing $e^{\mathcal{O}(k)}\log(n)$
different quantum circuits.

Changing quantum circuits is typically quite slow on current programmable
quantum devices, e.g., those based on FPGAs, while repeating a single circuit
may be done much faster. To circumvent the problem of programming various
circuits, we propose a scheme that allows one to estimate all $k$-qubit RDMs
at once. Our approach is based on measuring a system qubit and an ancilla
qubit in the Bell basis

$\displaystyle\lvert\hskip 0.4pt\Phi^{\pm}\hskip
0.4pt\rangle=\frac{1}{\sqrt{2}}\Big{(}\lvert\hskip 0.4pt0\hskip
0.4pt\rangle\otimes\lvert\hskip 0.4pt0\hskip 0.4pt\rangle\pm\lvert\hskip
0.4pt1\hskip 0.4pt\rangle\otimes\lvert\hskip 0.4pt1\hskip
0.4pt\rangle\Big{)}\,,$ (13) $\displaystyle\lvert\hskip 0.4pt\Psi^{\pm}\hskip
0.4pt\rangle=\frac{1}{\sqrt{2}}\Big{(}\lvert\hskip 0.4pt0\hskip
0.4pt\rangle\otimes\lvert\hskip 0.4pt1\hskip 0.4pt\rangle\pm\lvert\hskip
0.4pt1\hskip 0.4pt\rangle\otimes\lvert\hskip 0.4pt0\hskip
0.4pt\rangle\Big{)}\,.$ (14)

The Bell basis is a common eigenbasis of the commuting operators
$\sigma^{x}\otimes\sigma^{x}$, $\sigma^{y}\otimes\sigma^{y}$, and
$\sigma^{z}\otimes\sigma^{z}$, and their eigenvalues are listed in Tab. 1.

Outcome |  $\sigma^{x}\otimes\sigma^{x}$ |  $\sigma^{y}\otimes\sigma^{y}$ |  $\sigma^{z}\otimes\sigma^{z}$
---|---|---|---
$\Phi^{+}$ | 1 | -1 | 1
$\Phi^{-}$ | -1 | 1 | 1
$\Psi^{+}$ | 1 | 1 | -1
$\Psi^{-}$ | -1 | -1 | -1
Table 1: Eigenvalues of the Pauli tensor products in the Bell basis.

Therefore, the expectation values of these three operators can be measured
simultaneously. The Bell measurements can be done in parallel for all pairs of
qubits using Hardmard and CNOT gates. The quantum circuit to implement our
scheme, for one system qubit and one ancilla qubit, is plotted in Fig.
LABEL:fig:ibmcircuit.

If the Pauli-$x$, -$y$, and -$z$ operators are sampled at the same rate, a
natural choice of the ancilla state is the pure state defined in Eq. (7). It
can be obtained by rotating $\lvert\hskip 0.4pt0\hskip 0.4pt\rangle$ about the
$x$ axis by an angle $\theta=\arccos(1/\sqrt{3}\,)$ followed by a rotation
around the $z$ axis by an angle $\phi=3\pi/4$, see Fig. 3.1. Measuring the
system and ancilla qubits in the Bell basis yields
$\displaystyle\operatorname{Tr}\bigg{(}\rho\otimes\xi^{\otimes
n}\prod_{i=1}^{k}\sigma^{\alpha_{i}}_{j_{i}}\otimes\sigma^{\alpha_{i}}_{j^{\prime}_{i}}\bigg{)}=\frac{1}{\sqrt{3}^{\,k}}\;\rho^{\alpha_{1},\ldots,\alpha_{k}}_{j_{1},\ldots,j_{k}}\,,$
(15) where we use $\operatorname{Tr}(\xi\hskip
0.4pt\sigma^{x})=\operatorname{Tr}(\xi\hskip
0.4pt\sigma^{y})=\operatorname{Tr}(\xi\hskip 0.4pt\sigma^{z})=1/\sqrt{3}$. Due
to the factor $1/\sqrt{3}^{\,k}$, we must run the experiment
$3^{k}/\epsilon^{2}$ times to obtain the standard-deviation error $\epsilon$.
In summary, our scheme measures all $k$-qubit RMD elements in parallel, with
error that scales as $\epsilon$, by running a single quantum circuit for
$3^{k}/\epsilon^{2}$ times:

  1. 1.

To each system qubit (labeled by $j$) attach an ancillary qubit (labelled by
$j^{\prime}$) in a known state $\xi$, so that the total system-ancilla state
is $\rho\otimes\xi^{\otimes n}$.

  2. 2.

Measure each pair of qubits $(j,j^{\prime})$ in the common eigenbasis of
$\sigma^{x}\otimes\sigma^{x}$, $\sigma^{y}\otimes\sigma^{y}$, and
$\sigma^{z}\otimes\sigma^{z}$, i.e., the Bell basis.

While the scheme in [Cotler and Wilczek(2020)] allows one to specify all RDMs
up to some order $k$, our scheme allows for specifying the entire $n$-qubit
state, i.e., all RDMs, for all $k\in[1,n]$ 111For finite rounds of
measurements, though we have information about all RDMs, the ones involving
fewer qubits (smaller $k$) would be estimated more accurately than those
involving more qubits (lager $k$).. The reason for this inherent difference is
rooted in that the measurement we perform on each qubit is informationally
complete, that is it allows us to estimate the expectation values of
$\sigma_{x}$, $\sigma_{y}$, and $\sigma_{z}$, from one POVM. Since this
measurement is done in parallel for all qubits, we can use the data to
estimate the entire $n$-qubit state. In Apps. A, we show it implements a
symmetric informationally-complete measurement (SIC POVM) on a qubit, a.k.a.,
the tetrahedron measurement [Řeháček  _et al._(2004)Řeháček, Englert, and
Kaszlikowski]. Finally, we note that recent work [Hamamura and Imamichi(2019)]
has also suggested to use Bell-measurements in the context of RDMs
reconstruction. However, there the use of Bell-measurements was done on pairs
of system qubits. In App. B, we generalize the Bell-basis measurement method
to $D$-dimensional system, and show that similar to the qubit case it is
informationally-complete and implements SIC POVMs in certain cases.

###  3.2 Fermions

Now, we apply the Bell-basis measurement method for RDM reconstruction
together with the ternary-tree mapping for reconstructing $k$-fermion RDMs.
Generally, it requires $\mathcal{O}(n^{2k})$ parameters to determine the
$k$-RDMs of an $n$-mode fermionic system. To make matters worse, fermions obey
anticommutation relations which prevents one from finding large groups of
commuting operators that can be measured simultaneously. In second
quantization, the elements in a fermionic $k$-RDM of $n$ modes can be
expressed as expectation values involving $2k$ Majorana operators. For
instance, the fermionic 2-RDM may be written as

$\displaystyle\rho_{stuv}=\big{\langle}\gamma_{s}\gamma_{t}\gamma_{u}\gamma_{v}\big{\rangle}\,,$
(16)

where the $\gamma$’s are the Majorana fermion operators defined above. Encoded
with the ternary-tree mapping, the Pauli weights of elements in fermionic
$k$-RDMs are at most $2k\log_{3}(2n+1)$. With the Bell-basis measurement
strategy, the matrix elements are attenuated by a factor bounded by

$\displaystyle{\sqrt{3}}^{\>2k\log_{3}(2n+1)}=(2n+1)^{k}\,.$ (17)

Therefore, all elements in a fermionic $k$-RDMs can be measured to precision
$\epsilon$ by repeating the same circuit for $\lesssim(2n+1)^{k}/\epsilon^{2}$
times.

Recently, Bonet-Monroig, Babbush, and O’Brien [Bonet-Monroig  _et
al._(2019)Bonet-Monroig, Babbush, and O’Brien] showed that if one is able to
implement a linear depth circuit on a linear array prior to measurement, then
one can directly measure the fermionic $2$-RDM using $\mathcal{O}(n^{2})$
circuits. This result, albeit different from ours, suggests the same scaling
of measurement repetitions to sample elements in fermionic RDMs on a quantum
computer. If only the ground state energy is concerned, more efficient methods
based on linear combination of unitary operators [Izmaylov  _et
al._(2020)Izmaylov, Yen, Lang, and Verteletskyi, Zhao  _et al._(2019)Zhao,
Tranter, Kirby, Ung, Miyake, and Love] and a low rank factorization of the
two-electron integral tensor [Huggins  _et al._(2019)Huggins, McClean, Rubin,
Jiang, Wiebe, Whaley, and Babbush] are recently proposed.

##  4 Conclusion

The fermionic anticommutation relation has many important implications,
including the Pauli exclusion principle and more generally the
$n$-representability problem [Mazziotti(2009)]. As a direct consequence of the
anticommutation relation, we prove a lower bound on the weights of Pauli
operators to represent single fermionic operators of an $n$-mode fermionic
system. We also constructed a fermion-to-qubit mapping based on ternary trees
that saturates this bound, where the numbers of Pauli-$x$, -$y$, and -$z$
operators are balanced. We expect the ternary-tree mapping to be a useful tool
to studying fermionic systems, such as Hubbard-like systems, on noisy and
fault-tolerant quantum computing devices.

Related to the fermion-to-qubit mapping, we discuss the measurement of
fermionic RDMs which is likely to be a bottleneck in quantum simulation of
fermions; the noncommuting feature of fermionic operators forbids one to
measure them simultaneously. The fermionic anticommutation relation again puts
a lower bound on the measurement repetitions required to determine the RDMs.
Here, we have shown that individual elements of the $k$-RDM of a fermionic
state—stored in a quantum computer with the ternary-tree mapping—can be
determined in parallel to precision $\epsilon$ by repeating a single quantum
circuit for $\lesssim(2n+1)^{k}/\epsilon^{2}$ times. In comparison, using the
Bravyi-Kitaev transformation leads to a worse exponent in the number of
repetitions, i.e., $\lesssim(n+1)^{k\log_{2}3}/\epsilon^{2}$.

These measurement results for fermions are based on a Bell-basis method we
develop here that allows for determining individual elements of all $k$-qubit
RDMs in parallel, to precision $\epsilon$, by repeating a single quantum
circuit for $\lesssim 3^{k}\epsilon^{-2}$ times, independent of the system
size. This is especially suited for quantum computers with slow circuit
updating rates, e.g., those based on FPGAs. Our scheme also saves a $\log n$
factor in circuit repetitions compared to the results by Cotler and Wilczek
[Cotler and Wilczek(2020)], at the cost of introducing extra ancilla qubits.
Another desired property of our scheme is that it is informationally complete,
allowing for reconstruction of the entire quantum state as opposed to the RDMs
up to some order $k$. We have also generalized the Bell-basis measurement
scheme to qudits using the Heisenberg-Weyl operators.

Future work includes designing fermion-to-qubit mappings on ternary trees with
varying depths of root-to-leaf paths. This is useful to problems where some of
the Majorana operators are more important and need to be sampled more often.
It is desirable to map these operators to Pauli operators with less weights,
corresponding to low-depth paths in the tree. Another interesting line of
research is to combine the ternary-tree mapping with quantum error-correcting
codes by introducing redundant qubits [Steudtner and Wehner(2019), Setia and
Whitfield(2018), Jiang  _et al._(2019)Jiang, McClean, Babbush, and Neven].

After completion of this work, we became aware of the work by Vlasov
[Vlasov(2019)], and we thank the author for bringing his work to our
attention. We would like to thank Sergio Boixo, Yu-An Chen, Sam McArdle,
Jarrod McClean, Tom O’Brien, Nick Rubin, Kevin Sung, and Vadim Smelyanskiy for
fruitful discussions. Special thanks to Ryan Babbush for describing the
problem and the beautiful results he and collaborators found during a surfing
trip. AK acknowledges the support from the US Department of Defense and the
support from the AFOSR MURI project “Scalable Certification of Quantum
Computing Devices and Networks.”

## References

  * [Feynman(1982)] R. P. Feynman, “Simulating physics with computers,” International Journal of Theoretical Physics 21, 467 (1982).
  * [Lloyd(1996)] S. Lloyd, “Universal Quantum Simulators,” Science 273, 1073 (1996).
  * [Georgescu  _et al._(2014)Georgescu, Ashhab, and Nori] I. Georgescu, S. Ashhab, and F. Nori, “Quantum simulation,” Reviews of Modern Physics 86, 153 (2014).
  * [Wecker  _et al._(2015)Wecker, Hastings, Wiebe, Clark, Nayak, and Troyer] D. Wecker, M. B. Hastings, N. Wiebe, B. K. Clark, C. Nayak, and M. Troyer, “Solving strongly correlated electron models on a quantum computer,” Physical Review A 92, 062318 (2015).
  * [Babbush  _et al._(2018)Babbush, Wiebe, McClean, McClain, Neven, and Chan] R. Babbush, N. Wiebe, J. McClean, J. McClain, H. Neven, and G. K.-L. Chan, “Low-Depth Quantum Simulation of Materials,” Physical Review X 8, 011044 (2018).
  * [Jiang  _et al._(2018)Jiang, Sung, Kechedzhi, Smelyanskiy, and Boixo] Z. Jiang, K. J. Sung, K. Kechedzhi, V. N. Smelyanskiy, and S. Boixo, “Quantum Algorithms to Simulate Many-Body Physics of Correlated Fermions,” Physical Review Applied 9, 044036 (2018).
  * [Cirac and Zoller(1995)] J. I. Cirac and P. Zoller, “Quantum computations with cold trapped ions,” Physical Review Letters 74, 4091 (1995).
  * [Kielpinski  _et al._(2002)Kielpinski, Monroe, and Wineland] D. Kielpinski, C. Monroe, and D. J. Wineland, “Architecture for a large-scale ion-trap quantum computer,” Nature 417, 709 (2002).
  * [Häffner  _et al._(2008)Häffner, Roos, and Blatt] H. Häffner, C. F. Roos, and R. Blatt, “Quantum computing with trapped ions,” Physics Reports 469, 155 (2008).
  * [Devoret  _et al._(2004)Devoret, Wallraff, and Martinis] M. H. Devoret, A. Wallraff, and J. M. Martinis, “Superconducting Qubits: A Short Review,” arXiv:0411174 (2004).
  * [Wendin(2017)] G. Wendin, “Quantum information processing with superconducting circuits: a review,” Reports on Progress in Physics. Physical Society (Great Britain) 80, 106001 (2017).
  * [Peruzzo  _et al._(2014)Peruzzo, McClean, Shadbolt, Yung, Zhou, Love, Aspuru-Guzik, and O’ Brien] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’ Brien, “A variational eigenvalue solver on a photonic quantum processor,” Nature Communications 5, 4213 (2014).
  * [McClean  _et al._(2016)McClean, Romero, Babbush, and Aspuru-Guzik] J. R. McClean, J. Romero, R. Babbush, and A. Aspuru-Guzik, “The theory of variational hybrid quantum-classical algorithms,” New Journal of Physics 18, 023023 (2016).
  * [Nielsen(2005)] M. A. Nielsen, “The Fermionic canonical commutation relations and the Jordan-Wigner transform,” Tech. Rep. University of Queensland (2005).
  * [Seeley  _et al._(2012)Seeley, Richard, and Love] J. T. Seeley, M. J. Richard, and P. J. Love, “The Bravyi-Kitaev transformation for quantum computation of electronic structure,” The Journal of Chemical Physics 137, 224109 (2012).
  * [Bravyi and Kitaev(2002)] S. B. Bravyi and A. Y. Kitaev, “Fermionic Quantum Computation,” Annals of Physics 298, 210 (2002).
  * [Tranter  _et al._(2015)Tranter, Sofia, Seeley, Kaicher, McClean, Babbush, Coveney, Mintert, Wilhelm, and Love] A. Tranter, S. Sofia, J. Seeley, M. Kaicher, J. McClean, R. Babbush, P. V. Coveney, F. Mintert, F. Wilhelm, and P. J. Love, “The Bravyi-Kitaev transformation: Properties and applications,” International Journal of Quantum Chemistry 115, 1431 (2015).
  * [Havlíček  _et al._(2017)Havlíček, Troyer, and Whitfield] V. Havlíček, M. Troyer, and J. D. Whitfield, “Operator locality in the quantum simulation of fermionic models,” Physical Review A 95, 032332 (2017).
  * [Arute  _et al._(2019)Arute, Arya, Babbush, Bacon, Bardin, Barends, Biswas, Boixo, Brandao, Buell, Burkett, Chen, Chen, Chiaro, Collins, Courtney, Dunsworth, Farhi, Foxen, Fowler, Gidney, Giustina, Graff, Guerin, Habegger, Harrigan, Hartmann, Ho, Hoffmann, Huang, Humble, Isakov, Jeffrey, Jiang, Kafri, Kechedzhi, Kelly, Klimov, Knysh, Korotkov, Kostritsa, Landhuis, Lindmark, Lucero, Lyakh, Mandr??, McClean, McEwen, Megrant, Mi, Michielsen, Mohseni, Mutus, Naaman, Neeley, Neill, Niu, Ostby, Petukhov, Platt, Quintana, Rieffel, Roushan, Rubin, Sank, Satzinger, Smelyanskiy, Sung, Trevithick, Vainsencher, Villalonga, White, Yao, Yeh, Zalcman, Neven, and Martinis] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandr??, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505 (2019).
  * [Vlasov(2019)] A. Y. Vlasov, “Clifford algebras, Spin groups and qubit trees,” arXiv:1904.09912 (2019).
  * [Nielsen and Chuang(2000)] M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information_ , 1st ed. (Cambridge University Press, 2000).
  * [Sharma  _et al._(2008)Sharma, Dewhurst, Lathiotakis, and Gross] S. Sharma, J. K. Dewhurst, N. N. Lathiotakis, and E. K. U. Gross, “Reduced density matrix functional for many-electron systems,” Physical Review B 78, 201103 (2008).
  * [Fagotti and Essler(2013)] M. Fagotti and F. H. L. Essler, “Reduced density matrix after a quantum quench,” Physical Review B 87, 245107 (2013).
  * [Rubin  _et al._(2018)Rubin, Babbush, and McClean] N. C. Rubin, R. Babbush, and J. McClean, “Application of fermionic marginal constraints to hybrid quantum algorithms,” New Journal of Physics 20, 053020 (2018).
  * [Gidofalvi and Mazziotti(2007)] G. Gidofalvi and D. A. Mazziotti, “Molecular properties from variational reduced-density-matrix theory with three-particle N-representability conditions,” The Journal of Chemical Physics 126, 024105 (2007).
  * [Overy  _et al._(2014)Overy, Booth, Blunt, Shepherd, Cleland, and Alavi] C. Overy, G. H. Booth, N. S. Blunt, J. J. Shepherd, D. Cleland, and A. Alavi, “Unbiased reduced density matrices and electronic properties from full configuration interaction quantum Monte Carlo,” The Journal of Chemical Physics 141, 244117 (2014).
  * [O’Brien  _et al._(2019)O’Brien, Senjean, Sagastizabal, Bonet-Monroig, Dutkiewicz, Buda, DiCarlo, and Visscher] T. E. O’Brien, B. Senjean, R. Sagastizabal, X. Bonet-Monroig, A. Dutkiewicz, F. Buda, L. DiCarlo, and L. Visscher, “Calculating energy derivatives for quantum chemistry on a quantum computer,” npj Quantum Information 5, 1 (2019).
  * [McClean  _et al._(2017)McClean, Kimchi-Schwartz, Carter, and de Jong] J. R. McClean, M. E. Kimchi-Schwartz, J. Carter, and W. A. de Jong, “Hybrid quantum-classical hierarchy for mitigation of decoherence and determination of excited states,” Physical Review A 95, 042308 (2017).
  * [Takeshita  _et al._(2020)Takeshita, Rubin, Jiang, Lee, Babbush, and McClean] T. Takeshita, N. C. Rubin, Z. Jiang, E. Lee, R. Babbush, and J. R. McClean, “Increasing the Representation Accuracy of Quantum Simulations of Chemistry without Extra Quantum Resources,” Physical Review X 10, 011004 (2020).
  * [Cotler and Wilczek(2020)] J. Cotler and F. Wilczek, “Quantum Overlapping Tomography,” Physical Review Letters 124, 100401 (2020).
  * [Bonet-Monroig  _et al._(2019)Bonet-Monroig, Babbush, and O’Brien] X. Bonet-Monroig, R. Babbush, and T. E. O’Brien, “Nearly optimal measurement scheduling for partial tomography of quantum states,” arXiv:1908.05628 (2019).
  * [Řeháček  _et al._(2004)Řeháček, Englert, and Kaszlikowski] J. Řeháček, B.-G. Englert, and D. Kaszlikowski, “Minimal qubit tomography,” Phys. Rev. A 70, 052321 (2004).
  * [Hamamura and Imamichi(2019)] I. Hamamura and T. Imamichi, “Efficient evaluation of quantum observables using entangled measurements,” arXiv:1909.09119 (2019).
  * [Izmaylov  _et al._(2020)Izmaylov, Yen, Lang, and Verteletskyi] A. F. Izmaylov, T.-C. Yen, R. A. Lang, and V. Verteletskyi, “Unitary Partitioning Approach to the Measurement Problem in the Variational Quantum Eigensolver Method,” Journal of Chemical Theory and Computation 16, 190 (2020).
  * [Zhao  _et al._(2019)Zhao, Tranter, Kirby, Ung, Miyake, and Love] A. Zhao, A. Tranter, W. M. Kirby, S. F. Ung, A. Miyake, and P. Love, “Measurement reduction in variational quantum algorithms,” arXiv:1908.08067 (2019).
  * [Huggins  _et al._(2019)Huggins, McClean, Rubin, Jiang, Wiebe, Whaley, and Babbush] W. J. Huggins, J. McClean, N. Rubin, Z. Jiang, N. Wiebe, K. B. Whaley, and R. Babbush, “Efficient and Noise Resilient Measurements for Quantum Chemistry on Near-Term Quantum Computers,” arXiv:1907.13117 (2019).
  * [Mazziotti(2009)] D. A. Mazziotti, ed.,  _Reduced-Density-Matrix Mechanics: With Application to Many-Electron Atoms and Molecules_ (Wiley-Interscience, 2009).
  * [Steudtner and Wehner(2019)] M. Steudtner and S. Wehner, “Quantum codes for quantum simulation of fermions on a square lattice of qubits,” Physical Review A 99, 022308 (2019).
  * [Setia and Whitfield(2018)] K. Setia and J. D. Whitfield, “Bravyi-Kitaev Superfast simulation of electronic structure on a quantum computer,” The Journal of Chemical Physics 148, 164104 (2018).
  * [Jiang  _et al._(2019)Jiang, McClean, Babbush, and Neven] Z. Jiang, J. McClean, R. Babbush, and H. Neven, “Majorana Loop Stabilizer Codes for Error Mitigation in Fermionic Quantum Simulations,” Physical Review Applied 12, 064041 (2019).
  * [Fuchs  _et al._(2017)Fuchs, Hoang, and Stacey] C. A. Fuchs, M. C. Hoang, and B. C. Stacey, “The SIC question: History and state of play,” Axioms 6, 21 (2017).
  * [Dang  _et al._(2013)Dang, Blanchfield, Bengtsson, and Appleby] H. B. Dang, K. Blanchfield, I. Bengtsson, and D. M. Appleby, “Linear dependencies in Weyl–Heisenberg orbits,” Quantum Information Processing 12, 3449 (2013).

##  Appendix A The informational completeness of the Bell-basis measurement
and its implementation

In this Appendix, we prove that the Bell-basis measurement scheme introduced
in Sec. 3 implements a symmetric informationally complete (SIC) POVM for
qubits.

######  Theorem 2.

If $\operatorname{Tr}(\sigma^{\alpha}\xi)\neq 0$ for $\alpha=x,y,z$, our
procedure is informationally complete for $\rho$ in the limit of infinite
number of measurement repetitions, i.e., $\rho$ can be constructed from the
measurement outcomes.

###### Proof.

The Bell basis

$\displaystyle\lvert\hskip 0.4pt\Phi^{\pm}\hskip
0.4pt\rangle=\frac{1}{\sqrt{2}}\Big{(}\lvert\hskip 0.4pt0\hskip
0.4pt\rangle\otimes\lvert\hskip 0.4pt0\hskip 0.4pt\rangle\pm\lvert\hskip
0.4pt1\hskip 0.4pt\rangle\otimes\lvert\hskip 0.4pt1\hskip
0.4pt\rangle\Big{)}\,,$ (18) $\displaystyle\lvert\hskip 0.4pt\Psi^{\pm}\hskip
0.4pt\rangle=\frac{1}{\sqrt{2}}\Big{(}\lvert\hskip 0.4pt0\hskip
0.4pt\rangle\otimes\lvert\hskip 0.4pt1\hskip 0.4pt\rangle\pm\lvert\hskip
0.4pt1\hskip 0.4pt\rangle\otimes\lvert\hskip 0.4pt0\hskip
0.4pt\rangle\Big{)}\,.$ (19)

is a common eigenbasis of $\sigma^{x}\otimes\sigma^{x}$,
$\sigma^{y}\otimes\sigma^{y}$, and $\sigma^{z}\otimes\sigma^{z}$. Therefore,
in the limit of infinite number of measurement repetitions, for any
$k\in[1,n]$, $\alpha_{i}=x,y,z$ and $j_{i}\in[1,n]$ ($j_{i}\neq
j_{i^{\prime}}$ for $i\neq i^{\prime}$, $i,i^{\prime}=1,\ldots,k$), using the
procedure described in the main text we can calculate the $2k$-body
correlation function
$\operatorname{Tr}(\sigma^{\alpha_{1}}_{j_{1}}\otimes\sigma^{\alpha_{1}}_{j^{\prime}_{1}}\cdots\sigma^{\alpha_{k}}_{j_{k}}\otimes\sigma^{\alpha_{k}}_{j^{\prime}_{k}}\rho\otimes\xi^{\otimes
n})$ which equals to
$\operatorname{Tr}(\sigma^{\alpha_{1}}_{j_{1}}\cdots\sigma^{\alpha_{k}}_{j_{k}}\rho)\prod_{i=1}^{k}\operatorname{Tr}(\sigma^{\alpha_{i}}_{j^{\prime}_{i}}\xi)$.
Since we assumed $\xi$ is known and $\operatorname{Tr}(\sigma^{\alpha}\xi)\neq
0$ for $\alpha=x,y,z$, we can write

$\displaystyle\rho^{\alpha_{1},\ldots,\alpha_{k}}_{j_{1},\ldots,j_{k}}$
$\displaystyle=\operatorname{Tr}(\sigma^{\alpha_{1}}_{j_{1}}\cdots\sigma^{\alpha_{k}}_{j_{k}}\rho)$
(20)
$\displaystyle=\frac{\operatorname{Tr}(\sigma^{\alpha_{1}}_{j_{1}}\otimes\sigma^{\alpha_{1}}_{j^{\prime}_{1}}\cdots\sigma^{\alpha_{k}}_{j_{k}}\otimes\sigma^{\alpha_{k}}_{j^{\prime}_{k}}\rho\otimes\xi^{\otimes
n})}{\prod_{i=1}^{k}\operatorname{Tr}(\sigma^{\alpha_{i}}_{j^{\prime}_{i}}\xi)}\,.$
(21)

∎

The SIC POVM on a qubit is a collection of four outcomes (POVM elements)
$E_{i}=\frac{1}{2}\lvert\hskip 0.4pt\psi_{i}\hskip 0.4pt\rangle\langle\hskip
0.4pt\psi_{i}\hskip 0.4pt\rvert$, $i=1,\ldots,4$, such that

$\displaystyle|\langle\,\psi_{i}\,|\,\psi_{j}\,\rangle|^{2}=\frac{2\delta_{i,j}+1}{3}\,.$
(22)

We now show that, following Neumark’s theorem it can be implemented by
attaching an ancilla qubit in a state
$\xi=\frac{1}{2}(\mathbbm{1}+\frac{1}{\sqrt{3}}(\sigma_{x}+\sigma_{y}+\sigma_{z}))$
and measuring the two qubits in the Bell-basis.

In the Bell-basis measurement, the probability to obtain the outcome that
corresponds to $\Phi^{+}$ is:

$\displaystyle\langle\hskip 0.4pt\Phi^{+}\hskip
0.4pt\rvert\rho\otimes\xi\lvert\hskip 0.4pt\Phi^{+}\hskip 0.4pt\rangle$
$\displaystyle=\frac{1}{2}\Big{(}\langle\hskip 0.4pt0\hskip
0.4pt\rvert\rho\lvert\hskip 0.4pt0\hskip 0.4pt\rangle\langle\hskip
0.4pt0\hskip 0.4pt\rvert\xi\lvert\hskip 0.4pt0\hskip
0.4pt\rangle+\langle\hskip 0.4pt0\hskip 0.4pt\rvert\rho\lvert\hskip
0.4pt1\hskip 0.4pt\rangle\langle\hskip 0.4pt0\hskip 0.4pt\rvert\xi\lvert\hskip
0.4pt1\hskip 0.4pt\rangle+\langle\hskip 0.4pt1\hskip
0.4pt\rvert\rho\lvert\hskip 0.4pt0\hskip 0.4pt\rangle\langle\hskip
0.4pt1\hskip 0.4pt\rvert\xi\lvert\hskip 0.4pt0\hskip
0.4pt\rangle+\langle\hskip 0.4pt1\hskip 0.4pt\rvert\rho\lvert\hskip
0.4pt1\hskip 0.4pt\rangle\langle\hskip 0.4pt1\hskip 0.4pt\rvert\xi\lvert\hskip
0.4pt1\hskip 0.4pt\rangle\Big{)}\,.$ (23)

Therefore the POVM element on the system qubit which corresponds to the
$\Phi^{+}$ outcome is

$\displaystyle E_{\Phi^{+}}$ $\displaystyle=\frac{1}{2}\Big{(}\langle\hskip
0.4pt0\hskip 0.4pt\rvert\xi\lvert\hskip 0.4pt0\hskip 0.4pt\rangle\lvert\hskip
0.4pt0\hskip 0.4pt\rangle\langle\hskip 0.4pt0\hskip 0.4pt\rvert+\langle\hskip
0.4pt0\hskip 0.4pt\rvert\xi\lvert\hskip 0.4pt1\hskip 0.4pt\rangle\lvert\hskip
0.4pt1\hskip 0.4pt\rangle\langle\hskip 0.4pt0\hskip 0.4pt\rvert+\langle\hskip
0.4pt0\hskip 0.4pt\rvert\xi\lvert\hskip 0.4pt1\hskip 0.4pt\rangle\lvert\hskip
0.4pt1\hskip 0.4pt\rangle\langle\hskip 0.4pt0\hskip 0.4pt\rvert+\langle\hskip
0.4pt1\hskip 0.4pt\rvert\xi\lvert\hskip 0.4pt1\hskip 0.4pt\rangle\lvert\hskip
0.4pt1\hskip 0.4pt\rangle\langle\hskip 0.4pt1\hskip
0.4pt\rvert\Big{)}=\frac{\xi}{2}\,.$ (24)

Similarly we find,

$\displaystyle E_{\Phi^{-}}$ $\displaystyle=\frac{1}{2}\sigma^{z}\xi\hskip
0.4pt\sigma^{z}\,,$ (25) $\displaystyle E_{\Psi^{+}}$
$\displaystyle=\frac{1}{2}\sigma^{x}\xi\hskip 0.4pt\sigma^{x}\,,$ (26)
$\displaystyle E_{\Psi^{-}}$ $\displaystyle=\frac{1}{2}\sigma^{y}\xi\hskip
0.4pt\sigma^{y}\,.$ (27)

Note that $\xi$ is a pure state and therefore so are
$\sigma^{x}\xi\sigma^{x}$, $\sigma^{y}\xi\sigma^{y}$, and
$\sigma^{z}\xi\sigma^{z}$. To see that
$\\{E_{\Phi^{+}},E_{\Phi^{-}},E_{\Psi^{+}},E_{\Psi^{-}}\\}$ forms a SIC POVM
on a qubit, one can verify explicitly that for $\alpha\neq\beta=0,x,y,z$
$\operatorname{Tr}(\sigma^{\alpha}\xi\sigma^{\alpha}\sigma^{\beta}\xi\sigma^{\beta})=\frac{1}{3}$
where $\sigma^{0}=\mathbbm{1}$.

The implementation of the tetrahedron measurement on a qubit using the Bell-
basis measurement points at a deep connection between dense coding and SIC
POVM of a qubit. More explicitly, the protocol of dense coding is based on the
relations

$\displaystyle\lvert\hskip 0.4pt\Phi^{+}\hskip 0.4pt\rangle$
$\displaystyle=\mathbbm{1}\otimes\mathbbm{1}\lvert\hskip 0.4pt\Phi^{+}\hskip
0.4pt\rangle\,,$ (28) $\displaystyle\lvert\hskip 0.4pt\Phi^{-}\hskip
0.4pt\rangle$ $\displaystyle=\mathbbm{1}\otimes\sigma^{z}\lvert\hskip
0.4pt\Phi^{+}\hskip 0.4pt\rangle\,,$ (29) $\displaystyle\lvert\hskip
0.4pt\Psi^{+}\hskip 0.4pt\rangle$
$\displaystyle=\mathbbm{1}\otimes\sigma^{x}\lvert\hskip 0.4pt\Phi^{+}\hskip
0.4pt\rangle\,,$ (30) $\displaystyle\lvert\hskip 0.4pt\Psi^{-}\hskip
0.4pt\rangle$
$\displaystyle=\mathbbm{1}\otimes\sigma^{x}\sigma^{z}\lvert\hskip
0.4pt\Phi^{+}\hskip 0.4pt\rangle=\mathbbm{1}\otimes\sigma^{y}\lvert\hskip
0.4pt\Phi^{+}\hskip 0.4pt\rangle\,.$ (31)

These relations allow us to write Eqs. (24)-(27), which has the structure of
Heisenberg-Weyl (HW) group covariant SIC POVMs. Upon fixing $\xi$ to be a
fiducial state of the HW group SIC POVM, as we do above, we recover the
tetrahedron measurement.

##  Appendix B Generalization of RDM measurement scheme to qudits

In this appendix, we generalize the scheme introduced in Sec. 3 to $n$-qudit
systems, i.e., collections of $D$-level spin systems. We prove that our scheme
is informationally completely and can be implemented using the generalized
Bell basis. Consider the Heisenberg-Weyl (HW) shift and phase (clock)
operators,

$\displaystyle X\lvert\hskip 0.4ptd\hskip 0.4pt\rangle=\lvert\hskip
0.4ptd\oplus 1\hskip 0.4pt\rangle\,,\quad Z\lvert\hskip 0.4ptd\hskip
0.4pt\rangle=e^{\frac{2\pi id}{D}}\lvert\hskip 0.4ptd\hskip 0.4pt\rangle\,,$
(32)

where $d=0,\ldots,D-1$ and $\oplus$ is addition modulo $D$ ($\ominus$ for
modular subtraction). They obey the HW commutation relation $XZ=e^{\frac{2\pi
i}{D}}ZX$. Similarly to the Pauli operators on a qubit, the HW operators
generate a complete operator basis acting on the $D$-dimensional Hilbert
space. In particular, a density matrix $\rho$ of a qubit can be expressed as

$\displaystyle\rho=\frac{1}{D}\bigg{(}\mathbbm{1}+\sum_{f\land g\neq
0}^{D-1}\rho^{f\hskip 0.4ptg}X^{f}Z^{g}\bigg{)}\,,$ (33)

where $\rho^{f\hskip 0.4ptg}=\operatorname{Tr}(Z^{-g}X^{-f}\rho)$ are the
expansion coefficients. Similarly, given an $n$-qudit density matrix $\rho$, a
$k$-qudit RDM can be written as

$\displaystyle\operatorname{Tr}_{\begin{subarray}{c}\neq
j_{1},\ldots,j_{k}\end{subarray}}\big{(}\rho\big{)}$
$\displaystyle=\frac{1}{D^{k}}\sum_{f_{1},g_{1}\ldots,f_{k},g_{k}=0}^{D-1}\rho^{f_{1}g_{1},\ldots,f_{k}g_{k}}_{j_{1},\ldots,j_{k}}\operatorname*{\text{\raisebox{1.07639pt}{\scalebox{0.8}{$\bigotimes$}}}}_{i=1}^{k}X^{f_{i}}_{j_{i}}Z^{g_{i}}_{j_{i}}\,,$
(34)

where $X^{f_{i}}_{j_{i}}Z^{g_{i}}_{j_{i}}$ are the HW operators on the
$j_{i}$-th qudit, and

$\displaystyle\rho^{f_{1}g_{1},\ldots,f_{k}g_{k}}_{j_{1},\ldots,j_{k}}=\operatorname{Tr}\bigg{(}\rho\,\operatorname*{\text{\raisebox{1.07639pt}{\scalebox{0.8}{$\bigotimes$}}}}_{i=1}^{k}X^{f_{i}}_{j_{i}}Z^{g_{i}}_{j_{i}}\bigg{)}\,,$
(35)

By measuring the above correlation functions for all
$f_{1},h_{1}\ldots,f_{k},h_{k}$ and all $j_{1},\ldots,j_{k}$ we can determine
all $k$-qudit RDMs.

While the HW operators on a qudit are not commute or anticommute as the Pauli
operators on a qubit, nevertheless, we can measure all the required
correlation functions with a single quantum circuit, as we describe below.
Consider the generalization of the Bell-basis to qudits,

$\displaystyle\lvert\hskip 0.4pt\Phi_{h\ell}\hskip 0.4pt\rangle$
$\displaystyle=\mathbbm{1}\otimes X^{h}Z^{\ell}\,\lvert\hskip
0.4pt\Phi_{00}\hskip
0.4pt\rangle=Z^{\ell}X^{-h}\otimes\mathbbm{1}\,\lvert\hskip
0.4pt\Phi_{00}\hskip 0.4pt\rangle\,,$ (36)

where

$\displaystyle\lvert\hskip 0.4pt\Phi_{00}\hskip
0.4pt\rangle=\frac{1}{\sqrt{D}}\>\sum_{d=0}^{D-1}\>\lvert\hskip 0.4ptd\hskip
0.4pt\rangle\otimes\lvert\hskip 0.4ptd\hskip 0.4pt\rangle\,.$ (37)

Following the HW commutation relation we obtain,

$\displaystyle\langle\,\Phi_{h\ell}\,|\,\Phi_{h^{\prime}\ell^{\prime}}\,\rangle$
$\displaystyle=\langle\hskip 0.4pt\Phi_{00}\hskip
0.4pt\rvert\mathbbm{1}\otimes(X^{h}Z^{\ell})^{\dagger}X^{h^{\prime}}Z^{\ell^{\prime}}\lvert\hskip
0.4pt\Phi_{00}\hskip 0.4pt\rangle$ (38)
$\displaystyle=\delta_{\ell,\ell^{\prime}}\,\delta_{h,h^{\prime}}\,,$ (39)

where the $\delta_{\ell,\ell^{\prime}}=1$ if $\ell\ominus\ell^{\prime}=0$ and
$\delta_{\ell,\ell^{\prime}}=0$ otherwise (and similarly for
$\delta_{h,h^{\prime}}$). Therefore, the set $\\{\lvert\hskip
0.4pt\Phi_{h\ell}\hskip 0.4pt\rangle:h,\ell=0,\ldots,D-1\\}$ form an
orthonormal basis for two qudits. It is the eigenbasis of the operators
$X^{f}Z^{g}\otimes X^{f}Z^{-g}$ for $f,g=0,\ldots,D-1$,

$\displaystyle X^{f}Z^{g}\otimes X^{f}Z^{-g}\,\lvert\hskip
0.4pt\Phi_{h\ell}\hskip 0.4pt\rangle=e^{2\pi i\,(gh-f\ell)/D}\,\lvert\hskip
0.4pt\Phi_{h\ell}\hskip 0.4pt\rangle\,.$ (40)

Hence, measuring these mutually-commuting operators in the generalized Bell
basis (36) reveals their values simultaneously.

Similar to the qubit case, one can estimate elements in all $k$-qudit RDMs
with error $\epsilon$ by repeating the following steps for
$(D+1)^{k}/\epsilon^{2}$ times:

  1. 1.

To each system qudit (labeled by $j$) attach an ancillary qudit (labelled by
$j^{\prime}$) in a known state $\xi$, so that the total system-ancilla state
is $\rho\otimes\xi^{\otimes n}$.

  2. 2.

Measure each pair of qudits $(j,j^{\prime})$ in the common eigenbasis of
$X^{f}Z^{g}\otimes X^{f}Z^{-g}$, i.e., the generalized Bell basis.

By choosing a qudit ancilla state $\xi$ such that

$\displaystyle\operatorname{Tr}\Big{(}X^{f_{i}}_{j^{\prime}_{i}}Z^{-g_{i}}_{j^{\prime}_{i}}\xi\Big{)}=\frac{1}{\sqrt{D+1}}\,,$
(41)

we obtain

$\displaystyle\rho^{f_{1}g_{1},\ldots,f_{k}g_{k}}_{j_{1},\ldots,j_{k}}=\frac{\operatorname{Tr}\Big{(}\rho\otimes\xi^{\otimes
n}\prod_{i=1}^{k}X^{f_{i}}_{j_{i}}Z^{g_{i}}_{j_{i}}\otimes
X^{f_{i}}_{j^{\prime}_{i}}Z^{-g_{i}}_{j^{\prime}_{i}}\Big{)}}{\sqrt{D+1}^{\,k}}\,.$
(42)

Such states $\xi$ are known in various dimensions and believed to exist in
every dimension. For example, analytic solutions are known for dimensions
2-24, 28, 30, 31, 35, 37, 39, 43, 48, 124, and numerical solutions are known
in all dimensions up to and including 151 [Fuchs  _et al._(2017)Fuchs, Hoang,
and Stacey]. The last equation implies that to obtain a fixed standard-
deviation error $\epsilon$ in the measured quantities we must run the
experiment $(D+1)^{k}\hskip 0.4pt/\epsilon^{2}$ times, independently of $n$.
In Apps. A, we show that this measurement scheme implements a SIC POVM on a
qudit.

For example, for a qutrit (three-dimensional system) the pure state
$\psi=\frac{1}{\sqrt{2}}(0,1,-1)$ is known to be a fiducial state of the HW
group covariant SIC POVM [Dang  _et al._(2013)Dang, Blanchfield, Bengtsson,
and Appleby]. For the proposed protocol to success we only require that
$\big{\lvert}\operatorname{Tr}(X^{f_{i}}_{j^{\prime}_{i}}Z^{-g_{i}}_{j^{\prime}_{i}}\xi)\big{\rvert}\geq\delta$.
The parameter $\delta$ determines the number of total measurement rounds in
the protocol. Therefore, for dimensions where the HW group covariant SIC POVMs
are unknown or if we are only required to estimate specific correlation
functions we can replace the condition (41) with a less stringent one.

######  Theorem 3.

If $\operatorname{Tr}(X^{f}Z^{-g}\xi)\neq 0$ for $f,g=0,\ldots,D-1$, then in
the limit of infinite number measurement repetitions the above procedure is
informationally complete for $\rho$.

###### Proof.

Since the generalized Bell basis is a common eigenbasis of $X^{f}Z^{g}\otimes
X^{f}Z^{-g}$, for infinite number measurement repetitions, for any
$k\in[1,n]$, $f,g=0,\ldots,D-1$ and $j_{i}\in[1,n]$ ($j_{i}\neq
j_{i^{\prime}}$ for $i\neq i^{\prime}$, $i,i^{\prime}=1,\ldots,k$), using the
above procedure we can calculate the $2k$-body correlation function
$\operatorname{Tr}\big{(}X^{f_{1}}_{j_{1}}Z^{g_{1}}_{j_{1}}\otimes
X^{f_{1}}_{j^{\prime}_{1}}Z^{-g_{1}}_{j^{\prime}_{1}}\cdots
X^{f_{k}}_{j_{k}}Z^{g_{k}}_{j_{k}}\otimes
X^{f_{k}}_{j^{\prime}_{k}}Z^{-g_{k}}_{j^{\prime}_{k}}\rho\otimes\xi^{\otimes
n}\big{)}$ which equals to
$\operatorname{Tr}\big{(}X^{f_{1}}_{j_{1}}Z^{g_{1}}_{j_{1}}\cdots
X^{f_{k}}_{j_{k}}Z^{g_{k}}_{j_{k}}\rho\big{)}\prod_{i=1}^{k}\operatorname{Tr}\big{(}X^{f_{i}}_{j^{\prime}_{i}}Z^{-g_{i}}_{j^{\prime}_{i}}\xi\big{)}$.
Since we assumed $\xi$ is known and
$\operatorname{Tr}\big{(}X^{f_{i}}_{j^{\prime}_{i}}Z^{-g_{i}}_{j^{\prime}_{i}}\xi\big{)}\neq
0$ for $f_{i},g_{i}=0,\ldots,D-1$, we can write

$\displaystyle\rho^{f_{1},h_{1}\ldots,f_{k},h_{k}}_{j_{1},\ldots,j_{k}}=\operatorname{Tr}\big{(}X^{f_{1}}_{j_{1}}Z^{g_{1}}_{j_{1}}\cdots
X^{f_{k}}_{j_{k}}Z^{g_{k}}_{j_{k}}\rho\big{)}$ (43)
$\displaystyle=\frac{\operatorname{Tr}\big{(}X^{f_{1}}_{j_{1}}Z^{g_{1}}_{j_{1}}\otimes
X^{f_{1}}_{j^{\prime}_{1}}Z^{-g_{1}}_{j^{\prime}_{1}}\cdots
X^{f_{k}}_{j_{k}}Z^{g_{k}}_{j_{k}}\otimes
X^{f_{k}}_{j^{\prime}_{k}}Z^{-g_{k}}_{j^{\prime}_{k}}\rho\otimes\xi^{\otimes
n}\big{)}}{\prod_{i=1}^{k}\operatorname{Tr}\big{(}X^{f_{i}}_{j^{\prime}_{i}}Z^{-g_{i}}_{j^{\prime}_{i}}\xi\big{)}}\,.$
(44)

This completes the proof. ∎

The SIC POVM on a qudit, a $D$-dimensional Hilbert space, is a collection of
$D^{2}$ POVM elements $E_{i}=\frac{1}{D}\lvert\hskip 0.4pt\psi_{i}\hskip
0.4pt\rangle\langle\hskip 0.4pt\psi_{i}\hskip 0.4pt\rvert$,
$i=1,\ldots,D^{2}$, such that

$\displaystyle|\langle\,\psi_{i}\,|\,\psi_{j}\,\rangle|^{2}=\frac{D\delta_{i,j}+1}{D+1}\,.$
(45)

We now show that, following Neumark’s theorem it can be implemented by
attaching an ancilla qudit is a state $\xi$ (to be determined later) and
measuring the two qudits in a generalized Bell-basis.

Consider the following generalization of the Bell-basis to qudits. We define,

$\displaystyle\lvert\hskip 0.4pt\Phi_{h\ell}\hskip
0.4pt\rangle=\mathbbm{1}\otimes
X^{h}Z^{\ell}\;\bigg{(}\frac{1}{\sqrt{D}}\sum_{d=0}^{D-1}\,\lvert\hskip
0.4ptd\hskip 0.4pt\rangle\otimes\lvert\hskip 0.4ptd\hskip
0.4pt\rangle\bigg{)}=X^{h}Z^{\ell}\otimes\mathbbm{1}\;\bigg{(}\frac{1}{\sqrt{D}}\sum_{d=0}^{D-1}\,\lvert\hskip
0.4ptd\hskip 0.4pt\rangle\otimes\lvert\hskip 0.4ptd\hskip
0.4pt\rangle\bigg{)}\,,$ (46)

where $X$ and $Z$ are the HW shift and phase (clock) operators, respectively,

$\displaystyle X\lvert\hskip 0.4ptd\hskip 0.4pt\rangle=\lvert\hskip
0.4ptd\oplus 1\hskip 0.4pt\rangle\,,\quad Z\lvert\hskip 0.4ptd\hskip
0.4pt\rangle=e^{i2\pi d/D}\lvert\hskip 0.4ptd\hskip 0.4pt\rangle\,,$ (47)

where $d=0,\ldots,D-1$ and $\oplus$ is addition modulo $d$. Following the HW
commutation relation,

$\displaystyle XZ=e^{i2\pi/D}ZX\,,$ (48)

we obtain,

$\displaystyle\langle\,\Phi_{h\ell}\,|\,\Phi_{h^{\prime}\ell^{\prime}}\,\rangle$
$\displaystyle=\langle\hskip 0.4pt\Phi_{00}\hskip
0.4pt\rvert\mathbbm{1}\otimes(X^{h}Z^{\ell})^{\dagger}X^{h^{\prime}}Z^{\ell^{\prime}}\lvert\hskip
0.4pt\Phi_{00}\hskip 0.4pt\rangle=\langle\hskip 0.4pt\Phi_{00}\hskip
0.4pt\rvert\mathbbm{1}\otimes
Z^{D-\ell}X^{D-h}X^{h^{\prime}}Z^{\ell^{\prime}}\lvert\hskip
0.4pt\Phi_{00}\hskip 0.4pt\rangle$ (49)
$\displaystyle=e^{i2\pi(h-h^{\prime})\ell^{\prime}/D}\langle\hskip
0.4pt\Phi_{00}\hskip 0.4pt\rvert\mathbbm{1}\otimes
Z^{\ell^{\prime}-\ell}X^{h-h^{\prime}}\lvert\hskip 0.4pt\Phi_{00}\hskip
0.4pt\rangle=\delta_{\ell,\ell^{\prime}}\,\delta_{h,h^{\prime}}\,,$ (50)

where the $\delta_{\ell,\ell^{\prime}}=1$ if $\ell\ominus\ell^{\prime}=0$ and
$\delta_{\ell,\ell^{\prime}}=0$ otherwise (and similarly for
$\delta_{h,h^{\prime}}$). therefore, the set $\\{\lvert\hskip
0.4pt\Phi_{h\ell}\hskip 0.4pt\rangle:h=0,\ldots,D-1;\ell=0,\ldots,D-1\\}$ is a
set of orthonormal basis (generalized Bell basis) on two qudits.

Following the same calculation done for two-qubit Bell measurement, it is
straight forward to check that measuring the generalized Bell basis basis on a
two-qudit state $\rho\otimes\xi$, defines an effective measurement on the
first qudit with $d^{2}$ POVM elements

$\displaystyle E_{\Phi_{h\ell}}$ $\displaystyle=\frac{1}{d}X^{h}Z^{\ell}\xi
Z^{D-\ell}X^{D-h}\,,\;\;h,\ell=0,\ldots,D-1.$ (51)

These equations define the HW group covariant SIC POVM on a qudit, when $\xi$
is its fiducial state. Finding fiducial states for HW covariant SIC POVM is an
open question, though known results exist in certain dimensions.