In this paper
AbstractIntroductionBackgroundGrover’s AlgorithmQuantum Cost MetricsFinite Automata and State AssignmentWeighted Hamming Distance Cost FunctionQuantum Oracles with Angular Rotational CountersAngular Rotational Counter (ARC)Mathematical Correctness of ARCRelationship Between Objective and Measurement ProbabilitiesApplication to State AssignmentOracle with ARCARC as the Cost CalculatorOptimization AlgorithmExperimental MethodologyBenchmarksBoolean-Based Oracle as BaselineTranspilationMetrics and Percentage CalculationResultsDiscussionCircuit Cost in Comparison to Boolean-Based MethodsObjective Functions and Measurement ProbabilitiesComplexity AnalysisComparison of State Assignment with ARC to Classical AlgorithmComparison of State Assignment with ARC to Previous WorkFuture DirectionsConclusionsAcknowledgmentsReferencesWorksPhysics and Astronomy
Rotational Encoding of Objective Functions for Quantum Optimization
Abstract
In this paper, we introduce the Angular Rotational Counter (ARC), a novel approach to represent objective functions that can be decomposed as a weighted sum of Boolean functions. ARC encodes the objective as an accumulated sum of quantum rotations onto a single-qubit register instead of a multi-qubit register used in much of the previous literature. We mathematically establish and experimentally validate that these rotations sum to the objective value for all possible solutions and derive the relationship between the resulting measurement probabilities and the objective. This design was applied to construct a quantum oracle for the state assignment problem of finite automata and state machines using a weighted Hamming distance cost function, which is a special case of the quadratic assignment problem. We evaluate this oracle design on 26 benchmarks and compare it with corresponding Boolean-based oracles on four cost metrics. Across these benchmarks, the oracle with ARC produces a mean reduction in the qubit count of 20.8%, gate count of 89.3%, circuit depth of 92.4%, and quantum cost of 90.6%. These results demonstrate substantial reductions in circuit cost for the evaluated benchmarks and establish rotational encoding as a promising approach for representing objective functions in optimization based on quantum search algorithms.
Introduction
Quantum search algorithms, including Grover’s algorithm [1, 2, 3, 4, 5, 6], quantum walk-based search algorithms [7, 8], and BHT-QAOA [9, 10], have been proven to require less queries than classical exhaustive search. These algorithms are applicable to many constraint satisfaction problems (CSPs) through the construction of problem-specific oracles [11, 12, 13, 14]. The practicality and performance of these algorithms, however, are critically dependent on the realization and cost of these oracles. Furthermore, additional components are necessary for these oracles when they are designed for optimization problems.
In previous research on applying quantum search algorithms for combinatorial optimization problems [12, 13, 15, 16, 17], the resulting algorithms were based on repeated, adaptive executions of an oracle-based search algorithm, such as Grover’s search algorithm and quantum random walk. Many of these presented oracles [12, 13, 14, 17] were entirely Boolean-based and were created based on CSPs. Such oracles use quantum reversible gates to create logical, arithmetic, or comparison operations to determine whether a candidate solution satisfies each constraint. For this reason, these oracles can identify valid solutions, but cannot compare the valid solutions against each other. Therefore, optimization problems were framed as iterated CSPs with a threshold (for the objective function) as an additional constraint. An oracle designed for an iterated CSP computes the objective value using arithmetic operators implemented through reversible logic and encodes the resulting value onto a multi-qubit register. The oracle then employs a comparator to evaluate the computed objective value against a predefined threshold. Depending on the optimization objective, a less-than () comparator is used for minimization problems, whereas a greater-than () comparator is used for maximization problems. Hybrid classical-quantum algorithms are constructed by iteratively executing a quantum search algorithm while repeatedly updating the threshold. Although these oracles explicitly compute objective values, resulting in direct access to these values, their implementation requires additional ancilla qubits (temporary working registers) and multiple arithmetic and comparator gates, all of which further increase the circuit cost and depth. These costs depend on the objective function values, their size, and the implementation of the arithmetic and comparator gates. Such costs become more significant as the objective function value increases in size and complexity. An alternative representation that incorporates the information on the objective directly into quantum operations could therefore reduce the cost of such oracles.
In this work, we introduce the Angular Rotational Counter (ARC), a circuit design that rotationally encodes objective functions that can be decomposed into a weighted sum of Boolean functions. It encodes such objective functions through an accumulated sum of quantum rotational operations. Instead of explicitly computing the objective onto a conventional multi-qubit register as a binary value, ARC associates each term in the objective function with a rotational operation, and the measurement probability of the ARC output depends on the objective value of the candidate solution. Oracles with ARC are executed within a quantum search algorithm, such as Grover’s algorithm, to obtain optimized solutions based on the encoded objective function.
To study the practical applications of our introduced rotational encoding, we investigate quantum oracles with ARC based on a heuristic weighted Hamming distance cost function [18, 19, 20], a special case of the quadratic assignment cost function [21, 22, 23, 24], in the context of the state assignment problem [12, 18, 19, 20, 24, 25] for classical and quantum finite automata and state machines [26, 27, 28, 29, 30]. State assignment, also known as “state encoding,” is a fundamental optimization problem in structural automata synthesis and digital design. The assignment of binary encodings to automaton states directly influences the implementation cost and the resulting circuit complexity. Previous work on creating an oracle for finding the minimal encoding of the states of an automaton was discussed in [12], which presented a quantum Boolean-based oracle to encode states and inputs based on dependencies on input variables and a repeatedly updated threshold. However, in [12], their method contains many expensive multi-qubit gates and restrictions on applicability: the number of states and inputs had to be powers of two, and the automaton had to be completely specified Boolean functions. Our oracle with ARC does not have these restrictions.
The benchmark results demonstrate substantial reductions in quantum circuit resource requirements for the implementations with ARC compared with their corresponding quantum Boolean-based oracles. Across the 26 finite state machine benchmarks, the arithmetic mean reductions are 20.8% in qubit count, 89.3% in gate count, 92.4% in circuit depth, and 90.6% in circuit cost after transpilation. These results demonstrate the advantages of the oracles with ARC over their Boolean-based counterparts in terms of cost-effectiveness and resource efficiency. Although the observed improvements indicate substantially more compact quantum circuit implementations, they do not, by themselves, establish corresponding reductions in physical execution time or demonstrate an asymptotic quantum speedup. Nevertheless, the substantial reductions in quantum circuit resources motivate further investigation into rotational encodings of objective function values as an alternative to explicit binary encoding. Moreover, the applicability of ARC and its corresponding oracle designs is not limited to the benchmarks and problems considered in this study and may extend to other general classes of problems.
The main contributions of this paper are as follows.
Rotational encoding of decomposable objective functions: We introduce ARC as a method to represent objective functions that can be decomposed into a weighted sum of Boolean functions. ARC encodes the objective function as an accumulated sum of quantum rotational operations onto a single-qubit register, in contrast to conventional methods that explicitly compute the objective value in binary onto a multi-qubit register. Not only does this reduce the cost of the oracle, but it also introduces a rotational encoding of objective functions that can be utilized for optimization.
Mathematical model of ARC: We demonstrate the accumulated sum of the objective-dependent rotations and formalize the resulting output qubit of ARC for candidate solutions. We also derive the conditions under which the measurement probability is monotonic with respect to the objective function value. This proves that the output qubit of ARC optimizes the measurement probabilities with respect to the objective function value for candidate solutions.
Application and analysis of oracles with ARC for the state assignment problem: We construct oracles with ARC for the state assignment problem based on a heuristic weighted Hamming distance cost function, which is a special case of the cost function in the quadratic assignment problem. This demonstrates the applicability of ARC to important optimization problems.
Evaluation of state assignment oracles: We compare oracles with ARC against corresponding Boolean-based oracles for state assignment on four circuit cost metrics, namely qubit count, gate count, circuit depth, and Transpilation Quantum Cost (TQC) [31, 32, 33, 34]. Our results show cost reductions across all 26 evaluated benchmarks.
The remainder of this paper is organized as follows. Section 2 reviews the essential background on Grover’s algorithm, quantum cost, state assignment, and the weighted Hamming distance cost function. Section 3 presents the proposed Angular Rotational Counter (ARC) circuit with its mathematical representation. Section 4 applies ARC to construct the oracle for the state assignment problem. Section 5 details the experimental methodology used to evaluate such state assignment oracles. Section 6 presents the results. Section 7 discusses and analyzes the implications of our proposed approach. Lastly, Section 8 concludes this paper.
Background
Grover’s Algorithm
Classical computing methods to search through an unsorted dataset grow linearly in time complexity with the dataset size. However, in quantum computing, Grover’s algorithm [1, 4, 5, 6] can search through a search space of size with a query complexity [35] of , which is the number of queries the algorithm makes to the oracle. This algorithm searches through an unsorted dataset to find an element that satisfies the oracle, which is the fundamental block for creating quantum and hybrid classical-quantum algorithms for CSP and combinatorial optimization problems. This section presents the general structure of Grover’s algorithm.
Grover’s algorithm first applies Hadamard gates to all input qubits, creating a superposition that represents the entire search space. Then, these superposed inputs are run through the oracle. An oracle in Grover’s algorithm characterizes the target solutions, which are specific to the problem, by marking them.
A common type of oracle is a Boolean oracle [1, 5, 6], which outputs if the inputs are a solution and outputs if not. The output of is conceptually represented by a Boolean function and is realized using quantum reversible gates [14, 36, 37]. After the oracle , the controlled-diffusion operator [6] is applied, which increases the probability of measuring inputs that correspond to solutions, based on the Boolean outputs of . The combination of the oracle followed by the controlled-diffusion operator is called the Grover operator . After approximately iterations of (where is the size of the search space and is the number of solutions), the probability of measuring the target solution approaches 1. The complete construction of Grover’s algorithm with a Boolean oracle and controlled-diffusion operator is illustrated in Figure 1. There are other types of quantum oracles, such as the phase oracle [1, 5, 6, 9] (which uses the standard diffusion operator , not the controlled diffusion operator). In this paper, a modified version of the Boolean oracle is utilized.
Figure 1. The circuit for Grover’s algorithm, which consists of Hadamard gates followed by approximately iterations of Grover’s operator , where is the size of the search space and is the number of solutions.
Quantum Cost Metrics
The cost of a circuit can be calculated in many ways, such as qubit count, gate count, depth, and Transpilation Quantum Cost (TQC) [31, 32, 33, 34]. All of these metrics will be used for evaluation.
The qubit count of a circuit is the number of qubits it contains. Because of the limited size and noise of quantum computers, it is important to have circuits with a small number of qubits and gates to prevent decoherence [38, 39]. The gate count is the total number of gates, and it is usually calculated after all gates are decomposed into native gates, which are the supported operations the quantum hardware runs on. However, it is important to note that some gates are more expensive than other gates. Depth is the critical longest path of the gates along a transpiled circuit. The Transpilation Quantum Cost (TQC) is a metric that calculates the quantum cost of a circuit after transpilation. The TQC of a circuit is determined by Eq. (1), where is the number of native single-qubit gates, is the number of native double-qubit gates, is the number of SWAP gates [40, 41], and is the depth.
Finite Automata and State Assignment
The state assignment problem for finite automata and state machines [12, 18, 19, 20, 24, 25] is an important problem that greatly impacts the cost of realizing automata in classical and quantum technologies. There is both the abstract theory of automata [29, 30] and the structural theory of automata [26, 27, 28]. This problem is one of the most fundamental problems in the structural theory of automata, and it is stated as follows.
Given: An automaton with states , where is the number of states.
Goal: Find the state encodings so that the physical realization of the automaton is close to minimal in cost, where is the encoding of state and .
Constraint: For all , . In other words, the state encodings must be distinct for each state.
The state encodings affect the cost of the resulting circuit. The optimal encoding is affected by the hardware technology.
Weighted Hamming Distance Cost Function
In the literature [18, 19, 20], an effective heuristic cost function for state assignment is one based on a weighted sum of the Hamming distances (HDs) between state encodings. Algorithms minimize this cost function to approximate the solution. Hamming distance is defined in Eq. (2), where is the th bit in the encoding and is the length of the encodings. The weighted Hamming distance cost function is defined in Eq. (3), where is the weight between the encodings and .
There are different methods of assigning weights. One approach is to let equal the total number of transitions between state and . This approach is simpler and suitable for counters, autonomous machines, and flowcharts [26]. It can be applied to both classical and quantum automata. Another approach is to let be the sum of the number of literals in the transition function from state to and the transition function from state to . A standard approach is to use the minimal Sum of Products (SOP) expression [42, 43, 44] for a classical automaton realization and an Exclusive-or Sum of Products (ESOP) [45, 46, 47] expression for a quantum automaton realization. These expressions can be calculated using classical or quantum algorithms.
Quantum Oracles with Angular Rotational Counters
The oracle is a fundamental part of many quantum search algorithms, such as Grover’s algorithm [1, 4, 5, 6] and BHT-QAOA [9, 10]. This section introduces the concept of an Angular Rotational Counter (ARC) and its application in quantum oracles for transforming search algorithms into optimization ones.
This method is designed for combinatorial optimization problems with objective functions of the form expressed in Eq. (4), where , is a weight, and is a Boolean function. This covers a broad class of objective functions, and many functions, such as the weighted Hamming distance cost function, can be decomposed into this structure.
Angular Rotational Counter (ARC)
In this paper, we introduce the Angular Rotational Counter (ARC) as an approach for computing objective functions in combinatorial optimization problems using quantum circuits. The ARC circuit computes a rotational encoding of Eq. (4).
The structure of the ARC circuit is illustrated in Figure 2. The input is the candidate solution , which is a binary vector. For an objective function described by Eq. (4), each function is realized in the circuit on a single qubit. This qubit then acts as a control for a rotational gate with angle radians, where , that is applied to the output qubit with an initial state of . Note that both controlled- and controlled- gates can be used in ARC, but the axis of rotation must be consistent throughout the circuit. Controlled- gates are used in this paper. Each controlled- represents an increment of , since the rotation of is applied if , and no rotation is applied if . The accumulated angle of rotation after all controlled- gates is
Figure 2. The Angular Rotational Counter (ARC) circuit.
Mathematical Correctness of ARC
This section mathematically shows that the ARC circuit rotationally encodes the objective function for a superposition of inputs. Theorem 1 proves that the effect of the ARC circuit on the output qubit is equivalent to applying a quantum rotational operation with an angle proportional to for a single candidate solution (the input), and it thus demonstrates that the ARC circuit rotationally encodes . Note that the ARC circuit is implemented using controlled- gates, but the outcome of the circuit is equivalent to applying a single gate to the output qubit with an angle proportional to . Theorem 2 proves that, for a superposed input, the final state of the input qubits and output qubit is an entangled superposition of the corresponding inputs and outputs for each basis state.
Theorem 1. For a single candidate solution as the input, the final quantum state of the output qubit of an ARC circuit is determined by Eq. (5), where the initial state of the output qubit is and .
Proof. Let be the state of the output qubit before the controlled- gate. The result of applying the controlled- gate on the control qubit with state and target qubit with state is expressed below, where represents the Boolean negation of .
From Eq. (6), it can be found that the control qubit with state remains unchanged after the controlled- gate, and Eq. (7) can then be derived (where , the identity operator). Eq. (7) proves that the controlled- gate encodes the term.
Applying Eq. (7) for all values of results in the following equation.
The composition of rotations is equal to a single complete rotation, i.e., . Therefore, . Using the definition of from Eq. (4), .
Theorem 2. For a superposition of candidate solutions as the input, the final quantum state of the entangled input and output qubits of an ARC circuit is determined by Eq. (8), where the initial state of the output qubit is .
Proof. Theorem 1 states that for a single candidate solution , , and thus the final state of the input and output qubits is . Therefore, based on linearity, the final state is for the superposed input .
Relationship Between Objective and Measurement Probabilities
The ARC circuit optimizes the measurement probability of 1 with respect to the objective function . It performs either maximization, as proven in Theorem 3, or minimization, as proven in Theorem 4, depending on .
Theorem 3. If , then the measurement probability of 1 in monotonically increases on an interval , where , with respect to .
Proof. From Theorem 1, the final state of the output qubit with is
The probability amplitude of for is , which has a period of .
The measurement probability of 1 is . Because is positive and monotonically increases on the interval with respect to , is monotonically increasing on the interval with respect to .
Theorem 4. If , then the measurement probability of 1 in monotonically decreases on an interval , where , with respect to .
Proof. From Theorem 1, the final state of the output qubit with is
The probability amplitude of for is , which has a period of . The measurement probability of 1 is . Because is positive and monotonically decreases on the interval with respect to , is monotonically decreasing on the interval with respect to .
The graph of the measurement probability of 1 in is illustrated in Figure 3a if and Figure 3b if . Theorem 3 proves that if , as the objective of a solution increases, the measurement probability increases. Therefore, if is set to the maximum possible objective, then for all solutions, those with a higher objective value are selected with a higher probability after measurement. Therefore, ARC maximizes the measurement probabilities of solutions. In the case where , as proven in Theorem 4, the opposite effect takes place: as the objective of a solution increases, the measurement probability decreases. Hence, ARC minimizes the measurement probabilities of solutions instead.
Figure 3. The relationship between and on the interval , where is the probability of measuring 1 in the state and is the objective function.
On the one hand, Boolean-based oracles can distinguish between the inputs that are solutions and those that are not, and thus they can solve constraint satisfaction problems (CSPs). However, they cannot distinguish between the costs of the solutions, and thus cannot optimize them. For this reason, with such oracles, Grover’s algorithm is required to be executed multiple times with a repeatedly updated threshold.
On the other hand, in an oracle constructed using ARC, such an oracle not only finds solutions (through the Boolean-based realizations of constraints) but also optimizes the cost (through the ARC circuit). The main properties of the ARC circuit are summarized as follows.
If the output qubit is initialized to , the measurement probability of 1 in the output of ARC increases as the objective increases for (see Theorem 3). This proves that the oracle maximizes the measurement probabilities of solutions based on their objective values, yielding higher probabilities for those with higher objective values.
If the output qubit is initialized to , the measurement probability of 1 in the output of ARC decreases as the objective increases for (see Theorem 4). This proves that the oracle minimizes the measurement probabilities of solutions based on their objective values, yielding higher probabilities for those with lower objective values.
Using the ARC circuit in the oracles of quantum search algorithms is a general approach to solve optimization problems.
Application to State Assignment
This section applies the methodology of oracle construction detailed in the previous section to the state assignment problem.
Oracle with ARC
This subsection discusses in detail the construction of the oracle with ARC for state assignment. A full outline of the oracle is illustrated in Figure 4, and each section is listed below.
Figure 4. The quantum oracle for the state assignment problem with a cost calculator based on our Angular Rotational Counter (ARC), where is the number of states.
State Encodings (): These collectively form the input to the oracle. The Hadamard gates that precede the oracle in Grover’s algorithm generate a superposition of all possible state encodings for a given automaton. represents the encoding for state .
Encoding Checker (): This circuit outputs if all state encodings are distinct. This is achieved by checking every pair of state encodings. Note that it is crucial to check that the encodings are distinct for each state because Grover’s algorithm generates a superposition of all possible state encodings with Hadamard gates.
Cost Calculator (): This circuit rotationally calculates the total cost, based on a weighted sum of the Hamming distance (HD) between each pair of state encodings. This circuit is an Angular Rotational Counter (ARC).
SAT Toffoli Gate: This gate is used to verify that all constraints are satisfied. The constraints are to have distinct encodings (output of ) and to have optimized cost (output of ). The target qubit of this Toffoli gate is the final output of the oracle.
Mirror Gates ( and ): These gates are used to reverse (uncompute) the input and ancilla qubits back to their initial state for the diffusion operator and measurement.
ARC as the Cost Calculator
A major part of this quantum oracle is the circuit for calculating the cost of the encoding. The construction of the cost calculator as an ARC circuit is detailed in this section. Figure 5 illustrates the use of ARC for counting the cost , based on Eq. (3), where represents the weight for , which is the HD between and . The net rotation from the controlled- gates is
Figure 5. The ARC-based cost calculator in the oracle.
The cost calculator circuit is composed of multiple circuits that calculate the weighted HD between state encodings. Each of these circuits corresponds to two state encodings: and . These circuits calculate the HD between these encodings and weigh it by . The HD between these two encodings was defined in Eq. (2). The following steps are taken to calculate the HD using an ARC circuit.
For each index , will be compared to .
If the values are unequal, then a rotation of (corresponding to the weight ) is applied to the counter.
The final angle of the counter is , which corresponds to the term .
When comparing bits and , the expression represents . This expression can be realized in a quantum circuit through CNOT gates. The qubit with state serves as a control for the rotational gate, which will add a rotation of radians to the counter if , as illustrated in Figure 6. A second CNOT gate is then added in order to return the qubit with state to its initial state of . This circuit can be repeated for all to create the circuit that calculates the total weighted HD between two encodings, as shown in Figure 7. The net rotation created by the controlled- gates is . This circuit is repeated for each pair of states to construct the full cost calculator.
Figure 6. A component of the circuit for calculating HD. It checks for inequality between and .
Figure 7. The circuit for calculating the weighted HD with weight between the state encodings and .
Optimization Algorithm
This section formalizes the algorithm for state assignment using an oracle with ARC. For this algorithm, we use our developed controlled-diffuser operator , as discussed in our research [6]. The algorithm, in words, is explained below. The pseudocode of this algorithm is detailed in Algorithm 1. A similar approach based on our BHT-QAOA [9, 10] can be achieved, also as a classical-quantum algorithm. Example 1 demonstrates a simulated execution of this algorithm.
Create the oracle .
Initialize the circuit for with the following qubits.
superposed input qubits, where is the number of states.
ancilla qubits that are all initialized to .
One output qubit that is initialized to .
Create the encoding checker .
Create the cost calculator .
Set .
Create the SAT Toffoli gate.
Mirror (uncompute) gates.
Add the inverse of the cost calculator .
Add the inverse of the encoding checker .
Grover’s algorithm with the created oracle is then executed with the query complexity , where . Then, the input qubits are measured.
Choose solutions based on the highest measurement probabilities.
Check solutions.
Example 1. The goal is to assign state encodings to the automaton dk15, a benchmark from the LGSynth’91 logical benchmark set [48]. The weights calculated based on the number of transitions are listed in Table 1. These weights are used to construct the ARC-based cost calculator illustrated in Figure 8 (with ).
| 1,2 | 1,3 | 1,4 | 2,3 | 2,4 | 3,4 | |
| 3 | 7 | 3 | 6 | 3 | 3 |
Table 1. The transition-based weights for each pair of states and in the automaton dk15.
Figure 8. The cost calculator in the oracle for encoding the states of dk15.
Grover’s algorithm is executed once with an oracle constructed from the methodology introduced in this paper. The simulated result of measurement (with 2048 shots) is shown in Figure 9 (which was done using Qiskit [49]). The inputs that correspond to a high number of counts are solutions with minimal cost

