dorsal/arxiv
View SchemaEnsemble Algorithm for the Selection Problem by NMR Ensemble Quantum Computers
| Authors | Chien-Yuan Chen, Chih-Cheng Hsueh |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0407109 |
| URL | https://arxiv.org/abs/quant-ph/0407109 |
Abstract
In this paper, we present an ensemble algorithm for selection problem to find the k-th smallest element in the unsorted database. We will search the k-th smallest element by using "divide-and-conquer" strategy. We first divide D, the domain of the database, into two parts, determine which of the two parts the object element sought belongs to, and then concentrate on that part. We repeat divide that part until object element is found. The determination of which part depends on the output of ensemble counting scheme, which outputs the number of assignments satisfying the value of the oracle query function is set to one. Our algorithm modifies the ensemble counting scheme by constructing a new oracle query function g_y(j). We set g_y(j) to one if the j-th element is less than or equal to y. At first, we set y to the middle value of D and perform the ensemble counting scheme with the oracle query function g_y(.) to compute the number C, the number of j satisfying g_y(j)=1. If C>k, the object element lies in the first half of D. If C<=k, then it must be in the second half of D. We recursively apply this method by adapting y until the object element is found. Our algorithm thus requires O(ln|D|) oracle queries for adequate measure accuracy to find the k-th smallest element, where |D| denotes the size of D.
{
"annotation_id": "9c2eba8b-0db9-41a7-b763-34ef08e615bd",
"date_created": "2026-03-02T18:02:10.382000Z",
"date_modified": "2026-03-02T18:02:10.382000Z",
"file_hash": "37c1041cdd3997b6511aac0a748517151bf3c70c368bbd18843ac35e36c8dfc4",
"private": false,
"record": {
"abstract": "In this paper, we present an ensemble algorithm for selection problem to find\nthe k-th smallest element in the unsorted database. We will search the k-th\nsmallest element by using \"divide-and-conquer\" strategy. We first divide D, the\ndomain of the database, into two parts, determine which of the two parts the\nobject element sought belongs to, and then concentrate on that part. We repeat\ndivide that part until object element is found. The determination of which part\ndepends on the output of ensemble counting scheme, which outputs the number of\nassignments satisfying the value of the oracle query function is set to one.\nOur algorithm modifies the ensemble counting scheme by constructing a new\noracle query function g_y(j). We set g_y(j) to one if the j-th element is less\nthan or equal to y. At first, we set y to the middle value of D and perform the\nensemble counting scheme with the oracle query function g_y(.) to compute the\nnumber C, the number of j satisfying g_y(j)=1. If C\u003ek, the object element lies\nin the first half of D. If C\u003c=k, then it must be in the second half of D. We\nrecursively apply this method by adapting y until the object element is found.\nOur algorithm thus requires O(ln|D|) oracle queries for adequate measure\naccuracy to find the k-th smallest element, where |D| denotes the size of D.",
"arxiv_id": "quant-ph/0407109",
"authors": [
"Chien-Yuan Chen",
"Chih-Cheng Hsueh"
],
"categories": [
"quant-ph"
],
"title": "Ensemble Algorithm for the Selection Problem by NMR Ensemble Quantum Computers",
"url": "https://arxiv.org/abs/quant-ph/0407109"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "6f1cb2b0-e6ea-4473-b517-ec84a5f63232",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}