A classical GA sets up a population of solution candidates, which are often referred to as chromosomes. Each chromosome is a solution candidate to the given problem, and its fitness value is calculated in terms of its genes that represent values for variables and elements. In QGA, gene values are encoded in the computational-basis states of one or more qubits, and a sequence of encoded gene values is represented by a quantum register. A quantum chromosome can therefore be understood as a register whose computational-basis states correspond to possible chromosome encodings. Before measurement, this register may exist in a coherent superposition of multiple encoded chromosomes, while a classical chromosome is obtained only after measurement. In the computational basis, a quantum chromosome is basically a state vector formed by tensor products among multiple qubits. At the beginning of computation, the chromosome register of n qubits is initialized as | ψ ⟩ = | 0 ⟩ ⊗ n . Applying Hadamard gates to all qubits prepares the uniform superposition (1) H ⊗ n | 0 ⟩ ⊗ n = 1 2 n ∑ z ∈ { 0 , 1 } n | z ⟩ . The register then has support over all binary strings of length n. In QGA, each basis string | z ⟩ may be interpreted as an encoded candidate chromosome. Quantum gates transform the probability amplitudes of these encoded candidates coherently, and measurement returns classical bit strings according to the resulting probability distribution.

It is a common practice to implement the quantum selection operator with utilization of Grover’s search algorithm (Grover, 1996), one of the relatively well known quantum algorithms for its quadratic speedup capability. Its procedure is divided into two parts, the quantum oracle and the Grover’s diffuser. The oracle encodes and stores the problem function and input data, which then can be processed with successive quantum operations. Building a cost-effective oracle itself is a crucial topic with respect to developing any oracle-oriented quantum algorithm, and we will further discuss the related issues in the later part. The Grover’s diffuser, coming after the oracle, executes the process of amplitude amplification, which selectively amplifies the probability amplitude of the target state, raising the probability to guarantee its measurement at the end of the computation. Theoretically, the Grover’s search can specify the target state with O ( n ) queries from n items (Dürr and Hoyer, 1996). In QGA, the Grover’s search is employed to specify and select chromosomes with the highest fitness values in each generation. A quantum circuit for an overall algorithmic structure for QGA is presented in Fig. 1.

Implementing quantum crossover and mutation operators is relatively difficult in QGA, since uncontrolled interactions or unintended intermediate measurements can cause decoherence, collapse, or noise, thereby disturbing the encoded superposition. In addition, operations analogous to crossover and mutation must be implemented coherently through reversible quantum circuits, often requiring additional registers, controlled operations, and uncomputation (Yanofsky and Mannucci, 2008). Since the processes of crossover and mutation need to address and specify the target chromosomes periodically during computation, reproducing them with quantum computation would require a genuine strategy to bypass the aforementioned limitation.

Equation (1) implies that putting n qubits into uniform superposition generates a series of 2 n strings that consists of every possible binary combination of 0s and 1s of length n. Therefore, theoretically, if the sufficient number of qubits could be utilized to map the problem function entirely, the whole procedure would be reduced to simply searching for the optimum in the space where every possible solution candidate exists. Reduced quantum genetic algorithm (RQGA), referred to as quantum adaptive search outside the QGA literature, was introduced inspired by such methodological reduction (Sun and Xiong, 2014).

In RQGA, the only genetic operator involved is the selection, which is reproduced by Grover-BBHT algorithm, an improvement over the original Grover’s search. The absence of crossover and mutation here is not a procedural omission, but a defining feature of the reduced variant, whose purpose is to regulate circuit depth and qubit consumption by reducing the genetic process to quantum selection. The Grover’s oracle O f is a boolean operator, i.e. with the registers of input and auxiliary qubits | x and | − , respectively, (2) O f | x | − = ( − 1 ) f ( x ) | x | − , which is accustomed to a black-box function f ( x ) : { 0 , 1 } n → { 0 , 1 }, activating a phase flip depending on the evaluation of f ( x ). Roughly speaking, the Grover’s oracle is fed with a question, “Does this state satisfy the given condition (problem function)?” and it returns “yes” or “no” by marking the satisfactory state with a flipped sign. This implies that, for an optimum search problem, a threshold needs to be provided to the oracle to compare with the solution candidates. Indeed, in RQGA, the best solution candidate in each generation is marked as a threshold for the next generation, where it is compared with the next best candidate. Performing this task iteratively would ultimately lead to discovering the near-optimal solutions, negating the necessity of the crossover or mutation procedures as long as the corresponding population is capable of containing the entirety of the possible candidate pool.

