scientific article; zbMATH DE number 7561744
From MaRDI portal
Publication:5092465
DOI10.4230/LIPIcs.CCC.2020.16MaRDI QIDQ5092465
Ruizhe Zhang, Scott Aaronson, Chun-Hao Wang, Nai-Hui Chia, Han-Hsuan Lin
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/1911.01973
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
quantum computingclosest pairfine grained complexityquantum fine grained reductionquantum strong exponential time hypothesis
Related Items (3)
Quantum complexity for vector domination problem ⋮ Near-optimal quantum algorithms for string problems ⋮ Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of d-dimensional Voronoi diagrams
- Quantum Arthur-Merlin games
- Euclidean minimum spanning trees and bichromatic closest pairs
- An optimal algorithm for closest-pair maintenance
- A simple randomized sieve algorithm for the closest-pair problem
- On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
- A new algorithm for optimal 2-constraint satisfaction and its implications
- On the complexity of circuit satisfiability
- EXPONENTIAL IMPROVEMENT IN PRECISION FOR SIMULATING SPARSE HAMILTONIANS
- Search via Quantum Walk
- On the Complexity of Closest Pair via Polar-Pair of Point-Sets
- TIGHT QUANTUM BOUNDS FOR COMPUTATIONAL GEOMETRY PROBLEMS
- Quantum lower bounds for the collision and the element distinctness problems
- An improved exponential-time algorithm for k -SAT
- A Randomized Algorithm for Closest-Point Queries
- Strengths and Weaknesses of Quantum Computing
- Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
- Quantum Algorithms for the Subset-Sum Problem
- An Equivalence Class for Orthogonal Vectors
- Quantum Algorithms for Element Distinctness
- Computational Complexity
- More Applications of the Polynomial Method to Algorithm Design
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- Finding orthogonal vectors in discrete structures
- Quantum Walk Algorithm for Element Distinctness
- 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
- On the complexity of \(k\)-SAT
This page was built for publication:
