Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFrom reversible computation to quantum computation by Lagrange interpolation
157
0
0.0
(
0
)
Added by
Stijn De Baerdemacker
Publication date
2015
fields
Physics
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Classical reversible circuits, acting on $w$~bits, are represented by permutation matrices of size $2^w times 2^w$. Those matrices form the group P($2^w$), isomorphic to the symmetric group {bf S}$_{2^w}$. The permutation group P($n$), isomorphic to {bf S}$_n$, contains cycles with length~$p$, ranging from~1 to $L(n)$, where $L(n)$ is the so-called Landau function. By Lagrange interpolation between the $p$~matrices of the cycle, we step from a finite cyclic group of order~$p$ to a 1-dimensional Lie group, subgroup of the unitary group U($n$). As U($2^w$) is the group of all possible quantum circuits, acting on $w$~qubits, such interpolation is a natural way to step from classical computation to quantum computation.
rate research
Read More
Reversible simulation of irreversible algorithms is analyzed in the stylized form of a `reversible pebble game. While such simulations incur little overhead in additional computation time, they use a large amount of additional memory space during the computation. The reacheable reversible simulation instantaneous descriptions (pebble configurations) are characterized completely. As a corollary we obtain the reversible simulation by Bennett and that among all simulations that can be modelled by the pebble game, Bennetts simulation is optimal in that it uses the least auxiliary space for the greatest number of simulated steps. One can reduce the auxiliary storage overhead incurred by the reversible simulation at the cost of allowing limited erasing leading to an irreversibility-space tradeoff. We show that in this resource-bounded setting the limited erasing needs to be performed at precise instants during the simulation. We show that the reversible simulation can be modified so that it is applicable also when the simulated computation time is unknown.
We present a new approach to scalable quantum computing--a ``qubus computer--which realises qubit measurement and quantum gates through interacting qubits with a quantum communication bus mode. The qubits could be ``static matter qubits or ``flying optical qubits, but the scheme we focus on here is particularly suited to matter qubits. There is no requirement for direct interaction between the qubits. Universal two-qubit quantum gates may be effected by schemes which involve measurement of the bus mode, or by schemes where the bus disentangles automatically and no measurement is needed. In effect, the approach integrates together qubit degrees of freedom for computation with quantum continuous variables for communication and interaction.
In some of the earliest work on quantum mechanical computers, Feynman showed how to implement universal quantum computation by the dynamics of a time-independent Hamiltonian. I show that this remains possible even if the Hamiltonian is restricted to be a sparse matrix with all entries equal to 0 or 1, i.e., the adjacency matrix of a low-degree graph. Thus quantum walk can be regarded as a universal computational primitive, with any desired quantum computation encoded entirely in some underlying graph. The main idea of the construction is to implement quantum gates by scattering processes.
Atomic-scale logic and the minimization of heating (dissipation) are both very high on the agenda for future computation hardware. An approach to achieve these would be to replace networks of transistors directly by classical reversible logic gates built from the coherent dynamics of a few interacting atoms. As superpositions are unnecessary before and after each such gate (inputs and outputs are bits), the dephasing time only needs to exceed a single gate operation time, while fault tolerance should be achieved with low overhead, by classical coding. Such gates could thus be a spin-off of quantum technology much before full-scale quantum computation. Thus motivated, we propose methods to realize the 3-bit Toffoli and Fredkin gates universal for classical reversible logic using a single time-independent 3-qubit Hamiltonian with realistic nearest neighbour two-body interactions. We also exemplify how these gates can be composed to make a larger circuit. We show that trapped ions may soon be scalable simulators for such architectures, and investigate the prospects with dopants in silicon.
The problem of $X$-secure $T$-colluding symmetric Private Polynomial Computation (PPC) from coded storage system with $B$ Byzantine and $U$ unresponsive servers is studied in this paper. Specifically, a dataset consisting of $M$ files are stored across $N$ distributed servers according to $(N,K+X)$ Maximum Distance Separable (MDS) codes such that any group of up to $X$ colluding servers can not learn anything about the data files. A user wishes to privately evaluate one out of a set of candidate polynomial functions over the $M$ files from the system, while guaranteeing that any $T$ colluding servers can not learn anything about the identity of the desired function and the user can not learn anything about the $M$ data files more than the desired polynomial function, in the presence of $B$ Byzantine servers that can send arbitrary responses maliciously to confuse the user and $U$ unresponsive servers that will not respond any information at all. Two novel symmetric PPC schemes using Lagrange encoding are proposed. Both the two schemes achieve the same PPC rate $1-frac{G(K+X-1)+T+2B}{N-U}$, secrecy rate $frac{G(K+X-1)+T}{N-(G(K+X-1)+T+2B+U)}$, finite field size and decoding complexity, where $G$ is the maximum degree over all the candidate polynomial functions. Particularly, the first scheme focuses on the general case that the candidate functions are consisted of arbitrary polynomials, and the second scheme restricts the candidate functions to be a finite-dimensional vector space (or sub-space) of polynomials over $mathbb{F}_p$ but requires less upload cost, query complexity and server computation complexity. Remarkably, the PPC setup studied in this paper generalizes all the previous MDS coded PPC setups and the two degraded schemes strictly outperform the best known schemes in terms of (asymptotical) PPC rate, which is the main concern of the PPC schemes.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
