Search results for "Quantum physic"
showing 10 items of 1596 documents
Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding
2014
Quantum zero-knowledge proofs and quantum proofs of knowledge are inherently difficult to analyze because their security analysis uses rewinding. Certain cases of quantum rewinding are handled by the results by Watrous (SIAM J Comput, 2009) and Unruh (Eurocrypt 2012), yet in general the problem remains elusive. We show that this is not only due to a lack of proof techniques: relative to an oracle, we show that classically secure proofs and proofs of knowledge are insecure in the quantum setting. More specifically, sigma-protocols, the Fiat-Shamir construction, and Fischlin's proof system are quantum insecure under assumptions that are sufficient for classical security. Additionally, we show…
Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
2017
We study quantum algorithms on search trees of unknown structure, in a model where the tree can be discovered by local exploration. That is, we are given the root of the tree and access to a black box which, given a vertex $v$, outputs the children of $v$. We construct a quantum algorithm which, given such access to a search tree of depth at most $n$, estimates the size of the tree $T$ within a factor of $1\pm \delta$ in $\tilde{O}(\sqrt{nT})$ steps. More generally, the same algorithm can be used to estimate size of directed acyclic graphs (DAGs) in a similar model. We then show two applications of this result: a) We show how to transform a classical backtracking search algorithm which exam…
Quantum Algorithm for Dynamic Programming Approach for DAGs. Applications for Zhegalkin Polynomial Evaluation and Some Problems on DAGs
2018
In this paper, we present a quantum algorithm for dynamic programming approach for problems on directed acyclic graphs (DAGs). The running time of the algorithm is $O(\sqrt{\hat{n}m}\log \hat{n})$, and the running time of the best known deterministic algorithm is $O(n+m)$, where $n$ is the number of vertices, $\hat{n}$ is the number of vertices with at least one outgoing edge; $m$ is the number of edges. We show that we can solve problems that use OR, AND, NAND, MAX and MIN functions as the main transition steps. The approach is useful for a couple of problems. One of them is computing a Boolean formula that is represented by Zhegalkin polynomial, a Boolean circuit with shared input and non…
Automata and Quantum Computing
2015
Quantum computing is a new model of computation, based on quantum physics. Quantum computers can be exponentially faster than conventional computers for problems such as factoring. Besides full-scale quantum computers, more restricted models such as quantum versions of finite automata have been studied. In this paper, we survey various models of quantum finite automata and their properties. We also provide some open questions and new directions for researchers. Keywords: quantum finite automata, probabilistic finite automata, nondeterminism, bounded error, unbounded error, state complexity, decidability and undecidability, computational complexity
Supervised Quantum Learning without Measurements
2017
We propose a quantum machine learning algorithm for efficiently solving a class of problems encoded in quantum controlled unitary operations. The central physical mechanism of the protocol is the iteration of a quantum time-delayed equation that introduces feedback in the dynamics and eliminates the necessity of intermediate measurements. The performance of the quantum algorithm is analyzed by comparing the results obtained in numerical simulations with the outcome of classical machine learning methods for the same problem. The use of time-delayed equations enhances the toolbox of the field of quantum machine learning, which may enable unprecedented applications in quantum technologies. The…
Superlinear advantage for exact quantum algorithms
2012
A quantum algorithm is exact if, on any input data, it outputs the correct answer with certainty (probability 1). A key question is: how big is the advantage of exact quantum algorithms over their classical counterparts: deterministic algorithms. For total Boolean functions in the query model, the biggest known gap was just a factor of 2: PARITY of N inputs bits requires $N$ queries classically but can be computed with N/2 queries by an exact quantum algorithm. We present the first example of a Boolean function f(x_1, ..., x_N) for which exact quantum algorithms have superlinear advantage over the deterministic algorithms. Any deterministic algorithm that computes our function must use N qu…
Quantum Computation With Devices Whose Contents Are Never Read
2010
In classical computation, a "write-only memory" (WOM) is little more than an oxymoron, and the addition of WOM to a (deterministic or probabilistic) classical computer brings no advantage. We prove that quantum computers that are augmented with WOM can solve problems that neither a classical computer with WOM nor a quantum computer without WOM can solve, when all other resource bounds are equal. We focus on realtime quantum finite automata, and examine the increase in their power effected by the addition of WOMs with different access modes and capacities. Some problems that are unsolvable by two-way probabilistic Turing machines using sublogarithmic amounts of read/write memory are shown to…
A Quantum Lovasz Local Lemma
2012
The Lovasz Local Lemma (LLL) is a powerful tool in probability theory to show the existence of combinatorial objects meeting a prescribed collection of "weakly dependent" criteria. We show that the LLL extends to a much more general geometric setting, where events are replaced with subspaces and probability is replaced with relative dimension, which allows to lower bound the dimension of the intersection of vector spaces under certain independence conditions. Our result immediately applies to the k-QSAT problem: For instance we show that any collection of rank 1 projectors with the property that each qubit appears in at most $2^k/(e \cdot k)$ of them, has a joint satisfiable state. We then …
Proving The Power Of Postselection
2011
It is a widely believed, though unproven, conjecture that the capability of postselection increases the language recognition power of both probabilistic and quantum polynomial-time computers. It is also unknown whether polynomial-time quantum machines with postselection are more powerful than their probabilistic counterparts with the same resource restrictions. We approach these problems by imposing additional constraints on the resources to be used by the computer, and are able to prove for the first time that postselection does augment the computational power of both classical and quantum computers, and that quantum does outperform probabilistic in this context, under simultaneous time an…
Forrelation
2014
We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum query, yet we show that any randomized algorithm needs Ω(√(N)log(N)) queries (improving an Ω(N[superscript 1/4]) lower bound of Aaronson). Conversely, we show that this 1 versus Ω(√(N)) separation is optimal: indeed, any t-query quantum algorithm whatsoever can be simulated by an O(N[superscript 1-1/2t])-query randomized algorithm. Thus, resolving an open questi…