We examine the problem of estimating the trace of a matrix $A$ when given
access to an oracle which computes $x^\dagger A x$ for an input vector $x$. We
make use of the basis vectors from a set of mutually unbiased bases, widely
studied in the field of quantum information processing, in the selection of
probing vectors $x$. This approach offers a new state of the art single shot
sampling variance while requiring only $O(\log(n))$ random bits to generate
each vector. This significantly improves on traditional methods such as
Hutchinson's and Gaussian estimators in terms of the number of random bits
required and worst case sample variance.

使用互不偏基的基向量作为寻味向量，以估计矩阵迹，要求生成每个向量仅需 O (log (n)) 个随机比特，从而显著地提高了单次采样方差，同时也改进了传统方法。

改进的随机迹估计方法：基于互不偏的基底

Improved stochastic trace estimation using mutually unbiased bases

In coin tossing two remote participants want to share a uniformly distributed
random bit. At the least in the quantum version, each participant test whether
or not the other has attempted to create a bias on this bit. It is requested
that, for b = 0,1, the probability that Alice gets bit b and pass the test is
smaller than 1/2 whatever she does, and similarly for Bob. If the bound 1/2
holds perfectly against any of the two participants, the task realised is
called an exact coin tossing. If the bound is actually $1/2 + \xi$ where the
bias $\xi$ vanishes when a security parameter m defined by the protocol
increases, the task realised is a (non exact) coin tossing. It is found here
that exact coin tossing is impossible. At the same time, an unconditionally
secure quantum protocol that realises a (non exact) coin tossing is proposed.
The protocol executes m biased quantum coin tossing procedures at the same
time. It executes the first round in each of these m procedures sequentially,
then the second rounds are executed, and so on until the end of the n
procedures. Each procedure requires 4n particles where $n \in O(\lg m)$. The
final bit x is the parity of the m random bits. The information about each of
these m bits is announced a little bit at a time which implies that the
principle used against bit commitment does not apply. The bias on x is smaller
than $1/m$. The result is discussed in the light of the impossibility result
for exact coin tossing.

本研究提出了一种不精确硬币抛掷任务的量子协议，能够在不保证精确性的前提下，实现无条件安全性。协议同时执行 m 个有偏量子硬币投掷过程，并在多个回合中逐步公开每个随机比特的信息。