Strictly structured quantum genetic algorithm (SSQGA) is a rather recently developed approach to implement QGA, which strictly adopts the algorithmic procedure of classical GA. It maps only part of the problem’s decision space and utilizes all of the genetic operators, including the crossover and mutation, to search the optimum. The algorithm starts with generating a pseudo-randomizer circuit to initialize the population of c chromosomes under non-uniform superposition on n qubits, where c < 2 n applies. The purpose of this approach is to reduce the number of solution candidate states to be processed with the Grover’s diffuser, decreasing the required number of queries to complete the diffusion.

The crossover operation in SSQGA is enabled by generating two identical populations sets (3) | ψ = | P 1 ⊗ | P 2 = 1 c ∑ i = 1 c ∑ i = 1 c | a 1 a 2 | x 1 x 2 , where the population sets | P 1 and | P 2 are equal, and a k is an index register to a chromosome register x k in each population | P k . The chromosome registers are then halved as | x 1 left x 2 right | x 2 left x 1 right , allowing pseudo-swaps between qubits with the same index value by placing a series of CNOT gates. A subsequent study proposes an improved version of this structure by preserving a number of qubits in the chromosome register to significantly reduce the population size. Lastly, the mutation operation in SSQGA is implemented by applying X gates to specific qubits in the chromosome register.

In practice, QGA is generally built upon the computational basis, which takes the state vector | ψ of each qubit as (4) | ψ = α | 0 + β | 1 , where α and β are the probability amplitudes of | 0 and | 1 that must satisfy α 2 + β 2 = 1. This implies that, in order to encode classical data into a quantum circuit, it needs to be converted into a form of binary string q 0 q 1 q 2 … q n , q i ∈ { 0 , 1 }, which then can be mapped into qubits. To allow decoding the result of the quantum computation back to the classical format, an index is assigned to each quantum chromosome, which acts as an indicator that can be referred to for tracking the solution’s address in the original data. Consequently, encoding classical data into a quantum circuit requires proper allocation of qubits to the index arrangement and chromosome value mapping. n i d x qubits in an index register are put into uniform superposition to generate 2 n i d x indices, while n v a l qubits in a value register are connected with the index qubits via CNOT gates to represent n v a l genes accordingly with the corresponding indices.

Since GA is a heuristic optimization algorithm that stochastically chooses solution candidates from the search space, the following lemma holds.

In other words, as to continuous function-based problems, one must guarantee n v a l ⩾ n i d x in order to fully differentiate the chromosomes in terms of their relative fitness values. Overall, QGA requires k · n idx qubits to generate up to 2 n idx individuals with a constant k ⩾ 2 that could vary depending on the method of encoding and addition of auxiliary qubits for subsequent computations. While the difference in k is trivial asymptotically in terms of the number of qubits, as it is bounded to O ( n idx ), the difference in terms of the number of chromosomes could be significant, since it grows exponentially with the number of qubits, i.e. it is safe to claim that O ( 2 k 1 · n idx ) < O ( 2 k 2 · n idx ) if k 1 < k 2 . An appropriate management over the numbers of qubits and generable chromosomes thus appears to be a crucial matter in building a practical QGA with respect to its required implementation cost.

A continuous function f : R n → R is based upon an indefinite domain, where the infinite amount of input possibilities exists. For solving an optimization problem of such a kind, the methodology of RQGA, that the whole procedure can be reduced to selecting the optimum from a set of all the possible solution candidates, has its limitation, since it is virtually impossible to designate a finite set for input values from a continuous domain. This matter of search space presentation appears to be especially critical in QGA and many other quantum algorithms, where qubits are essentially scarce and their proper distribution to various operations is necessary (Giri and Korepin, 2017). While quantum superposition allows generation of exponentially numerous solution candidates with respect to the number of qubits in the index register, it is important to recall that at least the equal number of qubits needs to be assigned to the value register in order to distinctively present the features of candidates on the decision space, which in most cases consists of real numbers with multiple digits. The fact that n v a l has n idx as a lower bound for continuous functions infers that increasing the population size raises the minimum number of qubits required for value presentation as well, expanding the overall qubit consumption in two-folds.