Figure 9. The cost calculator in the oracle for encoding the states of dk15.
Algorithm 1 State Encoding Using an Oracle with ARC in Grover’s Algorithm
Input: finite automaton $M$, weights $W$ ($w_{i,j}$ for $i,j \in \{1,2,\ldots,n\}$ where $i<j$), and $r \in \mathbb{N}$
Output: state encodings $E_1,E_2,\ldots,E_n$
function $U_f(M,W,K)$ ▷ Constructs the circuit for the oracle $U_f$ with $K$
Initialize $U_f$
Add encoding checker $U_E$ to $U_f$
Add cost calculator $U_C$ to $U_f$
Add SAT Toffoli gate to $U_f$
Add mirrors $U_C^{-1}$ and $U_E^{-1}$ to $U_f$
return $U_f$
function ENCODE($M,W,K,r$)
solutions $\leftarrow$ generate $r$ from Grover’s algorithm with $U_f(M,W,K)$
for all solution $\in$ solutions do
Check solution
if solution is not a valid encoding then
Remove solution from solutions
return solutions
Initialize $K$
solutions $\leftarrow$ \operatorname{ENCODE}(M,W,K,r)$
(with the cost function from Eq. (3)). The inputs that correspond to a moderately low number of counts are solutions that have a greater cost than the minimum. The inputs that correspond to an extremely low or zero count are not valid solutions. Figure 10 illustrates the trend of the count decreasing as the cost increases for the solutions. A fully Boolean-based based oracle would not only have a greater cost, but it would also have taken multiple executions of Grover’s algorithm instead.

