Quantum Algorithms for the Triangle Problem
From MaRDI portal
Publication:5386207
DOI10.1137/050643684zbMath1166.68032arXivquant-ph/0310134OpenAlexW2035627701WikidataQ55891737 ScholiaQ55891737MaRDI QIDQ5386207
Miklos Santha, Frédéric Magniez, Mario Szegedy
Publication date: 22 April 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/quant-ph/0310134
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Quantum computation (81P68) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (64)
The staggered quantum walk model ⋮ Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model ⋮ A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs ⋮ Path-integral solution of the one-dimensional Dirac quantum cellular automaton ⋮ Randomizing quantum walk ⋮ QUANTUM QUERY COMPLEXITY OF CONSTANT-SIZED SUBGRAPH CONTAINMENT ⋮ Generating Reversible Circuits from Higher-Order Functional Programs ⋮ Improving quantum query complexity of Boolean matrix multiplication using graph collision ⋮ Path-sum solution of the Weyl quantum walk in 3 + 1 dimensions ⋮ Solving Lyapunov equation by quantum algorithm ⋮ Quantum walk and its application domains: a systematic review ⋮ Quantum algorithm for triangle finding in sparse graphs ⋮ Quantum Complexity of Boolean Matrix Multiplication and Related Problems ⋮ Szegedy quantum walks with memory on regular graphs ⋮ Weyl, Dirac and Maxwell quantum cellular automata ⋮ Quantum Walk Based Search Algorithms ⋮ Optimizing the walk coin in the quantum random walk search algorithm ⋮ Improvement of quantum walks search algorithm in single-marked vertex graph ⋮ Quantum algorithms for finding constant-sized sub-hypergraphs ⋮ A high-fidelity quantum state transfer algorithm on the complete bipartite graph ⋮ Quantum walks for the determination of commutativity of finite dimensional algebras ⋮ Quantum field as a quantum cellular automaton: the Dirac free evolution in one dimension ⋮ Overview: recent development and applications of reduction and lackadaisicalness techniques for spatial search quantum walk in the near term ⋮ Quantum algorithm for lexicographically minimal string rotation ⋮ Three-state quantum walk on the Cayley graph of the dihedral group ⋮ Discrete-time semiclassical Szegedy quantum walks ⋮ The Witten index for one-dimensional split-step quantum walks under the non-Fredholm condition ⋮ Near-optimal quantum algorithms for string problems ⋮ On the hitting times of quantum versus random walks ⋮ Novel two-party quantum private comparison via quantum walks on circle ⋮ Quantum search of matching on signed graphs ⋮ Equivalence of Szegedy's and coined quantum walks ⋮ Limiting properties of stochastic quantum walks on directed graphs ⋮ Adjacent Vertices Can Be Hard to Find by Quantum Walks ⋮ Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems ⋮ Quantum search with variable times ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Symmetries of the Dirac quantum walk and emergence of the de Sitter group ⋮ Quantum algorithm design: techniques and applications ⋮ One-dimensional quantum walks with a position-dependent coin ⋮ On the power of non-adaptive learning graphs ⋮ Connecting Coined Quantum Walks with Szegedy's Model ⋮ Two quantum coins sharing a walker ⋮ Quantum search algorithm for exceptional vertexes in regular graphs and its circuit implementation ⋮ Improved quantum query algorithms for triangle detection and associativity testing ⋮ Constructing quantum hash functions based on quantum walks on Johnson graphs ⋮ Element distinctness revisited ⋮ Quantum walks: a comprehensive review ⋮ Quantum counterfeit coin problems ⋮ Quantum Random Walks – New Method for Designing Quantum Algorithms ⋮ Quantum Walks with Multiple or Moving Marked Locations ⋮ Applied quantum physics for novel quantum computation approaches: an update ⋮ Quantum state transfer on unsymmetrical graphs via discrete-time quantum walk ⋮ Quantum algorithms for algebraic problems ⋮ Extended learning graphs for triangle finding ⋮ Quantum Property Testing for Bounded-Degree Graphs ⋮ Claw finding algorithms using quantum walk ⋮ Hash function based on quantum walks ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A quantum searching model finding one of the edges of a subgraph in a complete graph ⋮ Faster search of clustered marked states with lackadaisical quantum walks ⋮ Unnamed Item ⋮ Quantum walks can find a marked element on any graph
This page was built for publication: Quantum Algorithms for the Triangle Problem
