Inspired by quantum computing algorithms for Linear Algebra problems [Harrow et al., Phys. Rev. Lett. 2009, Ta-Shma, STOC 2013] we study how simulation on a classical computer of this type of "Phase Estimation algorithms" performs when we apply it to the Eigen-Problem of Hermitian matrices. The result is a completely new, efficient and stable, parallel algorithm to compute an approximate spectral decomposition of any Hermitian matrix. The algorithm can be implemented by Boolean circuits in O(log^2(n)) parallel time with a total cost of O(n^(\omega+1)) Boolean operations. This Boolean complexity matches the best known O(log^2(n)) parallel time algorithms, but unlike those algorithms our algorithm is (logarithmically) stable, so it may lead to actual implementations, allowing fast parallel computation of eigenvectors and eigenvalues in practice. Previous approaches to solve the Eigen-Problem generally use randomization to avoid bad conditions - as we do. Our algorithm makes further use of randomization in a completely new way, taking random powers of a unitary matrix to randomize the phases of its eigenvalues. Proving that a tiny Gaussian perturbation and a random polynomial power are sufficient to ensure almost pairwise independence of the phases (mod 2pi) is the main technical contribution of this work. It relies on the theory of low-discrepancy or quasi-random sequences - a theory, which to the best of our knowledge, has not been connected thus far to linear algebra problems. Hence, we believe that further study of this new connection will lead to additional improvements.

We introduce a new variant of quantum multiprover interactive proofs (QMIP) where the provers and the verifier are quantum. The verifier can exchange quantum messages with the provers. The provers cannot communicate quantumly between themselves and do not share entanglement, but are unlimited in the classical communication between them, even after receiving messages from the verifier. We show that any language in nondeterministic exponential time (NEXP) can be recognized in this model efficiently, with just two provers and two rounds of communication, and with a constant completeness/soundness gap. This is in contrast to the result of [R. Jain et al., Comm. ACM, 53 (2010), pp. 102--109], which shows that QIP = PSPACE, or equivalently that the set of languages that can be recognized by a quantum verifier communicating with a single quantum prover is equal to PSPACE. To analyze the cheating power of the provers, we give them more power and allow them to perform any separable operation. We then show a unique two-phase protocol in which the provers first commit to a superposition of correct answers to all possible questions, and then in the second phase the verifier opens up the committed answer and checks for correctness and consistency.

We use a Bayesian approach to optimally solve problems in noisy binary search. We deal with two variants:1. Each comparison is erroneous with independent probability 1-p. 2. At each stage k comparisons can be performed in parallel and a noisy answer is returned. We present a (classical) algorithm which solves both variants optimally (with respect to p and k), up to an additive term of O(loglog n), and prove matching information-theoretic lower bounds. We use the algorithm to improve the results of Farhi et al., presenting an exact quantum search algorithm in an ordered list of expected complexity less than (log2n)/3.

We introduce another variant of quantum MIP, where the provers do not share entanglement, the communication between the verifier and the provers is quantum, but the provers are unlimited in the classical communication between them. At first, this model may seem very weak, as provers who exchange information seem to be equivalent in power to a simple prover. This in fact is not the case-we show that any language in NEXP can be recognized in this model efficiently, with just two provers and two rounds of communication, with a constant completeness-soundness gap. Similar ideas and techniques may help help with other models of quantum MIP, including the dual question, of non communicating provers with unlimited entanglement.

Consider a distributed network in which up to a third of the nodes may be Byzantine, and in which the non-faulty nodes may be subject to transient faults that alter their memory in an arbitrary fashion. Within the context of this model, we are interested in the digital clock synchronization problem; which consists of agreeing on bounded integer counters, and increasing these counters regularly. It has been postulated in the past that synchronization cannot be solved in a Byzantine tolerant and self-stabilizing manner. The first solution to this problem had an expected exponential convergence time. Later, a deterministic solution was published with linear convergence time, which is optimal for deterministic solutions. In the current paper we achieve an expected constant convergence time. We thus obtain the optimal probabilistic solution, both in terms of convergence time and in terms of resilience to Byzantine adversaries.

