dorsal/arxiv
View SchemaSpeedup of iterated quantum search by parallel performance
| Authors | Yuri Ozhigov |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9904039 |
| URL | https://arxiv.org/abs/quant-ph/9904039 |
Abstract
Given a sequence $f_1 (x_1), f_2 (x_1, x_2), ..., f_k (x_1, ..., x_k)$ of Boolean functions, each of which $f_i$ takes the value 1 in a single point of the form $x_1^0, x_2^0, ..., x_i^0, i=1,2,..., k$. A length of all $x_i^0$ is $n, N=2^n$. It is shown how to find $x_k^0 (k\geq 2)$ using \frac{k\pi\sqrt{N}}{4\sqrt{2}}$ simultaneous evaluations of functions of the form $f_i, f_{i+1}$ with an error probability of order $k/\sqrt{N}$ which is $\sqrt{2}$ times as fast as by the $k$ sequential applications of Grover algorithm for the quantum search. Evolutions of amplitudes in parallel quantum computations are approximated by systems of linear differential equations. Some advantage of simultaneous evaluations of all $f_1 ,... f_k$ are discussed.
{
"annotation_id": "eefb33ab-ece7-4099-8e18-8c055801a194",
"date_created": "2026-03-02T18:02:44.910000Z",
"date_modified": "2026-03-02T18:02:44.910000Z",
"file_hash": "c241eb61197c7430715d01e981365257e2deb1e13d46b8e73a3d821530b8fca2",
"private": false,
"record": {
"abstract": "Given a sequence $f_1 (x_1), f_2 (x_1, x_2), ..., f_k (x_1, ..., x_k)$ of\nBoolean functions, each of which $f_i$ takes the value 1 in a single point of\nthe form $x_1^0, x_2^0, ..., x_i^0, i=1,2,..., k$. A length of all $x_i^0$ is\n$n, N=2^n$. It is shown how to find $x_k^0 (k\\geq 2)$ using\n\\frac{k\\pi\\sqrt{N}}{4\\sqrt{2}}$ simultaneous evaluations of functions of the\nform $f_i, f_{i+1}$ with an error probability of order $k/\\sqrt{N}$ which is\n$\\sqrt{2}$ times as fast as by the $k$ sequential applications of Grover\nalgorithm for the quantum search. Evolutions of amplitudes in parallel quantum\ncomputations are approximated by systems of linear differential equations. Some\nadvantage of simultaneous evaluations of all $f_1 ,... f_k$ are discussed.",
"arxiv_id": "quant-ph/9904039",
"authors": [
"Yuri Ozhigov"
],
"categories": [
"quant-ph"
],
"title": "Speedup of iterated quantum search by parallel performance",
"url": "https://arxiv.org/abs/quant-ph/9904039"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "cb574918-fbe2-474c-bbba-1a317f1a2ff7",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}