Quantum state tomography, the ability to deduce the state of a quantum system
from measured data, is the gold standard for verification and benchmarking of
quantum devices. It has been realized in systems with few components, but for
larger systems it becomes infeasible because the number of quantum measurements
and the amount of computation required to process them grows exponentially in
the system size. Here we show that we can do exponentially better than direct
state tomography for a wide range of quantum states, in particular those that
are well approximated by a matrix product state ansatz. We present two schemes
for tomography in 1-D quantum systems and touch on generalizations. One scheme
requires unitary operations on a constant number of subsystems, while the other
requires only local measurements together with more elaborate post-processing.
Both schemes rely only on a linear number of experimental operations and
classical postprocessing that is polynomial in the system size. A further
strength of the methods is that the accuracy of the reconstructed states can be
rigorously certified without any a priori assumptions.

通过矩阵乘积态假设，提出了两种在一维量子系统中进行量子状态重构的方案，一种方案需要对恒定数量的子系统进行幺正操作，而另一种方案只需要进行局部测量及更复杂的后处理，两种方案仅依赖于线性数量的实验操作和多项式级别的经典后处理，可以无需任何先验假设地严格证明重构状态的准确性。

高效量子态重构

Efficient quantum state tomography

We present general methods for simulating black-box Hamiltonians using
quantum walks. These techniques have two main applications: simulating sparse
Hamiltonians and implementing black-box unitary operations. In particular, we
give the best known simulation of sparse Hamiltonians with constant precision.
Our method has complexity linear in both the sparseness D (the maximum number
of nonzero elements in a column) and the evolution time t, whereas previous
methods had complexity scaling as D^4 and were superlinear in t. We also
consider the task of implementing an arbitrary unitary operation given a
black-box description of its matrix elements. Whereas standard methods for
performing an explicitly specified N x N unitary operation use O(N^2)
elementary gates, we show that a black-box unitary can be performed with
bounded error using O(N^{2/3} (log log N)^{4/3}) queries to its matrix
elements. In fact, except for pathological cases, it appears that most
unitaries can be performed with only O(sqrt{N}) queries, which is optimal.

本文提出了用量子行走模拟黑箱哈密顿量的一般方法。这些技术具有两个主要应用：模拟稀疏哈密顿量和实现黑箱酉操作。我们给出了稀疏 Hamiltonians 常数精度下最好的已知模拟方法，复杂度线性地随着稀疏矩阵的最大非零元素数 D 和演化时间 t 增长，并且我们还研究了给定黑箱描述矩阵元素的任意酉操作实现的任务。

黑盒哈密顿模拟和酉实现

Black-box Hamiltonian simulation and unitary implementation

We show that a set of gates that consists of all one-bit quantum gates (U(2))
and the two-bit exclusive-or gate (that maps Boolean values $(x,y)$ to $(x,x
\oplus y)$) is universal in the sense that all unitary operations on
arbitrarily many bits $n$ (U($2^n$)) can be expressed as compositions of these
gates. We investigate the number of the above gates required to implement other
gates, such as generalized Deutsch-Toffoli gates, that apply a specific U(2)
transformation to one input bit if and only if the logical AND of all remaining
input bits is satisfied. These gates play a central role in many proposed
constructions of quantum computational networks. We derive upper and lower
bounds on the exact number of elementary gates required to build up a variety
of two-and three-bit quantum gates, the asymptotic number required for $n$-bit
Deutsch-Toffoli gates, and make some observations about the number required for
arbitrary $n$-bit unitary operations.

该论文研究证明了所有基础一位量子门和两位 XOR 门可以作为量子通用门集，探究了构建所需的基本门数量，其中特别关注了广义的 Deutsch-Toffoli 门和任意 n 位酉操作所需门的数量。