Our proposed method to handle the issue explained in the last subsection is largely based on dimension-wise discretization of the search space, which transforms the coordinates of solution candidates along each axis to countable measures. Although the presented implementation is incorporated into the reduced variant of QGA, the proposed dynamic encoding scheme is not restricted to RQGA, since it modifies the representation of the candidate search space before the selection process and can therefore be combined with other QGA variants that include crossover or mutation operators. This approach of approximation, derived from the following lemma, allows to represent the candidates distinctively with the limited number of available qubits.

With Lemma 2, the search space can be described by coordinate vectors that are uniformly placed along each dimension, acting as approximate coordinates generated by superposition of the index qubits. n idx d qubits are assigned to each dimension to place 2 n idx d vectors, and every intersection between two vectors is regarded as a solution candidate. Overall, 2 n idx candidates in total can be generated with n idx qubits in the index register, forming a population. The task of the selection operator in QGA is then to evaluate the fitness of these candidates and specify the best one, which can be represented by the corresponding vectors’ binary indices.

It is important to distinguish the role of the adaptive search region from the quantum component of the proposed method. The contraction and expansion of the search range is a classical control mechanism, and similar ideas appear in adaptive grid refinement, pattern search, and trust-region optimization. Our method intends not to emphasize the use of local refinement itself, but the way such refinement is coupled with QGA encoding. At each generation, the computational basis states of the index register are mapped to coordinate vectors in the current search region. Therefore, the same set of quantum states represents different physical coordinates as the region changes. This allows the algorithm to increase the effective coordinate resolution locally without globally increasing the number of qubits to represent the entire continuous domain.

Sporadic placement of coordinate vectors in the continuous search space implies that there is a high probability that the global minimum is not collinear with any of the vectors that form the approximate grid. This loss of information caused by the approximation can be reduced by gradually decreasing the size of the search space.

Lemma 3 supports a geometric interpretation of region contraction: when the number of grid points is fixed, reducing the search radius increases the density of candidate points in the current region. It does not imply that the global optimum of the original domain remains inside the contracted region; rather, the direct consequence for the proposed encoding scheme is instead a local approximation property: if the relevant optimum lies inside the current search region, then the uniformly encoded grid can approximate the best point in that region more closely as the region radius decreases.

The bound above is conditional on the relevant optimum remaining inside the current search region. Let x ∗ denote the global minimum in the original domain and suppose x ∗ ∈ S t . After the selection step, the proposed method constructs the next search region as (5) S t + 1 = [ g t − r t + 1 , g t + r t + 1 ] d , where g t is the selected candidate. Then x ∗ remains inside the next search region if and only if (6) ‖ g t − x ∗ ‖ ∞ ⩽ r t + 1 . Therefore, contraction is considered safe when the selected candidate is sufficiently close to the global minimum. If this condition is violated, the global optimum is likely to be excluded from the next search region and subsequent contractions cannot recover it unless an expansion, restart, or multi-region search mechanism is applied.

We can expect that in a smaller search space, the coordinate vectors will be placed with higher density that probabilistically decreases their Euclidean distances from the minimum inside the space. In other words, theoretically, through repetitive shrinking of the search region, the grid resolution within that region increases, thereby reducing the local discretization error when the target optimum remains inside the region. The best candidate in each generation becomes the centre of the search space for the next generation, which is bounded by other candidate points that are adjacent to the centre candidate on the plane of the approximated space in every dimension. We deem that this methodology is plausible in a sense that the arbitrary local optima are likely to exist within the bounded area due to the approximity of the solution candidates. The overall procedure of the proposed method is pictured in Fig. 2 along with its pseudo-code in Algorithm 1.

Admittedly, our approach described in the last subsection does not guarantee that the global minimum would remain inside the search space under all circumstances. Let x ∗ be the global minimum and let g t be the candidate selected by quantum adaptive search from the approximate grid G t . If g t lies in the basin of a local minimum and the contracted region centred at g t does not contain x ∗ , then the algorithm becomes restricted to a subregion from which the global minimum is unreachable by further contraction alone. This can occur when the current grid is too coarse to place a candidate sufficiently close to the global basin, or when a local basin contains grid points with better observed fitness values than the available grid points near the global minimum.