This paper shows that quantum computation can be made fault-tolerant against errors and inaccuracies when $\eta$, the probability for an error in a qubit or a gate, is smaller than a constant threshold $\eta_c$. This result improves on Shor's result [Proceedings of the 37th Symposium on the Foundations of Computer Science, IEEE, Los Alamitos, CA, 1996, pp. 56–65], which shows how to perform fault-tolerant quantum computation when the error rate $\eta$ decays polylogarithmically with the size of the computation, an assumption which is physically unreasonable. The cost of making the quantum circuit fault-tolerant in our construction is polylogarithmic in time and space. Our result holds for a very general local noise model, which includes probabilistic errors, decoherence, amplitude damping, depolarization, and systematic inaccuracies in the gates. Moreover, we allow exponentially decaying correlations between the errors both in space and in time. Fault-tolerant computation can be performed with any universal set of gates. The result also holds for quantum particles with $p>2$ states, namely, p-qudits, and is also generalized to one-dimensional quantum computers with only nearest-neighbor interactions. No measurements, or classical operations, are required during the quantum computation. We estimate the threshold of our construction to be $\eta_c\simeq 10^{-6}$, in the best case. By this we show that local noise is in principle not an obstacle for scalable quantum computation. The main ingredient of our proof is the computation on states encoded by a quantum error correcting code (QECC). To this end we introduce a special class of Calderbank–Shor–Steane (CSS) codes, called polynomial codes (the quantum analogue of Reed–Solomon codes). Their nice algebraic structure allows all of the encoded gates to be transversal. We also provide another version of the proof which uses more general CSS codes, but its encoded gates are slightly less elegant. To achieve fault tolerance, we encode the quantum circuit by another circuit by using one of these QECCs. This step is repeated polyloglog many times, each step slightly improving the effective error rate, to achieve the desired reliability. The resulting circuit exhibits a hierarchical structure, and for the analysis of its robustness we borrow terminology from Khalfin and Tsirelson [Found. Phys., 22 (1992), pp. 879–948] and Gács [Advances in Computing Research: A Research Annual: Randomness and Computation, JAI Press, Greenwich, CT, 1989]. The paper is to a large extent self-contained. In particular, we provide simpler proofs for many of the known results we use, such as the fact that it suffices to correct for bit-flips and phase-flips, the correctness of CSS codes, and the fact that two-qubit gates are universal, together with their extensions to higher-dimensional particles. We also provide full proofs of the universality of the sets of gates we use (the proof of universality was missing in Shor's paper). This paper thus provides a self-contained and complete proof of universal fault-tolerant quantum computation in the presence of local noise.

Secret sharing and multiparty computation (also called "secure function evaluation") are fundamental primitives in modern cryptography, allowing a group of mutually distrustful players to perform correct, distributed computations under the sole assumption that some number of them will follow the protocol honestly. This paper investigates how much trust is necessary -- that is, how many players must remain honest -- in order for distributed quantum computations to be possible. We present a verifiable quantum secret sharing (VQSS) protocol, and a general secure multiparty quantum computation (MPQC) protocol, which can tolerate any \left[ {\frac{{n - 1}} {2}} \right] cheaters among n players. Previous protocols for these tasks tolerated \left[ {\frac{{n - 1}} {4}} \right] and \left[ {\frac{{n - 1}} {6}} \right] cheaters, respectively. The threshold we achieve is tight -- even in the classical case, "fair" multiparty computation is not possible if any set of n/2 players can cheat. Our protocols rely on approximate quantum errorcorrecting codes, which can tolerate a larger fraction of errors than traditional, exact codes. We introduce new families of authentication schemes and approximate codes tailored to the needs of our protocols, as well as new state purification techniques along the lines of those used in faulttolerant quantum circuits.

We present a randomized Byzantine Agreement (BA) protocol with an expected running time of O(log n) rounds, in a synchronous full-information network of n players. For any constant ε > 0, the constructed protocol tolerates t non-adaptive Byzantine faults, as long as n ≥ (4 + ε)t. In the full-information model, no restrictions are placed on the computational power of the faulty players or the information available to them. In particular, the faulty players may be infinitely powerful, and they can observe all communication among the honest players.This constitutes significant progress over the best known randomized BA protocol in the same setting which has a round-complexity of Θ(t/log n) rounds [9], and answers an open problem posed by Chor and Dwork [10].

