It has been shown that, for even $n$, evolving $n$ qubits according to a Hamiltonian that is the sum of pairwise interactions between the particles, can be used to exactly implement an $(n+1)$-qubit fanout gate using a particular constant-depth circuit [arXiv:quant-ph/0309163]. However, the coupling coefficients in the Hamiltonian considered in that paper are assumed to be all equal. In this paper, we generalize these results and show that for all $n$, including odd $n$, one can exactly implement an $(n+1)$-qubit parity gate and hence, equivalently in constant depth an $(n+1)$-qubit fanout gate, using a similar Hamiltonian but with unequal couplings, and we give an exact characterization of which couplings are adequate to implement fanout via the same circuit. We also investigate pairwise couplings that satisfy an inverse square law, giving necessary and sufficient criteria for implementing fanout given spatial arrangements of identical qubits in two and three dimensions subject to this law. We use our criteria to give planar arrangements of four qubits that (together with a target qubit) are adequate to implement $5$-qubit fanout.
相關內容
We describe a `discretize-then-relax' strategy to globally minimize integral functionals over functions $u$ in a Sobolev space satisfying prescribed Dirichlet boundary conditions. The strategy applies whenever the integral functional depends polynomially on $u$ and its derivatives, even if it is nonconvex. The `discretize' step uses a bounded finite-element scheme to approximate the integral minimization problem with a convergent hierarchy of polynomial optimization problems over a compact feasible set, indexed by the decreasing size $h$ of the finite-element mesh. The `relax' step employs sparse moment-SOS relaxations to approximate each polynomial optimization problem with a hierarchy of convex semidefinite programs, indexed by an increasing relaxation order $\omega$. We prove that, as $\omega\to\infty$ and $h\to 0$, solutions of such semidefinite programs provide approximate minimizers that converge in $L^p$ to the global minimizer of the original integral functional if this is unique. We also report computational experiments that show our numerical strategy works well even when technical conditions required by our theoretical analysis are not satisfied.
Given a property (graph class) $\Pi$, a graph $G$, and an integer $k$, the \emph{$\Pi$-completion} problem consists in deciding whether we can turn $G$ into a graph with the property $\Pi$ by adding at most $k$ edges to $G$. The $\Pi$-completion problem is known to be NP-hard for general graphs when $\Pi$ is the property of being a proper interval graph (PIG). In this work, we study the PIG-completion problem %when $\Pi$ is the class of proper interval graphs (PIG) within different subclasses of chordal graphs. We show that the problem remains NP-complete even when restricted to split graphs. We then turn our attention to positive results and present polynomial time algorithms to solve the PIG-completion problem when the input is restricted to caterpillar and threshold graphs. We also present an efficient algorithm for the minimum co-bipartite-completion for quasi-threshold graphs, which provides a lower bound for the PIG-completion problem within this graph class.
Blumer et al. (1987, 1989) showed that any concept class that is learnable by Occam algorithms is PAC learnable. Board and Pitt (1990) showed a partial converse of this theorem: for concept classes that are closed under exception lists, any class that is PAC learnable is learnable by an Occam algorithm. However, their Occam algorithm outputs a hypothesis whose complexity is $\delta$-dependent, which is an important limitation. In this paper, we show that their partial converse applies to Occam algorithms with $\delta$-independent complexities as well. Thus, we provide a posteriori justification of various theoretical results and algorithm design methods which use the partial converse as a basis for their work.
We study the problem of reconstructing the Faber--Schauder coefficients of a continuous function $f$ from discrete observations of its antiderivative $F$. Our approach starts with formulating this problem through piecewise quadratic spline interpolation. We then provide a closed-form solution and an in-depth error analysis. These results lead to some surprising observations, which also throw new light on the classical topic of quadratic spline interpolation itself: They show that the well-known instabilities of this method can be located exclusively within the final generation of estimated Faber--Schauder coefficients, which suffer from non-locality and strong dependence on the initial value and the given data. By contrast, all other Faber--Schauder coefficients depend only locally on the data, are independent of the initial value, and admit uniform error bounds. We thus conclude that a robust and well-behaved estimator for our problem can be obtained by simply dropping the final-generation coefficients from the estimated Faber--Schauder coefficients.
Whisper is a recent Automatic Speech Recognition (ASR) model displaying impressive robustness to both out-of-distribution inputs and random noise. In this work, we show that this robustness does not carry over to adversarial noise. We show that we can degrade Whisper performance dramatically, or even transcribe a target sentence of our choice, by generating very small input perturbations with Signal Noise Ratio of 35-45dB. We also show that by fooling the Whisper language detector we can very easily degrade the performance of multilingual models. These vulnerabilities of a widely popular open-source model have practical security implications and emphasize the need for adversarially robust ASR.
L. Klebanov proved the following theorem. Let $\xi_1, \dots, \xi_n$ be independent random variables. Consider linear forms $L_1=a_1\xi_1+\cdots+a_n\xi_n,$ $L_2=b_1\xi_1+\cdots+b_n\xi_n,$ $L_3=c_1\xi_1+\cdots+c_n\xi_n,$ $L_4=d_1\xi_1+\cdots+d_n\xi_n,$ where the coefficients $a_j, b_j, c_j, d_j$ are real numbers. If the random vectors $(L_1,L_2)$ and $(L_3,L_4)$ are identically distributed, then all $\xi_i$ for which $a_id_j-b_ic_j\neq 0$ for all $j=\overline{1,n}$ are Gaussian random variables. The present article is devoted to an analog of the Klebanov theorem in the case when random variables take values in a locally compact Abelian group and the coefficients of the linear forms are integers.
Given $n$ independent and identically distributed observations and measuring the value of obtaining an additional observation in terms of Le Cam's notion of deficiency between experiments, we show for certain types of non-parametric experiments that the value of an additional observation decreases at a rate of $1/\sqrt{n}$. This is distinct from the known typical decrease at a rate of $1/n$ for parametric experiments and the non-decreasing value in the case of very large experiments. In particular, the rate of $1/\sqrt{n}$ holds for the experiment given by observing samples from a density about which we know only that it is bounded from below by some fixed constant. Thus there exists an experiment where the value of additional observations tends to zero but for which no estimator that is consistent (in total variation distance) exists.
This is an expository paper. A $1$-cycle in a graph is a set $C$ of edges such that every vertex is contained in an even number of edges from $C$. E.g., a cycle in the sense of graph theory is a $1$-cycle, but not vice versa. It is easy to check that the sum (modulo $2$) of $1$-cycles is a $1$-cycle. In this text we study the following problems: to find $\bullet$ the number of all 1-cycles in a given graph; $\bullet$ a small number of 1-cycles in a given graph such that any 1-cycle is the sum of some of them. We also consider generalizations (of these problems) to graphs with symmetry, and to $2$-cycles in $2$-dimensional hypergraphs.
A new information theoretic condition is presented for reconstructing a discrete random variable $X$ based on the knowledge of a set of discrete functions of $X$. The reconstruction condition is derived from Shannon's 1953 lattice theory with two entropic metrics of Shannon and Rajski. Because such a theoretical material is relatively unknown and appears quite dispersed in different references, we first provide a synthetic description (with complete proofs) of its concepts, such as total, common and complementary informations. Definitions and properties of the two entropic metrics are also fully detailed and shown compatible with the lattice structure. A new geometric interpretation of such a lattice structure is then investigated that leads to a necessary (and sometimes sufficient) condition for reconstructing the discrete random variable $X$ given a set $\{ X_1,\ldots,X_{n} \}$ of elements in the lattice generated by $X$. Finally, this condition is illustrated in five specific examples of perfect reconstruction problems: reconstruction of a symmetric random variable from the knowledge of its sign and absolute value, reconstruction of a word from a set of linear combinations, reconstruction of an integer from its prime signature (fundamental theorem of arithmetic) and from its remainders modulo a set of coprime integers (Chinese remainder theorem), and reconstruction of the sorting permutation of a list from a minimal set of pairwise comparisons.
Ghost, or fictitious points allow to capture boundary conditions that are not located on the finite difference grid discretization. We explore in this paper the impact of ghost points on the stability of the explicit Euler finite difference scheme in the context of the diffusion equation. In particular, we consider the case of a one-touch option under the Black-Scholes model. The observations and results are however valid for a much wider range of financial contracts and models.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191