Figure 10. The corresponding number counts (shots) and cost of solutions (valid state encodings) of dk15.
Experimental Methodology
This section details how oracles with ARC for state assignment are evaluated in comparison to their corresponding Boolean-based oracles when applied to finite state machine benchmarks.
Benchmarks
The 26 finite state machine benchmarks used are lion, train4, dk15, mc, tav, s8, bbtas, s27, dk27, beecount, dk14, shiftreg, dk17, ex6, ex5, lion9, ex3, ex7, bbara, train11, modulo12, ex4, dk512, ex2, donfile, and dk16, all of which are from the LGSynth’91 library [48] in the .kiss2 file format. Information on the number of states, number of inputs, and minimum encoding length of each of these benchmarks is listed in Table 2. For both the oracles with ARC and Boolean-based oracles, the weights are based on the total number of transitions between each pair of states.
| lion | train4 | dk15 | mc | tav | s8 | bbtas | s27 | dk27 | beecount | dk14 | shiftreg | dk17 | |
| No. of States | 4 | 4 | 4 | 4 | 4 | 5 | 6 | 6 | 7 | 7 | 7 | 8 | 8 |
| No. of Inputs | 2 | 2 | 3 | 3 | 4 | 4 | 2 | 4 | 1 | 3 | 3 | 1 | 2 |
| Min. Enc. Len. | 2 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| ex6 | ex5 | lion9 | ex3 | ex7 | bbara | train11 | modulo12 | ex4 | dk512 | ex2 | donfile | dk16 | |
| No. of States | 8 | 9 | 9 | 10 | 10 | 10 | 11 | 12 | 14 | 15 | 19 | 24 | 27 |
| No. of Inputs | 5 | 2 | 2 | 2 | 2 | 4 | 2 | 1 | 6 | 1 | 2 | 2 | 2 |
| Min. Enc. Len. | 3 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 5 | 5 | 5 |
Table 2. The 26 benchmarks from the LGSynth’91 library [48] used for evaluation.
Boolean-Based Oracle as Baseline
The structure of the Boolean-based oracle that is used for comparison is illustrated in Figure 11. Both the oracle with ARC and the Boolean-based oracle have identical Boolean-based encoding checkers (which are decomposed into the inequality comparators shown in Figure 12 and a multi-qubit Toffoli gate), but their cost calculators are different. As discussed earlier, the oracle with ARC uses the ARC-based cost calculator presented in § 4.1.
Figure 11. For comparison and evaluation, the quantum Boolean-based oracle for state assignment.
Figure 12. The decomposition of the inequality () comparator used in the encoding checker .
The Boolean-based oracle instead uses a cost calculator constructed from arithmetic operators, specifically controlled-incrementer gates, that store the cost (encoded in binary) onto a multi-qubit register. In addition, this oracle also uses a comparator (which compares the cost to the threshold ). The threshold is stored on another multi-qubit register and is an input to the circuit. In order to optimize the cost, the threshold is updated after each execution of Grover’s algorithm to the cost of the selected solution. The controlled-incrementer and less-than () comparator gates are realized from quantum reversible gates, as shown in Figure 13 and Figure 14, respectively.
Figure 13. The decomposition of the controlled-incrementer.
Figure 14. The decomposition of the less-than () comparator.
Transpilation
To ensure a fair and consistent comparison of the circuit costs of oracles implemented using ARC and Boolean-based approaches, all oracles were transpiled using exactly the same configuration and settings. Specifically, the Qiskit [49] transpiler was configured with the highest optimization level (level 3), using the Qiskit Aer simulator as the target backend and the same set of basis gates: , , , , and . All experiments were conducted using identical software versions: Qiskit 2.5.2 and Qiskit Aer 0.17.2.
Furthermore, the transpilation process was repeated 200 times for each oracle under these same settings, and the circuit with the lowest TQC among the 200 transpiled circuits was selected for comparison.
Metrics and Percentage Calculation
The transpiled oracles were evaluated using four metrics: qubit count, gate count, depth, and Transpilation Quantum Cost (TQC). For a specific metric, the percentage improvement of the oracle with ARC (with a value in that metric of ) in comparison to the Boolean-based oracle (with a value in that metric of ) is . The mean percentage improvements reported were calculated from the arithmetic mean of the percentage improvements across all 26 evaluated benchmarks.
Results
Table 3 lists the qubit count, gate count, depth, and Transpilation Quantum Cost (TQC) of the transpiled oracle with ARC and the transpiled Boolean-based oracle for each benchmark.
In this table, the percentage improvement in qubit count ranged from 3.9% to 45.2%, with a mean improvement of 20.8%. More specifically, the size of the encoding checker grows quadratically with the number of states, whereas the cost calculator has constant size in the ARC-based approach and grows logarithmically with respect to the maximum cost in the Boolean-based approach. Nevertheless, the use of ARC consistently reduces the qubit count across all benchmarks. This reduction stems from the fact that an ARC-based oracle requires only a single-qubit register to encode the cost, whereas a Boolean-based oracle requires two multi-qubit registers: one to encode the cost and another to encode the threshold. The sizes of both registers scale with the range of objective function values, resulting in a higher overall qubit requirement for the Boolean-based approach.
| Benchmark | Inputs | States | Boolean-Based Oracle Qubits | Boolean-Based Oracle Gates | Boolean-Based Oracle Depth | Boolean-Based Oracle TQC | Oracle with ARC Qubits | Oracle with ARC Gates | Oracle with ARC Depth | Oracle with ARC TQC | % Improvement Qubits | % Improvement Gates | % Improvement Depth | % Improvement TQC |
| lion | 2 | 4 | 25 | 6302 | 4453 | 10755 | 17 | 1157 | 632 | 1789 | 32.0% | 81.6% | 85.8% | 83.4% |
| train4 | 2 | 4 | 25 | 7087 | 5032 | 12119 | 17 | 1229 | 662 | 1891 | 32.0% | 82.7% | 86.8% | 84.4% |
| dk15 | 3 | 4 | 29 | 51516 | 39633 | 91149 | 17 | 1377 | 735 | 2112 | 41.4% | 97.3% | 98.1% | 97.7% |
| mc | 3 | 4 | 27 | 22806 | 17193 | 39999 | 17 | 1230 | 664 | 1894 | 37.0% | 94.6% | 96.1% | 95.3% |
| tav | 4 | 4 | 31 | 179050 | 137010 | 316060 | 17 | 1232 | 664 | 1896 | 45.2% | 99.3% | 99.5% | 99.4% |
| s8 | 4 | 5 | 40 | 36518 | 27233 | 63751 | 28 | 3228 | 1673 | 4901 | 30.0% | 91.2% | 93.9% | 92.3% |
| bbtas | 2 | 6 | 48 | 46521 | 34627 | 81148 | 36 | 4370 | 2189 | 6559 | 25.0% | 90.6% | 93.7% | 91.9% |
| s27 | 4 | 6 | 52 | 371650 | 277009 | 648659 | 36 | 5033 | 2498 | 7531 | 30.8% | 98.6% | 99.1% | 98.8% |
| dk27 | 1 | 7 | 57 | 48172 | 35076 | 83248 | 45 | 6403 | 3028 | 9431 | 21.1% | 86.7% | 91.4% | 88.7% |
| beecount | 3 | 7 | 59 | 172551 | 129877 | 302428 | 45 | 6292 | 2974 | 9266 | 23.7% | 96.4% | 97.7% | 96.9% |
| dk14 | 3 | 7 | 61 | 279337 | 206650 | 485987 | 45 | 7173 | 3392 | 10565 | 26.2% | 97.4% | 98.4% | 97.8% |
| shiftreg | 1 | 8 | 67 | 49989 | 35862 | 85851 | 55 | 8391 | 3818 | 12209 | 17.9% | 83.2% | 89.4% | 85.8% |
| dk17 | 2 | 8 | 69 | 129245 | 95481 | 224726 | 55 | 9028 | 4124 | 13152 | 20.3% | 93.0% | 95.7% | 94.1% |
| ex6 | 5 | 8 | 75 | 1868513 | 1356341 | 3224854 | 55 | 8931 | 4074 | 13005 | 26.7% | 99.5% | 99.7% | 99.6% |
| ex5 | 2 | 9 | 89 | 186014 | 138291 | 324305 | 75 | 15748 | 9262 | 25010 | 15.7% | 91.5% | 93.3% | 92.3% |
| lion9 | 2 | 9 | 87 | 76972 | 56928 | 133900 | 75 | 13676 | 8280 | 21956 | 13.8% | 82.2% | 85.5% | 83.6% |
| ex3 | 2 | 10 | 104 | 284841 | 208799 | 493640 | 88 | 21030 | 10232 | 31262 | 15.4% | 92.6% | 95.1% | 93.7% |
| ex7 | 2 | 10 | 104 | 269771 | 198190 | 467961 | 88 | 20123 | 9840 | 29963 | 15.4% | 92.5% | 95.0% | 93.6% |
| bbara | 4 | 10 | 104 | 284615 | 209137 | 493752 | 88 | 20406 | 10053 | 30459 | 15.4% | 92.8% | 95.2% | 93.8% |
| train11 | 2 | 11 | 114 | 75950 | 55175 | 131125 | 102 | 22970 | 11601 | 34571 | 10.5% | 69.8% | 79.0% | 73.6% |
| modulo12 | 1 | 12 | 129 | 74141 | 49399 | 123540 | 117 | 26852 | 13443 | 40295 | 9.3% | 63.8% | 72.8% | 67.4% |
| ex4 | 6 | 14 | 172 | 6097113 | 4392823 | 10489936 | 150 | 36927 | 18268 | 55195 | 12.8% | 99.4% | 99.6% | 99.5% |
| dk512 | 1 | 15 | 182 | 208106 | 145816 | 353922 | 168 | 43813 | 21310 | 65123 | 7.7% | 78.9% | 85.4% | 81.6% |
| ex2 | 2 | 19 | 287 | 941555 | 668445 | 1610000 | 269 | 88550 | 43687 | 132237 | 6.3% | 90.6% | 93.5% | 91.8% |
| donfile | 2 | 24 | 417 | 990210 | 692089 | 1682299 | 399 | 138169 | 68714 | 206883 | 4.3% | 86.0% | 90.1% | 87.7% |
| dk16 | 2 | 27 | 509 | 1733691 | 1212996 | 2946687 | 489 | 179056 | 88206 | 267262 | 3.9% | 89.7% | 92.7% | 90.9% |
Table 3. Comparison of the transpiled oracle with ARC and the transpiled Boolean-based oracle for each benchmark.
The percentage improvements range from 63.8% to 99.5% in gate count, 72.8% to 99.7% in circuit depth, and 67.4% to 99.6% in TQC, with corresponding mean improvements of 89.3%, 92.4%, and 90.6%, respectively. These substantial reductions can primarily be attributed to the use of controlled- gates in ARC-based oracles, as opposed to controlled-incrementer gates in their Boolean-based counterparts. When decomposed, controlled-incrementer gates require more elementary gates and result in greater circuit depth. Furthermore, ARC-based oracles eliminate the need for a comparator, which is a relatively costly component in Boolean-based oracles. By avoiding both the overhead associated with controlled-incrementer gates and the comparator, ARC significantly reduces oracle circuit costs. Overall, across all 26 evaluated benchmarks, ARC-based oracles consistently achieve lower circuit costs and require fewer qubits than their corresponding Boolean-based oracles after transpilation.
Discussion
This section discusses the theoretical and experimental findings of this research. The Angular Rotational Counter (ARC) circuit computes the objective function value of a given candidate solution through rotationally encoding it with the angle radians onto a single-qubit register. This is an alternative, cost-effective approach to explicitly encoding as a binary value onto a multi-qubit register, which was used previously in Boolean-based oracles for optimization problems.
Circuit Cost in Comparison to Boolean-Based Methods
Oracles with ARC have a lower circuit cost than corresponding Boolean-based oracles for three main reasons: oracles with ARC use controlled quantum rotational gates instead of controlled-incrementer gates, do not use a comparator, and have a single-qubit register instead of multi-qubit registers. Firstly, the controlled-incrementer gates and other arithmetic operators used in a Boolean-based circuit for computing cost must be decomposed into many individual gates, such as (NOT), (CNOT), and Toffoli gates. Such arithmetic operators increase in cost depending on the size of the multi-qubit register and are more expensive than controlled quantum rotational gates. Secondly, the Boolean-based oracle always requires a comparator, which has similar disadvantages to arithmetic operators, in order for the oracle to be able to distinguish the cost of solutions. In contrast, oracles with ARC do not use these expensive comparators because the output of ARC is already dependent on the objective function values. Thirdly, ARC uses a single-qubit register, while Boolean-based cost calculators use a multi-qubit register that increases in qubit count based on the objective function values.
Objective Functions and Measurement Probabilities
The ARC circuit is naturally suited for objective functions that can be decomposed into a weighted sum of Boolean functions, where the outputs of the Boolean functions are treated as real numbers, although they must be 0 or 1, because of the inherently logical property of controlled gates (which represent the Boolean functions) and the continuity of rotational angles (which represent the weights). Here, the applicability of ARC for weighted Hamming distance cost functions has been demonstrated by decomposing the Hamming distance function into a sum of Boolean functions. Many other functions can be decomposed in similar ways. For functions that cannot be decomposed into such a form, the ARC circuit should be modified.
The measurement probabilities of the output qubit of ARC are dependent on the objective function. However, the ARC circuit itself does not automatically yield valid or optimal solutions. A marking circuit that identifies valid solutions and filters out the rest must be added to the oracle. An oracle cannot work without such a circuit. In the context of optimization, the ARC circuit should be used within a quantum algorithm. Furthermore, for an ARC circuit to function as intended, the constant (in as the rotational angle) should be set to a value greater than or equal to the maximum objective function value because of the periodic nature of the sinusoidal functions that appear in rotational gates. However, it is important to note that in physical hardware, there is a limit to how small an angle can be [50, 51], corresponding to a limit on how large can be. It is also important to note that for higher values of , and thus smaller and more precise angles, the impact of noise will become a larger problem for performance.
Complexity Analysis
The exact time complexity of an ARC circuit depends on the objective function. A general formula for the complexity, however, can be derived, as achieved in Theorem 5.
Theorem 5. The time complexity of an ARC circuit is determined by Eq. (9), where the ARC circuit contains qubits, the objective function is of the form in Eq. (4), and is the time complexity of the quantum circuit realization of .
Proof. The ARC circuit contains a circuit realization of , a controlled-, and a circuit realization of for all .
The time complexity of the circuit realization of is given as . The time complexity of its inverse, , is also , because the circuit for can be reversed to obtain the circuit for . The total time complexity of all and circuits is therefore . The controlled- gate has a constant time complexity. Let this constant be .
The time complexity of the whole ARC circuit would then be
This simplifies to .
Comparison of State Assignment with ARC to Classical Algorithm
In the classical-quantum algorithm for state assignment introduced in this paper, Grover’s algorithm is executed once with input qubits. Therefore, the query complexity of this classical-quantum algorithm is . In contrast, an equivalent classical algorithm makes at most queries, which is the total number of possible assignments of state encodings. Accordingly, the query complexity of this algorithm is , which grows faster than . Hence, this classical-quantum algorithm introduced in this work has a lower query complexity than an equivalent classical algorithm.
Comparison of State Assignment with ARC to Previous Work
Previous work on creating a quantum oracle for state assignment was discussed in [12]. Notable differences include the applicability, cost function, circuit cost, and corresponding algorithm. The cost calculator of the oracle in the previous method [12] is constructed with a Boolean-based counter and a comparator (for a threshold). According to [12], the time complexity of the cost calculator circuit and comparator is
where is the number of states and is the number of inputs. However, it is important to note that the scaling in time complexity of the many multi-qubit Toffoli gates used in the circuit is not considered in the calculation from [12] and that the previous method encodes both states and inputs with a more accurate cost function.
In contrast, the cost calculator of the oracle in our method is constructed with an ARC circuit. The cost calculator circuit is composed of at most weighted HD calculator circuits, each of which contains CNOT gates and controlled-RX gates. Therefore, by applying Theorem 5 and letting the time complexity of a CNOT and controlled-RX gate be the constants and , respectively, the cost calculator circuit has a time complexity of
While the cost calculator circuit in the previous method has a time complexity that is more than exponential, the cost calculator circuit in our method has a time complexity that is quadratic-logarithmic, which is significantly lower than the previous method.
Future Directions
There are several promising directions in which this research can be extended. Firstly, future work could investigate the application of the ARC circuit to a broader class of objective functions and optimization problems beyond the finite state machine benchmarks considered in this study. In particular, exploring different objective function representations may reveal additional opportunities for constructing cost-effective, resource-efficient quantum oracles. One interesting direction is to investigate rotational encodings of objective function values as an alternative to explicit binary representations in more general contexts.
Secondly, the ARC circuit could be further developed and integrated into other quantum algorithms. Investigating its applicability to different quantum optimization frameworks and oracle-based algorithms may help establish the broader utility of the proposed approach.
Thirdly, further research could focus on improving the query and time complexities of optimization algorithms that employ ARC-based oracles. Specifically, theoretical analyses and experimental evaluations could help determine whether the observed reductions in quantum circuit resources can translate into improvements in overall algorithmic efficiency.
Finally, the scalability of ARC-based implementations warrants further investigation, particularly for automata with larger state spaces. Evaluating larger problem instances using more powerful computational platforms would provide additional insight into their resource requirements and practical limitations. Such investigations could help establish the applicability of ARC to increasingly complex optimization problems.
Conclusions
This paper introduces the Angular Rotational Counter (ARC), a quantum circuit design that encodes decomposable objective functions through the accumulation of quantum rotational operations on a single-qubit register. We establish the correctness of the proposed circuit, formally characterize the quantum state of its output qubit for candidate solutions, and demonstrate its application to constructing oracles for quantum search algorithms in optimization problems. Notably, we prove that the measurement probabilities of the ARC output qubit vary monotonically with the objective function values. This property enables the construction of oracles that favor candidate solutions according to either the maximization or minimization of the objective, depending on the initialization of the input qubits in the ARC circuit.
To investigate the practical applicability of ARC, we employ it to construct oracles for the state assignment problem in finite automata and state machines, using a heuristic weighted Hamming distance as the objective function. We evaluate the resulting oracles with ARC against their conventional Boolean-based counterparts across 26 finite state machine benchmarks using four quantum circuit cost metrics. The experimental results demonstrate substantial reductions in circuit resource requirements and resulting costs. Specifically, the implementations with ARC achieve arithmetic mean reductions of 20.8% in qubit count, 89.3% in gate count, 92.4% in circuit depth, and 90.6% in transpiled circuit cost. These results highlight the potential of rotational encoding to substantially reduce the quantum circuit resources required for oracle construction compared with conventional Boolean-based representations.
Although these results demonstrate significant improvements in quantum circuit cost and resource efficiency, they do not, by themselves, establish corresponding reductions in physical execution time or an asymptotic quantum speedup. Nevertheless, the consistent cost reductions observed across the evaluated benchmarks provide encouraging evidence for the practical utility of ARC-based oracle construction. More broadly, this work motivates further investigation into rotational encodings of function values as an alternative to explicit binary representations in quantum circuits. The proposed ARC framework also provides a foundation for exploring oracle constructions for a broader range of objective functions and optimization problems. As quantum computing continues to evolve, our results suggest that rotational encoding, exemplified by resource-efficient oracle architectures such as ARC, may offer a promising alternative design framework for quantum oracles, paving the way toward more practical and scalable quantum optimization algorithms.
Acknowledgments
Computational resources used in this work were supported by the Oregon Regional Computing Accelerator (Orca), funded by NSF CC*-2346732.
References
- [1]L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 212–219, 1996.arxiv.org/abs/quant-ph/9605043
- [2]L. K. Grover, “Quantum mechanics helps in searching for a needle in a haystack,” Physical Review Letters, vol. 79, no. 2, p. 325, 1997.DOI
- [3]L. K. Grover, “Quantum computers can search rapidly by using almost any transformation,” Physical Review Letters, vol. 80, no. 19, p. 4329, 1998.DOI
- [4]M. Boyer, G. Brassard, P. Høyer, and A. Tapp, “Tight bounds on quantum searching,” Fortschritte der Physik: Progress of Physics, vol. 46, no. 4-5, pp. 493–505, 1998.
- [5]C. Figgatt, D. Maslov, K. A. Landsman, N. M. Linke, S. Debnath, and C. Monroe, “Complete 3-qubit Grover search on a programmable quantum computer,” Nature Communications, vol. 8, no. 1, p. 1918, 2017.DOI
- [6]A. Al-Bayaty and M. Perkowski, “A concept of controlling Grover diffusion operator: A new approach to solve arbitrary Boolean-based problems,” Scientific Reports, vol. 14, no. 1, p. 23570, 2024.DOI
- [7]N. Shenvi, J. Kempe, and K. B. Whaley, “Quantum random-walk search algorithm,” Physical Review A, vol. 67, no. 5, p. 052307, 2003.DOI
- [8]A. M. Childs and J. Goldstone, “Spatial search by quantum walk,” Physical Review A—Atomic, Molecular, and Optical Physics, vol. 70, no. 2, p. 022314, 2004.DOI
- [9]A. Al-Bayaty and M. Perkowski, “BHT-QAOA: The generalization of quantum approximate optimization algorithm to solve arbitrary Boolean problems as Hamiltonians,” Entropy, vol. 26, no. 10, p. 843, 2024.DOI
- [10]A. Al-Bayaty and M. Perkowski, “The impact of optimization approximation algorithms on the performance of the BHT-QAOA,” Academia Quantum, vol. 2, no. 4, 2025.DOI
- [11]E. Campbell, A. Khurana, and A. Montanaro, “Applying quantum algorithms to constraint satisfaction problems,” Quantum, vol. 3, p. 167, July 2019.DOI
- [12]E. Tsai and M. Perkowski, “A quantum algorithm for automata encoding,” Facta Universitatis, Series: Electronics and Energetics, vol. 33, no. 2, pp. 169–215, 2020.DOI
- [13]W. Hou and M. A. Perkowski, “Quantum-based algorithm and circuit design for bounded knapsack optimization problem.,” Quantum Inf. Comput., vol. 20, no. 9&10, pp. 766–786, 2020.
- [14]M. Perkowski, “Inverse problems, constraint satisfaction, reversible logic, invertible logic and Grover quantum oracles for practical problems,” Science of Computer Programming, vol. 218, p. 102775, 2022.
- [15]C. Durr and P. Hoyer, “A quantum algorithm for finding the minimum,” arXiv preprint quant-ph/9607014, 1996.arxiv.org/abs/quant-ph/9607014
- [16]A. Gilliam, S. Woerner, and C. Gonculea, “Grover adaptive search for constrained polynomial binary optimization,” Quantum, vol. 5, p. 428, 2021.DOI
- [17]H. Ketineni and M. Perkowski, “Quantum algorithm for exact minimal ESOP minimization of incompletely specified Boolean functions and reversible synthesis,” Quantum Information and Computation, vol. 23, no. 3–4, pp. 195–222, 2023.
- [18]S. Devadas, H.-K. Ma, A. R. Newton, and A. Sangiovanni-Vincentelli, “MUSTANG: State assignment of finite state machines targeting multilevel logic implementations,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 7, no. 12, pp. 1290–1300, 1988.DOI
- [19]L. Benini and G. De Micheli, “State assignment for low power dissipation,” IEEE Journal of Solid-State Circuits, vol. 30, no. 3, pp. 258–268, 1995.
- [20]C.-Y. Tsui, M. Pedram, and A. M. Despain, “Low-power state assignment targeting two-and multilevel logic implementations,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 17, no. 12, pp. 1281–1291, 1998.DOI
- [21]R. K. Ahuja, J. B. Orlin, and A. Tiwari, “A greedy genetic algorithm for the quadratic assignment problem,” Computers & Operations Research, vol. 27, no. 10, pp. 917–934, 2000.
- [22]E. M. Loiola, N. M. M. De Abreu, P. O. Boaventura-Netto, P. Hahn, and T. Querido, “A survey for the quadratic assignment problem,” European Journal of Operational Research, vol. 176, no. 2, pp. 657–690, 2007.
- [23]D. L. Mermoud, A. Simonetto, and S. Elloumi, “Variational quantum algorithms for permutation-based combinatorial problems: Optimal ansatz generation with applications to quadratic assignment problems and beyond,” Quantum, vol. 10, p. 1998, 2026.arxiv.org/abs/2505.05981
- [24]G. De Micheli, R. K. Brayton, and A. Sangiovanni-Vincentelli, “Optimal state assignment for finite state machines,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 4, no. 3, pp. 269–285, 1985.
- [25]T. Villa and A. Sangiovanni-Vincentelli, “NOVA: State assignment of finite state machines for optimal two-level logic implementations,” in Proceedings of the 26th ACM/IEEE Design Automation Conference, pp. 327–332, 1989.DOI
- [26]Y. Huang and M. Perkowski, “One hot encoding synthesis of quantum automata from flowcharts,” Journal of Quantum Information Science, vol. 13, no. 3, pp. 156–176, 2023.DOI
- [27]Y. Huang, Multiple-Valued Quantum Automata for Robotics. PhD thesis, Portland State University, 2026.DOI
- [28]M. Kumar and M. Perkowski, “Realization of deterministic quantum circuits for non-deterministic or incompletely specified quantum state machines,” Quantum Information & Computation, vol. 25, no. 6, pp. 716–738, 2025.DOI
- [29]C. Moore and J. P. Crutchfield, “Quantum automata and quantum grammars,” Theoretical Computer Science, vol. 237, no. 1-2, pp. 275–306, 2000.arxiv.org/abs/quant-ph/9707031
- [30]A. Kondacs and J. Watrous, “On the power of quantum finite state automata,” in Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pp. 66–75, IEEE, 1997.
- [31]A. Al-Bayaty and M. Perkowski, “GALA-n: Generic architecture of layout-aware n-bit quantum operators for cost-effective realization on IBM quantum computers,” arXiv preprint arXiv:2311.06760, 2023.
- [32]A. Al-Bayaty, X. Song, and M. Perkowski, “CALA-n: A quantum library for realizing cost-effective 2-, 3-, 4-, and 5-bit gates on IBM quantum computers using Bloch sphere approach, Clifford+T gates, and layouts,” arXiv preprint arXiv:2408.01025, 2024.
- [33]A. Al-Bayaty, S. Chen, A. Al-Shuwaili, A. AlZubaidi, and M. Perkowski, “A geometrical design tool for building cost-effective layout-aware n-bit quantum gates using the Bloch sphere approach,” Cureus Journal Of Computer Science, vol. 3, 2026.
- [34]S. Yang, A. Al-Bayaty, and M. Perkowski, “Minimization of AND-XOR expressions with decoders for quantum circuits,” Physical Review A, vol. 113, no. 5, p. 052443, 2026.
- [35]A. Ambainis, “Understanding quantum algorithms via query complexity,” in Proceedings of the International Congress of Mathematicians, pp. 3265–3285, World Scientific, 2018.arxiv.org/abs/1712.06349
- [36]T. Toffoli, “Reversible computing,” in International colloquium on automata, languages, and programming, pp. 632–644, Springer, 1980.DOI
- [37]A. Peres, “Reversible logic and quantum computers,” Physical Review A, vol. 32, no. 6, p. 3266, 1985.pubmed.ncbi.nlm.nih.gov/9896493
- [38]P. W. Shor, “Scheme for reducing decoherence in quantum computer memory,” Physical Review A, vol. 52, no. 4, p. R2493, 1995.pubmed.ncbi.nlm.nih.gov/9912632
- [39]H. G. Krojanski and D. Suter, “Reduced decoherence in large quantum registers,” Physical Review Letters, vol. 97, no. 15, p. 150503, 2006.
- [40]A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurther, “Elementary gates for quantum computation,” Physical Review A, vol. 52, no. 5, p. 3457, 1995.DOI
- [41]G. Li, Y. Ding, and Y. Xie, “Tackling the qubit mapping problem for NISQ-era quantum devices,” in Proceedings of the 24th International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 1001–1014, 2019.arxiv.org/abs/1809.02573
- [42]W. V. Quine, “The problem of simplifying truth functions,” The American Mathematical Monthly, vol. 59, no. 8, pp. 521–531, 1952.
- [43]E. J. McCluskey, “Minimization of Boolean functions,” The Bell System Technical Journal, vol. 35, no. 6, pp. 1417–1444, 1956.DOI
- [44]R. K. Brayton, G. D. Hachtel, L. A. Hemachandra, A. R. Newton, and A. L. M. Sangiovanni-Vincentelli, “A comparison of logic minimization strategies using ESPRESSO: An APL program package for partitioned logic minimization,” in Proceedings of the International Symposium on Circuits and Systems, pp. 42–48, 1982.
- [45]N. Song and M. A. Perkowski, “EXORCISM-MV-2: Minimization of exclusive sum of products expressions for multiple-valued input incompletely specified functions,” in Proceedings of the 23rd International Symposium on Multiple-Valued Logic, pp. 132–137, IEEE, 1993.
- [46]N. Song and M. Perkowski, “New fast approach to approximate ESOP minimization for incompletely specified multi-output functions,” in Proc. IFIP 10.5 Workshop on Application of Reed-Muller Expansions in Circuit Design, pp. 61–72, 1997.
- [47]A. Mishchenko and M. Perkowski, “Fast heuristic minimization of exclusive-sums-of-products,” in Proc. RM’2001 Workshop, 2001.
- [48]S. Yang, “Logic synthesis and optimization benchmarks user guide: Version 3.0,” tech. rep., MCNC Technical Report, Jan. 1991.
- [49]A. Javadi-Abhari, M. Treinish, K. Krulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross, et al., “Quantum computing with Qiskit,” arXiv preprint arXiv:2405.08810, 2024.
- [50]D. Greenbaum and Z. Dutton, “Modeling coherent errors in quantum error correction,” Quantum Science and Technology, vol. 3, no. 1, p. 015007, 2018.DOI
- [51]S. Lazăr, Q. Ficheux, J. Herrmann, A. Remm, N. Lacroix, C. Hellings, F. Swiadek, D. C. Zanuz, G. J. Norris, M. B. Panah, et al., “Calibration of drive nonlinearity for arbitrary-angle single-qubit gates using error amplification,” Physical Review Applied, vol. 20, no. 2, p. 024036, 2023.DOI