We present a fast quantum Byzantine Agreement protocol that can reach agreement in O(1) expected communication rounds against a strong full information, dynamic adversary, tolerating up to the optimal t‹n3 faulty players in the synchronous setting, and up to t‹n4 faulty players for asynchronous systems. This should be contrasted with the known classical synchronous lower bound of Ω(√ nlog n) [3] when t=(n).

We prove tight upper and lower bounds of @(t/J-) on the expected number of rounds needed for randomized synchronous consensus protocols for a fail-stop, full information, dynamic adversary.In particular this proves that some restrictions are needed on the power of the adversary to allow randomized constant expected number of rounds protocols.

BARTER (a Backbone ARchitecture for Trade of ElectRonic content) is a payment infrastructure that facilitates digital content trade over an open network. BARTER is designed to operate over a large-scale, global and heterogeneous communication network. The BARTER protocols address two vital requirements, neglected from existing electronic commerce systems: scalability and transactional efficiency. These protocols possess strong properties such as delivery atomicity, agreement validation and the ability to resolve several classes of disputes. BARTER's novelty is twofold: First, BARTER servers are not required to perform expensive cryptographic operations such as commitment verification; commitments are cross-verified by the parties themselves, thus reducing the overhead of online transaction processing by orders of magnitude. Consequently, BARTER can serve as an efficient online/offline clearing infrastructure. Second, BARTER integrates scalability considerations into several system components (the authentication subsystem, the account management subsystem, and the maintenance of global data) that are likely to suffer service degradation in a world-wide setting. In addressing these issues, BARTER takes into account the inherent asynchronous, unreliable, insecure and failure-prone environment assumptions. We contend that by employing service distribution, BARTER is expected to scale well, meeting the demands of a world-wide setting, over which it is intended to operate.

In the past year many developments have taken place in the area of quantum error corrections. Recently Shor showed how to perform fault tolerant quantum computation when, , the probability for a fault in one time step per qubit or per gate, is polylogarithmically small. This paper closes the gap and shows how to perform fault tolerant quantum computation when the error probability, , is smaller than some constant threshold, 0 . The cost is polylogarithmic in time and space, and no measurements are used during the quantum computation. The same result is shown also for quantum circuits which operate on nearest neighbors only.

Recently it has become clear, that a key issue in quantum computation is understanding how interaction with the environment, or "decoherence", affects the computational power of quantum computers. We adopt the standard physical method of describing systems which are interwound with their environment by "density matrices", and within this framework define a model of decoherence in quantum computation. Our results show that the computational power of decohered quantum computers depends strongly on the amount of parallelism in the computation. We first present a simulation of decohered sequential quantum computers, on a classical probabilistic Turing machine, and prove that the expected slowdown of this simulation is polynomial in time and space of the quantum computation, for any non zero decoherence rate. Similar results hold for quantum computers that are allowed to operate on logarithmic number of qubits at a time. For decohered quantum circuits (with local gates), the situation is more subtle and depends on the decoherence rate, /spl eta/. We find that our simulation is efficient for circuits with decoherence rate /spl eta/ higher than some constant /spl eta//sub 1/ but exponential for a general (random) circuit subjected to decoherence rate lower than some constant /spl eta//sub 2/. The transition from exponential cost to polynomial cost happens in a short range of decoherence rates. We use computer experiments to exhibit the phase transitions in various quantum circuits.

We provide a simple and powerful combinatorial method for proving lower bounds for algebraic computation trees over algebraically closed fields of characteristic p>0. We apply our method to prove, for example, an /spl Omega/(n log n) lower bound for the n element distinctness problem, an /spl Omega/(n log(n/k)) lower bound to the "k-equal problem"-that is deciding whether there are k identical elements out of n input elements, and more. The proof of the main theorem relies on the deep work of B.M. Dwork, P. Deligne, and E. Bombieri on the Weil conjectures. In particular we make use of Bombieri's bound on the degree of the Zeta function of algebraic varieties over finite fields. Our bounds provide a natural extension to the recent topological lower bounds obtained by A. Bjorner, L. Lovasz and A.C. Yao for algebraic computation trees over the real numbers. For the special cases of real subspace arrangements and general complex varieties we can reformulate their specific results using our combinatorial approach without mentioning any topological invariants.>

We investigate the problem of multiparty computations in a fully connected, asynchronous network of n players, in which up to t Byzantine faults may occur.

We initiate a study of security in asynchronous networks.We consider a completely asynchronous network where every two parties are connected via a private channel, and some of the parties may be faulty.We start by defining secure computation in this model.Our definition adapts the underlying principles of defining security (i.e.

We present and O(1) slowdown emulation of a fault-free N x N two dimensional mesh with a slack of O(log N log log N) by a faulty mesh of the same size and slack. All components of the faulty mesh, including the memory modules, are assumed to be subject to failure. The faults may occur at any time during the emulation and the system readjusts dynamically.

It is shown that, over an arbitrary ring, the functions computed by polynomial-size algebraic formulas are also computed by polynomial-length algebraic straight-line programs that use only three registers. This was previously known for Boolean formulas [D. A. Barrington, J. Comput. System Sci., 38 (1989), pp. 150–164], which are equivalent to algebraic formulas over the ring $GF(2)$. For formulas over arbitrary rings, the result is an improvement over previous methods that require the number of registers to be logarithmic in the size of the formulas in order to obtain polynomial-length straight-line programs. Moreover, the straight-line programs that arise in these constructions have the property that they consist of statements whose actions on the registers are linear and bijective. A consequence of this is that the problem of determining the iterated product of $n3 \times 3$ matrices is complete (under P-projections) for algebraic $NC^1 $. Also, when the ring is $GF(2)$, the programs that arise in the constructions are equivalent to bounded-width permutation branching programs.

A scheme for emulating the parallel random access machine (PRAM) on a faulty hypercube is presented. All components of the hypercube, including the memory modules, are assumed to be subject to failure. The faults may occur at any time during the emulation and the system readjusts dynamically. The scheme, which rests on L.G. Valiant's BSP model (1990), is the first to achieve optimal and work-preserving PRAM emulation on a dynamically faulty network.>

Two parties, A and B, want to sign a contract C over a communication network. To do so, they must simultaneously exchange their commitments to C. Since simultaneous exchange is usually impossible in practice, protocols are needed to approximate simultaneity by exchanging partial commitments in piece-by-piece manner. During such a protocol, one party or another may have a slight advantage; a fair protocol keeps this advantage within acceptable limits. A new protocol is proposed. It is fair in the sense that, at any stage in its execution, the conditional probability that one party cannot commit both parties to the contract given that the other party can, is close to zero. This is true even if A and B have vastly different computing powers and is proved under very weak cryptographic assumptions.>

Under the assumption that each participant can broadcast a message to all other participants and that each pair of participants can communicate secretly, we present a verifiable secret sharing protocol, and show that any multiparty protocol, or game with incomplete information, can be achieved if a majority of the players are honest. The secrecy achieved is unconditional and does not rely on any assumption about computational intractability. Applications of these results to Byzantine Agreement are also presented.

We show that, over an arbitrary ring, the functions computed by polynomial-size algebraic formulas are also computed by polynomial-length algebraic straight-line programs which use only 3 registers (or 4 registers, depending on some definitions). We also show that polynomial-length products of 3 × 3 matrices compute precisely those functions that polynomial-size formulas compute (whereas, for general rings, polynomial-length 3-register straight-line programs compute strictly more functions than polynomial-size formulas). This can be viewed as an extension of the results of Barrington in [Ba1,Ba2] from the Boolean setting to the algebraic setting of an arbitrary ring.

Quite complex cryptographic machinery has been developed based on the assumption that one-way functions exist, yet we know of only a few possible such candidates. It is important at this time to find alternative foundations to the design of secure cryptography. We introduce a new model of generalized interactive proofs as a step in this direction. We prove that all NP languages have perfect zero-knowledge proof-systems in this model, without making any intractability assumptions.

Every function of n inputs can be efficiently computed by a complete network of n processors in such a way that:

An efficient deterministic polynomial time algorithm is developed for the sparse polynomial interpolation problem. The number of evaluations needed by this algorithm is very small. The algorithm also has a simple NC implementation.

Given a polynomial $p(z)$ of degree n with m bit integer coefficients and an integer $\mu $, the problem of determining all its roots with error less than $2^{ - \mu } $ is considered. It is shown that this problem is in the class NC if $p(z)$ has all real roots. Some very interesting properties of a Sturm sequence of a polynomial with distinct real roots are proved and used in the design of a fast parallel algorithm for this problem. Using Newton identities and a novel numerical integration scheme for evaluating a contour integral to high precision, this algorithm determines good approximations to the linear factors of $p(z)$.

Article Free Access Share on A fast parallel algorithm for determining all roots of a polynomial with real roots Authors: M Ben-Or Hebrew University, Jerusalem, Israel Hebrew University, Jerusalem, IsraelView Profile , E Feig IBM Research, Yorktown Heights, NY IBM Research, Yorktown Heights, NYView Profile , D Kozen Dept. of Computer Science, Cornell University, Ithaca, NY Dept. of Computer Science, Cornell University, Ithaca, NYView Profile , P Tiwari Coordinated Science Lab., University of Illinois at Urbana-Champaign, Urbana, IL Coordinated Science Lab., University of Illinois at Urbana-Champaign, Urbana, ILView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 340–349https://doi.org/10.1145/12130.12165Published:01 November 1986Publication History 15citation381DownloadsMetricsTotal Citations15Total Downloads381Last 12 Months35Last 6 weeks16 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The power of players in a collective decision process is a central issue in Mathematical Economics and Game Theory. Similar issues arise in Computer Science in the study of distributed, fault tolerant computations when several processes, some perhaps faulty, have to reach agreement. In the present article we study voting schemes which are relatively immune to the presence of unfair players. In particular, we discuss how to perform collective coin flipping which is only slightly biased despite the presence of unfair players. Mathematically this corresponds to problems concerning the minima of Banzhaf values in certain n -person games. These are measures of power studied in Game Theory. It is quite remarkable that while dictatorial voting games are, of course, the most sensitive to the presence of unfair players, some voting schemes that we propose here are significantly more robust than majority voting. Coin flipping was selected as a study case because of its simplicity and because collective coin flipping is widely used in randomized algorithms for distributed computations. It is our feeling that Game Theory has much to contribute to Computer Science and we are sure that further applications will be found.

No abstract available.

No abstract available.

Article Free Access Share on A theorem on probabilistic constant depth Computations Authors: Miklos Ajtai View Profile , Michael Ben-Or View Profile Authors Info & Claims STOC '84: Proceedings of the sixteenth annual ACM symposium on Theory of computingDecember 1984 Pages 471–474https://doi.org/10.1145/800057.808715Online:01 December 1984Publication History 55citation507DownloadsMetricsTotal Citations55Total Downloads507Last 12 Months22Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article The complexity of elementary algebra and geometry Share on Authors: Michael Ben-Or View Profile , Dexter Kozen View Profile , John Reif View Profile Authors Info & Claims STOC '84: Proceedings of the sixteenth annual ACM symposium on Theory of computingDecember 1984 Pages 457–464https://doi.org/10.1145/800057.808712Online:01 December 1984Publication History 26citation516DownloadsMetricsTotal Citations26Total Downloads516Last 12 Months31Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Recently, Fischer, Lynch and Paterson [3] proved that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We exhibit here a probabilistic solution for this problem, which guarantees that as long as a majority of the processes continues to operate, a decision will be made (Theorem 1). Our solution is completely asynchronous and is rather strong: As in [4], it is guaranteed to work with probability 1 even against an adversary scheduler who knows all about the system.

A topological method is given for obtaining lower bounds for the height of algebraic computation trees, and algebraic decision trees. Using this method we are able to generalize, and present in a uniform and easy way, almost all the known nonlinear lower bounds for algebraic computations. Applying the method to decision trees we extend all the apparently known lower bounds for linear decision trees to bounded degree algebraic decision trees, thus answering the open questions raised by Steele and Yao [20]. We also show how this new method can be used to establish lower bounds on the complexity of constructions with ruler and compass in plane Euclidean geometry.

The ability to “hide” one bit in trapdoor functions has recently gained much interest in cryptography research, and is of great importance in many transactions protocols. In this paper we study the cryptographic security of RSA bits. In particular, we show that unless the cryptanalyst can completely break the RSA encryption, any heuristic he uses to determine the least significant bit of the cleartext must have an error probability greater than 1/4—e A similar result is shown for Rabin's encryption scheme.