In this chapter a general mathematical framework for probabilistic theories of operationally understood circuits is laid out. Circuits are comprised of operations and wires. An operation is one use of an apparatus and a wire is a diagrammatic device for showing how apertures on the apparatuses are placed next to each other. Mathematical objects are defined in terms of the circuit understood graphically. In particular, we do not think of the circuit as sitting in a background time. Circuits can be foliated by hypersurfaces comprised of sets of wires. Systems are defined to be associated with wires. A closable set of operations is defined to be one for which the probability associated with any circuit built from this set is independent both of choices on other circuits and of extra circuitry that may be added to outputs from this circuit. States can be associated with circuit fragments corresponding to preparations. These states evolve on passing through circuit fragments corresponding to transformations. The composition of transformations is treated. A number of theorems are proven including one which rules out quaternionic quantum theory. The case of locally tomographic theories (where local measurements on a systems components suffice to determine the global state) is considered. For such theories the probability can be calculated for a circuit from matrices pertaining the operations that comprise that circuit. Classical probability theory and quantum theory are exhibited as examples in this framework.
The assumption of local tomography is equivalent to the assumption that @math where @math is the number of probabilities needed to specify the state of the composite system @math and @math ( @math ) is the number needed to describe system @math ( @math ) alone (this is the content of Theorem 5 below). Theories having this property were investigated in a paper by Wootters @cite_41 (see also @cite_3 ) in 1990 who showed that they are consistent with the relation @math where @math is the number of states that can be distinguished in a single shot measurement (this was used in @cite_33 as part of the axiomatic structure).
@cite_41 @cite_33 @cite_3
2171253836 2963956175 2058583833 2766371994
Traditional quantum state tomography requires a number of measurements that grows exponentially with the number of qubits n . But using ideas from computational learning theory, we show that one can do exponentially better in a statistical setting. In particular, to predict the outcomes of most measurements drawn from an arbitrary probability distribution, one needs only a number of sample measurements that grows linearly with n . This theorem has the conceptual implication that quantum states, despite being exponentially long vectors, are nevertheless ‘reasonable’ in a learning theory sense. The theorem also has two applications to quantum computing: first, a new simulation of quantum one-way communication protocols and second, the use of trusted classical advice to verify untrusted quantum advice. We introduce the problem of *shadow tomography*: given an unknown D-dimensional quantum mixed state ρ, as well as known two-outcome measurements E1,…,EM, estimate the probability that Ei accepts ρ, to within additive error e, for each of the M measurements. How many copies of ρ are needed to achieve this, with high probability? Surprisingly, we give a procedure that solves the problem by measuring only O( e−5·log4 M·logD) copies. This means, for example, that we can learn the behavior of an arbitrary n-qubit state, on *all* accepting rejecting circuits of some fixed polynomial size, by measuring only nO( 1) copies of the state. This resolves an open problem of the author, which arose from his work on private-key quantum money schemes, but which also has applications to quantum copy-protected software, quantum advice, and quantum one-way communication. Recently, building on this work, have given a different approach to shadow tomography using semidefinite programming, which achieves a savings in computation time. The Mathematics of Computerized Tomography covers the relevant mathematical theory of the Radon transform and related transforms and also studies more practical questions such as stability, sampling, resolution, and accuracy. Quite a bit of attention is given to the derivation, analysis, and practical examination of reconstruction algorithm, for both standard problems and problems with incomplete data. We consider the problem of learning a one-hidden-layer neural network: we assume the input @math is from Gaussian distribution and the label @math , where @math is a nonnegative vector in @math with @math , @math is a full-rank weight matrix, and @math is a noise vector. We first give an analytic formula for the population risk of the standard squared loss and demonstrate that it implicitly attempts to decompose a sequence of low-rank tensors simultaneously. Inspired by the formula, we design a non-convex objective function @math whose landscape is guaranteed to have the following properties: 1. All local minima of @math are also global minima. 2. All global minima of @math correspond to the ground truth parameters. 3. The value and gradient of @math can be estimated using samples. With these properties, stochastic gradient descent on @math provably converges to the global minimum and learn the ground-truth parameters. We also prove finite sample complexity result and validate the results by simulations.