We introduce an expansion mechanism to reduce the risk described above. When the best fitness value does not improve for a prescribed number of generations, the search region is expanded in order to recover candidate areas that may have been excluded by previous contractions. This mechanism increases the opportunity to escape from local minima, although it does not by itself guarantee global convergence for arbitrary non-convex or non-Lipschitz functions. A formal global convergence guarantee would require additional techniques, such as repeated coverage of the original domain, a restart policy with nonzero probability of sampling every relevant region, or a multi-region search procedure that maintains several candidate basins simultaneously, which are the commonly suggested practices among various heuristic optimization studies.

In an environment where the abundant number of qubits can be utilized, the aforementioned issue of multimodality could possibly be solved by adopting parallel processing upon multiple intersections of the coordinate vectors. This setting would allow to proceed with multiple search spaces concurrently, and their locations can be decided by the observation counts of the state vectors on multiple measurements of the circuit. Several copies of the circuit that implements our method would be needed to run this procedure.

We used IBM Qiskit (Abraham et al., 2019) to set up a quantum simulation environment and to implement our method in it. For result clarification purposes, we chose to run our program with Qiskit Aer StatevectorSimulator, which supports up to 30 simulated qubits in a state vector form. The oracle includes the in-built IntegerComparator function that requires n v a l ancilla qubits, raising the total number of qubits in the index and value registers to 3 · n idx . Since two qubits are spared for the task of specifying target states via phase-flip, the maximum possible number for n idx is 9. Such scarcity of qubit indicates that running the simulation upon complex real-world problems would be impractical and hardly produce any meaningful results. Therefore, we decided to conduct the experiment upon four benchmark optimization problem functions, Rosenbrock (Rosenbrock, 1960), Rastrigin (Hoffmeister and Bäck, 1991), Ackley (Ackley, 1987), and Sphere (Picheny et al., 2013). Each function is set as 2-dimensional with up to 4 index qubits assignable to each dimension, generating 16 coordinate vectors at the maximum.

In order to measure the comparative performance of the proposed method, we implemented the standard RQGA and SSQGA under the same setting. Our method and RQGA would start with n idx = 4 and add two additional index qubits to their circuits each time the found minimum has remained the same for more than 3 generations. SSQGA, on the other hand, starts with n idx = 8 because it requires two population sets from the beginning. With n idx = 4 initial index qubits, SSQGA would be allowed to generate only 4 chromosomes for each of the initial populations, which we deem is unsuitable for measuring the algorithm’s practicality. All three algorithms were given 50 generations to perform the optimization task, and the whole procedure was iterated 10 times to assess their average performance. An elitist strategy is chosen, with which the best candidate in each generation is saved and compared with the next one, replacing it if better.

The benchmark functions used in our experiment generally assume a relative small search space. For example, it is a common practice to evaluate the Rastrigin function on a hypercube of x i ∈ [ − 5.12 , 5.12 ] (Naser et al., 2025). Since one of our aims is to rate the scalable practicality of the quantum algorithms with the limited amount of resources, we set the initial search ranges r relatively larger, by x i ∈ [ − 10 , 10 ] with r = 10 and x i ∈ [ − 20 , 20 ] with r = 20. For our method, the ranges are continuously changed, depending on the optimization tendency. Each algorithm was tested on both ranges to observe the relative performance in varying size of the search space.

The present experimental evaluation is intended as a proof-of-concept comparison among QGA-based methods under the same simulated-qubit constraint, and it is not designed as a comprehensive benchmarking study against classical continuous optimization algorithms. In particular, we do not intend to include classical adaptive or evolutionary optimizers as baselines for comparison. Therefore, the results reported in this section should be interpreted as evidence of improvement over the selected QGA variants tested here, namely RQGA and SSQGA, rather than as evidence that the proposed method is competitive with classical counterparts.

Figure 3 shows the graphs of optimizing progresses done by our method (titled as QuASAR, an acronym for Quantum Adaptive Search in Approximate Region), RQGA, and SSQGA on the benchmark functions over 50 generations. A logarithmic scale is applied to the Fitness axis to cover the broad range of values. For the functions of Rosenbrock, Ackley, and Sphere, our method with r = 10 achieves the lowest minimum found, while for Rastrigin our method with r = 20 performs better. Table 2 is provided to list the numerical end results from all three algorithms, each presenting two cases of r = 10 and r = 20 along with the true global optimum of the functions. The lowest minimum for each function is marked as bold. Note that “Rosen.” and “Rastrig.” are truncated terms for Rosenbrock and Rastrigin, respectively.

