Search results for "algorithm"

showing 10 items of 4887 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…

FOS: Computer and information sciencesQuantum PhysicsQuantum networkComputer Science - Cryptography and SecurityTheoretical computer scienceFOS: Physical sciencesQuantum capacityQuantum cryptographyQuantum error correctionQuantum algorithmQuantum informationQuantum Physics (quant-ph)Cryptography and Security (cs.CR)Quantum computerQuantum complexity theoryMathematicsComputer Science::Cryptography and Security
researchProduct

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…

FOS: Computer and information sciencesQuantum PhysicsSpeedupBacktrackingFOS: Physical sciences0102 computer and information sciences02 engineering and technologyComputational Complexity (cs.CC)Directed acyclic graph01 natural sciencesSearch treeCombinatoricsComputer Science - Computational Complexity010201 computation theory & mathematicsSearch algorithm020204 information systemsComputer Science - Data Structures and AlgorithmsTernary search tree0202 electrical engineering electronic engineering information engineeringData Structures and Algorithms (cs.DS)Quantum algorithmDepth-first searchQuantum Physics (quant-ph)MathematicsProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
researchProduct

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…

FOS: Computer and information sciencesQuantum PhysicsTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITYComputer Science - Data Structures and AlgorithmsFOS: Physical sciencesData Structures and Algorithms (cs.DS)Quantum Physics (quant-ph)MathematicsofComputing_DISCRETEMATHEMATICS
researchProduct

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…

FOS: Computer and information sciencesQuantum machine learningField (physics)Computer Science - Artificial IntelligenceComputer sciencelcsh:MedicineFOS: Physical sciencesMachine Learning (stat.ML)01 natural sciencesUnitary stateArticle010305 fluids & plasmasSuperconductivity (cond-mat.supr-con)Statistics - Machine Learning0103 physical sciencesMesoscale and Nanoscale Physics (cond-mat.mes-hall)lcsh:Science010306 general physicsQuantumProtocol (object-oriented programming)Quantum PhysicsClass (computer programming)MultidisciplinaryCondensed Matter - Mesoscale and Nanoscale PhysicsCondensed Matter - Superconductivitylcsh:RQuantum technologyArtificial Intelligence (cs.AI)ComputerSystemsOrganization_MISCELLANEOUSlcsh:QQuantum algorithmQuantum Physics (quant-ph)Algorithm
researchProduct

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…

FOS: Computer and information sciencesQuantum sortGeneral Computer ScienceDeterministic algorithmGeneral MathematicsFOS: Physical sciences0102 computer and information sciencesQuantum capacityComputational Complexity (cs.CC)01 natural sciences010305 fluids & plasmasCombinatorics0103 physical sciencesQuantum phase estimation algorithmQuantum informationBoolean function010306 general physicsComputer Science::DatabasesQuantum computerMathematicsDiscrete mathematicsQuantum PhysicsFunction (mathematics)Computer Science - Computational Complexity010201 computation theory & mathematicsQuantum Fourier transformNo-teleportation theoremQuantum algorithmQuantum Physics (quant-ph)Proceedings of the forty-fifth annual ACM symposium on Theory of Computing
researchProduct

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…

FOS: Computer and information sciencesQuantum sortQuantum PhysicsTheoretical computer scienceQuantum Turing machineComputer scienceFormal Languages and Automata Theory (cs.FL)ComputationQuantum simulatorFOS: Physical sciencesComputer Science - Formal Languages and Automata TheoryComputational Complexity (cs.CC)Computer Science - Computational ComplexityQuantum algorithmQuantum informationComputational problemQuantum Physics (quant-ph)Quantum computer
researchProduct

Corrigendum: ExGUtils: A Python Package for Statistical Analysis With the ex-Gaussian Probability Density

2018

The study of reaction times and their underlying cognitive processes is an important field in Psychology. Reaction times are usually modeled through the ex-Gaussian distribution, because it provides a good fit to multiple empirical data. The complexity of this distribution makes the use of computational tools an essential element in the field. Therefore, there is a strong need for efficient and versatile computational tools for the research in this area. In this manuscript we discuss some mathematical details of the ex-Gaussian distribution and apply the ExGUtils package, a set of functions and numerical tools, programmed for python, developed for numerical analysis of data involving the ex…

