Targeting entailment model checking, a recent study has pioneered an idea of Eigenmarking search, an improvement over Grover search using extra qubits. The extra qubits condition the quantum state evolution such that the answer states (if exist) are always in the minority. The minority criteria is essential to Grover probability-amplitude amplification and consequently the effectiveness of Grover search. In addition to enforce the minority criteria, Eigenmarking also employs complementary states (through well-orchestrated phase rotation) for easy identification of a no-answer case (related to a no-violation case in the context of model checking). Eigenmarking search has been shown effective in two-qubit simulations.
The three Eigenmarking schemes have been previously proposed. Two schemes require two extra qubits. One scheme (called ``subtle marking'') requires one extra qubit with a multiple-qubit-controlled phase rotation. Our study refines the mechanism using only one extra qubit with only two-qubit-controlled phase rotation, commonly known as \texttt{ccz}, regardless of how many qubits the input has. Using a multiple-qubit-controlled phase rotation (as in subtle marking) associates with highly entangled states. Highly entangled states in a real quantum hardware are difficult (or in some cases may even be unachievable) particularly in a scaled up scenario involving many qubits. Our proposed new Eigenmarking scheme has lightened the burden for the hardware requirement. The new Eigenmarking search has been experimented in two-qubit-system simulations and shown viable, achieving the minimal relative local winning margin of W=3.17 and the worst-case distinguishability of D=0.769 (cf. W=0.67; D=0.19 from conventional marking and W=0.28; D=0.55 from subtle marking).
Comments
This study has been presented at Innovation and Analytics Conference & Exhibition (IACE 2025), Uzbekistan during 20-22 October 2025
Targeting entailment model checking, a recent study has pioneered an idea of Eigenmarking search, an improvement over Grover search using extra qubits. The extra qubits condition the quantum state evolution such that the answer states (if exist) are always in the minority. The minority criteria is essential to Grover probability-amplitude amplification and consequently the effectiveness of Grover search. In addition to enforce the minority criteria, Eigenmarking also employs complementary states (through well-orchestrated phase rotation) for easy identification of a no-answer case (related to a no-violation case in the context of model checking). Eigenmarking search has been shown effective in two-qubit simulations.
The three Eigenmarking schemes have been previously proposed. Two schemes require two extra qubits. One scheme (called ``subtle marking'') requires one extra qubit with a multiple-qubit-controlled phase rotation. Our study refines the mechanism using only one extra qubit with only two-qubit-controlled phase rotation, commonly known as \texttt{ccz}, regardless of how many qubits the input has. Using a multiple-qubit-controlled phase rotation (as in subtle marking) associates with highly entangled states. Highly entangled states in a real quantum hardware are difficult (or in some cases may even be unachievable) particularly in a scaled up scenario involving many qubits. Our proposed new Eigenmarking scheme has lightened the burden for the hardware requirement. The new Eigenmarking search has been experimented in two-qubit-system simulations and shown viable, achieving the minimal relative local winning margin of W=3.17 and the worst-case distinguishability of D=0.769 (cf. W=0.67; D=0.19 from conventional marking and W=0.28; D=0.55 from subtle marking).
Logic entailment is essential to reasoning, but entailment checking has the worst-case complexity of an exponential of the variable size. With recent development, quantum computing when mature may allow an effective approach for various combinatorial problems, including entailment checking. Grover algorithm uses Grover operations, i.e., selective phase inversion and amplitude amplification to address a search over unstructured data with quadratic improvement from a classical method. Its original form is intended to a single-winner scenario: exactly one match is promised. Its extension to multiple-winner cases employs probabilistic control over a number of applications of Grover operations, while a no-winner case is determined by time-out. Our study explores various schemes of “eigenmarking” approach. Still relying on Grover operations, but the approach introduces additional qubits to tag the eigenstates. The tagged eigenstates are to facilitate an interpretation of the measured results and enhance identification of a no-winner case (related to no logic violation in entailment context). Our investigation experiments three variations of eigenmarking on a two-qubit system using an IBM Aer simulator. The results show strong distinguishability in all schemes with the best relative distinguishabilities of 19 and 53 in worst case and in average case, respectively. Our findings reveal a viable quantum mechanism to differentiate a no-winner case from other scenarios, which could play a pivot role in entailment checking and logic reasoning in general.
We study the possibility of an implementation of N-qubit (N>3) Grover search in cavity QED, based on a fast operation of N-qubit controlled phase-flip with atoms in resonance with the cavity mode. We demonstrate both analytically and numerically that, our scheme could be achieved efficiently to find a marked state with high fidelity and high success probability. As cavity decay is involved in our quantum trajectory treatment, we could analytically understand the implementation of a Grover search subject to dissipation, which would be very helpful for relevant experiments.
We briefly introduced some of our recent work related to the phase matching condition in quantum searching algorithms and the improved Grover algorithm. When one replaces the two phase inversions in the Grover algorithm with arbitrary phase rotations, the modified algorithm usually fails in searching the marked state unless a phase matching condition is satisfied between the two phases. The Grover algorithm is not 100% in success rate, an improved Grover algorithm with zero-failure rate is given by replacing the phase inversions with angles that depends on the size of the database. Other aspects of the Grover algorithm such as the SO(3) picture of quantum searching, the dominant gate imperfections in the Grover algorithm are also mentioned.
We explore the possibility of an N -qubit ( N > 3) Grover search in cavity QED, based on a fast operation of an N -qubit controlled phase-flip with atoms in resonance with the cavity mode. We demonstrate both analytically and numerically that our scheme can be achieved efficiently to find a marked state with high fidelity and high success probability. As an example, a ten-qubit Grover search is simulated specifically under the discussion of experimental feasibility and challenge. We argue that our scheme is applicable to the case involving an arbitrary number of qubits. As cavity decay is involved in our quantum trajectory treatment, we can analytically understand the implementation of a Grover search subject to dissipation, which will be very helpful for relevant experiments.
IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.
For an unknown eigenstate ∣ψ⟩ of a unitary operator U, suppose we have an estimate of the corresponding eigenvalue which is separated from all other eigenvalues by a minimum gap of magnitude Δ. In the eigenstate-marking problem (EMP), the goal is to implement a selective phase transformation of the ∣ψ⟩ state (known as \emph{marking} the ∣ψ⟩ state in the language of the quantum search algorithms). The EMP finds important applications in the construction of several quantum algorithms. The best known algorithm for the EMP combines the ideas of the phase estimation algorithm and the majority-voting. It uses Θ(Δ1lnε1) applications of U where ε is the tolerable error. It needs Θ(lnΔ1) ancilla qubits for the phase estimation and another Θ(lnε1) ancilla qubits for the majority-voting. In this paper, we show that the majority-voting is not a crucial requirement for the EMP and the same purpose can also be achieved using the fixed-point quantum search algorithm which does not need any ancilla qubits. In the case of majority-voting, these ancilla qubits were needed to do controlled transformations which are harder to implement physically. Using fixed-point quantum search, we get rid off these Θ(lnε1) ancilla qubits and same number of controlled transformations. Thus we get a much simpler algorithm for marking the unknown eigenstates. However, the required number of applications of U increases by the factor of Θ(lnε1). This tradeoff can be beneficial in typical situations where spatial resources are more constrained or where the controlled transformations are very expensive.