To make a further analysis on the overall qubit requirement of the proposed method and other QGA techniques, we counted the cumulative number of simulated qubits used for each algorithm during optimization. The consumption growth on the Ackley function is plotted on the graph in Fig. 4 as a visual reference, and the final counts are presented in Table 3. Again, the lowest cumulative count for each function is marked as bold, which in every case belongs to our method.

The metric of cumulative qubit usage is used here as a simulator-level measure that reflects how many active qubits are used across generations as the register size changes during the optimization process. The actual hardware-relevant qubit requirement is determined by the maximum active circuit size, which is limited up to 30 qubits for all compared methods under the largest tested setting. Therefore, Table 3 should be interpreted together with the final fitness results in Table 2: the main advantage of the proposed method is not a large reduction in maximum qubit count, but an improved optimization accuracy under essentially the same qubit constraint.

Our method is implemented within the reduced-QGA structure, which deliberately omits the genetic processes of crossover and mutation for the purpose of qubit sparing, and therefore relies primarily on quantum selection. A likely negative effect of such an approach is reduction to an elitist random sampling, since the result in one generation would barely provide any feedback to the next population (Chiesa et al., 2020). Our method compensates such a deficiency by iterative contraction of the search space towards the global minimum, which contributes to an effective exploration over the space with a limited population size. The effect of the proposed approach is relatively more evident in (c) and (d) in Fig. 3, where our method demonstrates a considerable degree of convergence at the early stages of optimization. For the case of r = 10 every algorithm generally performs better, and we speculate that even for the Rastrigin function in (b) our method with r = 10 would have eventually outperformed the case of r = 20 if a longer series of generations were provided.

SSQGA, for both cases of r = 10 and r = 20, appears to have performed the worst among the test approaches, as we initially expected. The largest contributing factor to this result, to our knowledge, should be the exceptionally small size of its population, which can only contain 16 chromosomes even with the maximum possible number of the index qubits limited by the experiment setup. While there still is a possibility that its performance would dramatically improve if given a sufficient number of qubits for generating the population, its structural constraint that requires two identical sets of population needs to be resolved for the sake of its cost efficiency, especially with regard to the fact that RQGA, which totally lacks the unique and presupposed advantage of having all the possible solution candidates in its search list, still slightly outperforms it.

Fig. 4 and Table 3 show that the amount of qubit usage saved by adopting our method is rather trivial, and it is expected that the difference would be nearly indistinguishable in case large and complex problems are to be solved. Therefore, the resource advantage of the proposed method should be interpreted carefully. The proposed method does not substantially reduce the maximum qubit count required by the underlying RQGA-style circuit; rather, its advantage lies in using a comparable qubit budget to perform a more precise continuous-domain search through dynamic reuse of the same index register over successively refined local regions.

For a fixed value of n idx , the proposed method uses the same selection-oriented circuit structure as RQGA: the same type of index register, value register, comparator ancilla, oracle marking, and Grover-type amplification are employed. The dynamic encoding scheme changes the classical mapping between index states and coordinate values in the current search region, but it does not introduce additional quantum genetic operators or extra quantum registers. Consequently, its circuit depth, gate count, number of measurements, and simulation runtime are expected to be of the same order as those of RQGA under the same register size and oracle implementation. When the same encoding scheme is incorporated into other QGA variants, its circuit-level resource requirements would likewise follow the requirements of the corresponding base variant.

It is important to note that the presented resource analysis is based on a simulation, not a hardware-oriented experiment. In particular, there are several key factors, including circuit depth, gate counts, oracle gate complexity, finite-shot measurement statistics, total number of circuit executions, and sensitivity to realistic device noise, that need to be assessed to assure the method’s optimality and practicality on real quantum devices. Since the experiments were performed using Qiskit Aer StatevectorSimulator, no finite-shot sampling noise or quantum device noise model was included. Runtime on a classical statevector simulator should be further analysed to be used as an evidence of quantum runtime efficiency, since it currently depends on the simulator implementation and the classical hardware environment. These analyses are left for future work.