FOS: Computer and information sciencesResponse timeslcsh:BF1-990Probability density functionex-Gaussian fitStatistics - Applications050105 experimental psychology03 medical and health sciences0302 clinical medicineSignificance testingresponse componentsConceptual AnalysisPsychology0501 psychology and cognitive sciencesStatistical analysisApplications (stat.AP)Ex-Gaussian fitTempo de reaçãoGeneral Psychologycomputer.programming_languagesignificance testingResponse componentsNumerical analysis05 social sciencesAnálise estatísticaCorrectionPython (programming language)Ex gaussianDistribuição Gaussianapythonlcsh:PsychologyOutlierTrimmingPsychologyMATEMATICA APLICADAAlgorithmcomputerSignificance testing030217 neurology & neurosurgeryresponse timesPython
researchProduct

Progressive Stochastic Binarization of Deep Networks

2019

A plethora of recent research has focused on improving the memory footprint and inference speed of deep networks by reducing the complexity of (i) numerical representations (for example, by deterministic or stochastic quantization) and (ii) arithmetic operations (for example, by binarization of weights). We propose a stochastic binarization scheme for deep networks that allows for efficient inference on hardware by restricting itself to additions of small integers and fixed shifts. Unlike previous approaches, the underlying randomized approximation is progressive, thus permitting an adaptive control of the accuracy of each operation at run-time. In a low-precision setting, we match the accu…

FOS: Computer and information sciencesScheme (programming language)Computer Science - Machine LearningComputer scienceStochastic processScalar (physics)Sampling (statistics)Machine Learning (stat.ML)Machine Learning (cs.LG)Statistics - Machine LearningApproximation errorBounded functionReference implementationRepresentation (mathematics)computerAlgorithmcomputer.programming_language2019 Fifth Workshop on Energy Efficient Machine Learning and Cognitive Computing - NeurIPS Edition (EMC2-NIPS)
researchProduct

Sensitivity versus block sensitivity of Boolean functions

2010

Determining the maximal separation between sensitivity and block sensitivity of Boolean functions is of interest for computational complexity theory. We construct a sequence of Boolean functions with bs(f) = 1/2 s(f)^2 + 1/2 s(f). The best known separation previously was bs(f) = 1/2 s(f)^2 due to Rubinstein. We also report results of computer search for functions with at most 12 variables.

FOS: Computer and information sciencesSequenceComputational complexity theoryBlock (permutation group theory)Computational Complexity (cs.CC)Computer Science ApplicationsTheoretical Computer ScienceCombinatoricsComputer Science - Computational ComplexitySignal ProcessingTheory of computationSensitivity (control systems)Boolean functionAlgorithmComputer searchInformation SystemsMathematics
researchProduct

Constructing Antidictionaries in Output-Sensitive Space

2021

A word $x$ that is absent from a word $y$ is called minimal if all its proper factors occur in $y$. Given a collection of $k$ words $y_1,y_2,\ldots,y_k$ over an alphabet $\Sigma$, we are asked to compute the set $\mathrm{M}^{\ell}_{y_{1}\#\ldots\#y_{k}}$ of minimal absent words of length at most $\ell$ of word $y=y_1\#y_2\#\ldots\#y_k$, $\#\notin\Sigma$. In data compression, this corresponds to computing the antidictionary of $k$ documents. In bioinformatics, it corresponds to computing words that are absent from a genome of $k$ chromosomes. This computation generally requires $\Omega(n)$ space for $n=|y|$ using any of the plenty available $\mathcal{O}(n)$-time algorithms. This is because a…

FOS: Computer and information sciencesSettore ING-INF/05 - Sistemi Di Elaborazione Delle InformazioniOutput sensitive algorithmsString algorithmsPhysicsAntidictionarieSettore INF/01 - InformaticaOutput sensitive algorithm0102 computer and information sciencesAbsent wordsSpace (mathematics)01 natural sciencesAntidictionariesCombinatorics010201 computation theory & mathematicsTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITYData compressionComputer Science - Data Structures and AlgorithmsData Structures and Algorithms (cs.DS)Computer Science::Symbolic Computation[INFO]Computer Science [cs]Absent wordAlphabetWord (group theory)2019 Data Compression Conference (DCC)
researchProduct