Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Grover's algorithm”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 37 records · Page 2

Exact and Fixed-Point Grover Search with Qudits

Grover's algorithm provides a quadratic speedup for searching unstructured databases and is traditionally implemented with qubits in Hilbert spaces whose dimensions are powers of two. With the advent of quantum platforms utilizing qudits---quantum systems with more than two levels---there is a need to generalize Grover search to these architectures, including heterogeneous systems with qudits of varying dimensions. Here, we present a unified framework for qudit-based Grover search, detailing the construction of oracles and diffusion operators with and without ancilla qubits and generalizing deterministic and fixed-point search variants that ensure exact or bounded success probabilities. We analyze phase-matching techniques and provide explicit circuit decompositions suitable for diverse hardware platforms. We also compare the corresponding trajectories on the Bloch sphere to provide an intuitive visualization of how the different phase choices amplify the target state. These results facilitate flexible, hardware-oriented protocols for implementing Grover search on qudit processors, potentially reducing circuit depth and enhancing success probabilities, thereby offering a practical toolkit for quantum computation and sensing applications leveraging multilevel quantum systems.

Roy, Tanay [Fermilab] (ORCID:000000019442862X)↗

Large gradients via correlation in random parameterized quantum circuits

Scaling of variational quantum algorithms to large problem sizes requires efficient optimization of random parameterized quantum circuits. For such circuits with uncorrelated parameters, the presence of exponentially vanishing gradients in cost function landscapes is an obstacle to optimization by gradient descent methods. In this work, we prove that reducing the dimensionality of the parameter space by utilizing circuit modules containing spatially or temporally correlated gate layers can allow one to circumvent the vanishing gradient phenomenon. Here, examples are drawn from random separable circuits and asymptotically optimal variational versions of Grover's algorithm based on the quantum alternating operator ansatz. In the latter scenario, our bounds on cost function variation imply a transition between vanishing gradients and efficient trainability as the number of layers is increased toward $\mathcal{O}\left({2}^{n/2}\right)$, the optimal oracle complexity of quantum unstructured search.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Implementation and analysis of quantum computing application to Higgs boson reconstruction at the large Hadron Collider

With the advent of the High-Luminosity Large Hadron Collider (HL-LHC) era, high energy physics (HEP) event selection will require new approaches to rapidly and accurately analyze vast databases. The current study addresses the enormity of HEP databases in an unprecedented manner—a quantum search using Grover’s Algorithm (GA) on an unsorted database, ATLAS Open Data, from the ATLAS detector. A novel method to identify rare events at 13 TeV in CERN’s LHC using quantum computing (QC) is presented. As indicated by the Higgs boson decay channel H→ZZ*→4l , the detection of four leptons in one event may be used to reconstruct the Higgs boson and, more importantly, evince Higgs boson decay to some new phenomena, such as H→ZZ d →4l . Searching the dataset for collisions resulting in detection of four leptons using a Jupyter Notebook, a classical simulation of GA, and several quantum computers with multiple qubits, the current application was found to make the proper selection in the unsorted dataset. Quantum search efficacy was analyzed for the incoming HL-LHC by implementing the QC method on multiple classical simulators and IBM’s quantum computers with the IBM Qiskit Open Source Software. The current QC application provides a novel, high-efficiency alternative to classical database searches, demonstrating its potential utility as a rapid and increasingly accurate search method in HEP.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

Grover Search and the No-Signaling Principle

Two of the prime properties of quantum physics are the no-signaling principle and the Grover search lower bound. That is, despite admitting stronger-than-classical correlations, quantum mechanics does not imply superluminal signaling, and despite a form of exponential parallelism, quantum mechanics does not imply polynomial-time brute force solution of NP-complete problems. Herein, we investigate the degree to which these two properties are connected. We explore four classes of deviations from quantum mechanics, for which we draw inspiration from the literature on the black hole information paradox. We show that in these models, the physical resources required to send a superluminal signal scale polynomially with the resources needed to speed up Grover’s algorithm. Hence the no-signaling principle is equivalent to the inability to solve NP-hard problems efficiently by brute force within the classes of theories analyzed.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

SU-D-BRB-05: Quantum Learning for Knowledge-Based Response-Adaptive Radiotherapy

Purpose: There is tremendous excitement in radiotherapy about applying data-driven methods to develop personalized clinical decisions for real-time response-based adaptation. However, classical statistical learning methods lack in terms of efficiency and ability to predict outcomes under conditions of uncertainty and incomplete information. Therefore, we are investigating physics-inspired machine learning approaches by utilizing quantum principles for developing a robust framework to dynamically adapt treatments to individual patient’s characteristics and optimize outcomes. Methods: We studied 88 liver SBRT patients with 35 on non-adaptive and 53 on adaptive protocols. Adaptation was based on liver function using a split-course of 3+2 fractions with a month break. The radiotherapy environment was modeled as a Markov decision process (MDP) of baseline and one month into treatment states. The patient environment was modeled by a 5-variable state represented by patient’s clinical and dosimetric covariates. For comparison of classical and quantum learning methods, decision-making to adapt at one month was considered. The MDP objective was defined by the complication-free tumor control (P{sup +}=TCPx(1-NTCP)). A simple regression model represented state-action mapping. Single bit in classical MDP and a qubit of 2-superimposed states in quantum MDP represented the decision actions. Classical decision selection was done using reinforcement Q-learning and quantum searching was performed using Grover’s algorithm, which applies uniform superposition over possible states and yields quadratic speed-up. Results: Classical/quantum MDPs suggested adaptation (probability amplitude ≥0.5) 79% of the time for splitcourses and 100% for continuous-courses. However, the classical MDP had an average adaptation probability of 0.5±0.22 while the quantum algorithm reached 0.76±0.28. In cases where adaptation failed, classical MDP yielded 0.31±0.26 average amplitude while the quantum approach averaged a more optimistic 0.57±0.4, but with high phase fluctuations. Conclusion: Our results demonstrate that quantum machine learning approaches provide a feasible and promising framework for real-time and sequential clinical decision-making in adaptive radiotherapy.

60 APPLIED LIFE SCIENCES↗

Search on a hypercubic lattice using a quantum random walk. I. d>2

Random walks describe diffusion processes, where movement at every time step is restricted to only the neighboring locations. We construct a quantum random walk algorithm, based on discretization of the Dirac evolution operator inspired by staggered lattice fermions. We use it to investigate the spatial search problem, that is, to find a marked vertex on a d-dimensional hypercubic lattice. The restriction on movement hardly matters for d>2, and scaling behavior close to Grover's optimal algorithm (which has no restriction on movement) can be achieved. Using numerical simulations, we optimize the proportionality constants of the scaling behavior, and demonstrate the approach to that for Grover's algorithm (equivalent to the mean-field theory or the d{yields}{infinity} limit). In particular, the scaling behavior for d=3 is only about 25% higher than the optimal d{yields}{infinity} value.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Multipartite entanglement in quantum algorithms

We investigate the entanglement features of the quantum states employed in quantum algorithms. In particular, we analyze the multipartite entanglement properties in the Deutsch-Jozsa, Grover, and Simon algorithms. Our results show that for these algorithms most instances involve multipartite entanglement.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Quantum search algorithms on a regular lattice

Quantum algorithms for searching for one or more marked items on a d-dimensional lattice provide an extension of Grover's search algorithm including a spatial component. We demonstrate that these lattice search algorithms can be viewed in terms of the level dynamics near an avoided crossing of a one-parameter family of quantum random walks. We give approximations for both the level splitting at the avoided crossing and the effectively two-dimensional subspace of the full Hilbert space spanning the level crossing. This makes it possible to give the leading order behavior for the search time and the localization probability in the limit of large lattice size including the leading order coefficients. For d=2 and d=3, these coefficients are calculated explicitly. Closed form expressions are given for higher dimensions.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Experimental implementation of a quantum random-walk search algorithm using strongly dipolar coupled spins

An important quantum search algorithm based on the quantum random walk performs an oracle search on a database of N items with O({radical}(phN)) calls, yielding a speedup similar to the Grover quantum search algorithm. The algorithm was implemented on a quantum information processor of three-qubit liquid-crystal nuclear magnetic resonance (NMR) in the case of finding 1 out of 4, and the diagonal elements' tomography of all the final density matrices was completed with comprehensible one-dimensional NMR spectra. The experimental results agree well with the theoretical predictions.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Decoherence in a dynamical quantum phase transition

Motivated by the similarity between adiabatic quantum algorithms and quantum phase transitions, we study the impact of decoherence on the sweep through a second-order quantum phase transition for the prototypical example of the Ising chain in a transverse field and compare it to the adiabatic version of Grover's search algorithm, which displays a first-order quantum phase transition. For site-independent and site-dependent coupling strengths as well as different operator couplings, the results show (in contrast to first-order transitions) that the impact of decoherence caused by a weak coupling to a rather general environment increases with system size (i.e., number of spins or qubits). This might limit the scalability of the corresponding adiabatic quantum algorithm.

36 MATERIALS SCIENCE↗

Optimal time schedule for adiabatic evolution

We show that, provided dephasing is taken into account, there is a unique timetable which maximizes the fidelity with a target state in adiabatic evolutions. The optimum has constant tunneling rate along the path. Application to quantum search algorithms recovers the Grover result for appropriate scaling of the dephasing with the size of the database. Moreover, the Grover bound imposes constraints on the dephasing rates of systems coupled to a universal Markovian bath.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Hybrid quantum computation

We present a hybrid model of the unitary-evolution-based quantum computation model and the measurement-based quantum computation model. In the hybrid model, part of a quantum circuit is simulated by unitary evolution and the rest by measurements on star graph states, thereby combining the advantages of the two standard quantum computation models. In the hybrid model, a complicated unitary gate under simulation is decomposed in terms of a sequence of single-qubit operations, the controlled-z gates, and multiqubit rotations around the z axis. Every single-qubit and the controlled-z gate are realized by a respective unitary evolution, and every multiqubit rotation is executed by a single measurement on a required star graph state. The classical information processing in our model requires only an information flow vector and propagation matrices. We provide the implementation of multicontrol gates in the hybrid model. They are very useful for implementing Grover's search algorithm, which is studied as an illustrative example.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Sampling on NISQ Devices: "Who’s the Fairest One of All?"

Modern NISQ devices are subject to a variety of biases and sources of noise that degrade the solution quality of computations carried out on these devices. A natural question that arises in the NISQ era, is how fairly do these devices sample ground state solutions. To this end, we run five fair sampling problems (each with at least three ground state solutions) that are based both on quantum annealing and, on the Grover Mixer, -QAOA algorithm for gate-based NISQ hardware. In particular, we use seven IBM Q devices, the Aspen-9 Rigetti device, the IonQ device, and three D-Wave quantum annealers. For each of the fair sampling problems, we measure the ground state probability, the relative fairness of the frequency of each ground state solution with respect to the other ground state solutions, and the aggregate error as given by each hardware provider. Overall, our results show that NISQ devices do not achieve fair sampling yet. Furthermore, we also observe differences in the software stack with a particular focus on compilation techniques that illustrate what work will still need to be done to achieve a seamless integration of frontend (i.e., quantum circuit description) and backend compilation.

Computer Science↗

Using Grover’s search protocol to select the best qubit pairs

This research represents a continuation of our investigation of the Rigetti quantum platform as part of the Quantum Leap for Fusion Energy Sciences project. We evaluate the performance of the new Aspen-11, Aspen-M-2, Aspen-M-3 quantum processing units (QPU) through the application of the Grover’s search algorithm and the validation of single gate fidelities. The performance of the new QPUs is compared to the older Aspen-7 device, and it is shown that qubit pair selection plays a key role in the optimization process. Additionally, we delve into the examination of coherent and decoherent errors associated with native gates. To optimize our approach, we have developed several relatively inexpensive hardware protocols aimed at facilitating the selection of the most suitable qubit pairs. These protocols involve running various circuits on the hardware and assessing the overall performance of the tested qubit pairs. Through these protocols, we have demonstrated that the quality of qubit pairs on a single chip can exhibit significant variations.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Non-Boolean quantum amplitude amplification and quantum mean estimation

This paper generalizes the quantum amplitude amplification and amplitude estimation algorithms to work with non-Boolean oracles. The action of a non-Boolean oracle $U_\varphi $ on an eigenstate $\mathinner {|{x}\rangle }$ is to apply a state-dependent phase-shift $\varphi (x)$. Unlike Boolean oracles, the eigenvalues $\exp (i\varphi (x))$ of a non-Boolean oracle are not restricted to be $\pm 1$. Two new oracular algorithms based on such non-Boolean oracles are introduced. The first is the non-Boolean amplitude amplification algorithm, which preferentially amplifies the amplitudes of the eigenstates based on the value of $\varphi (x)$. Starting from a given initial superposition state $\mathinner {|{\psi _0}\rangle }$, the basis states with lower values of $\cos (\varphi )$ are amplified at the expense of the basis states with higher values of $\cos (\varphi )$. The second algorithm is the quantum mean estimation algorithm, which uses quantum phase estimation to estimate the expectation $\mathinner {\langle {\psi _0|U_\varphi |\psi _0}\rangle }$, i.e., the expected value of $\exp (i\varphi (x))$ for a random x sampled by making a measurement on $\mathinner {|{\psi _0}\rangle }$. It is shown that the quantum mean estimation algorithm offers a quadratic speedup over the corresponding classical algorithm. Both algorithms are demonstrated using simulations for a toy example. Potential applications of the algorithms are briefly discussed.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Decoherence-protected quantum gates for a hybrid solid-state spin register

Protecting the dynamics of coupled quantum systems from decoherence by the environment is a key challenge for solid-state quantum information processing. An idle quantum bit (qubit) can be efficiently insulated from the outside world by dynamical decoupling, as has recently been demonstrated for individual solid-state qubits. However, protecting qubit coherence during a multi-qubit gate is a non-trivial problem in general, the decoupling disrupts the interqubit dynamics and hence conflicts with gate operation. This problem is particularly salient for hybrid systems, in which different types of qubit evolve and decohere at very different rates. Here we present the integration of dynamical decoupling into quantum gates for a standard hybrid system, the electron-nuclear spin register. Our design harnesses the internal resonance in the coupled-spin system to resolve the conflict between gate operation and decoupling. We experimentally demonstrate these gates using a two-qubit register in diamond operating at room temperature. Quantum tomography reveals that the qubits involved in the gate operation are protected as accurately as idle qubits. We also perform Grover's quantum search algorithm, and achieve fidelities of more than 90% even though the algorithm run-time exceeds the electron spin dephasing time by two orders of magnitude. Our results directly allow decoherence-protected interface gates between different types of solid-state qubit. Ultimately, quantum gates with integrated decoupling may reach the accuracy threshold for fault-tolerant quantum information processing with solid-state devices.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

Scalable quantum search using trapped ions

We propose a scalable implementation of Grover's quantum search algorithm in a trapped-ion quantum information processor. The system is initialized in an entangled Dicke state by using adiabatic techniques. The inversion-about-average and oracle operators take the form of single off-resonant laser pulses. This is made possible by utilizing the physical symmetries of the trapped-ion linear crystal. The physical realization of the algorithm represents a dramatic simplification: each logical iteration (oracle and inversion about average) requires only two physical interaction steps, in contrast to the large number of concatenated gates required by previous approaches. This not only facilitates the implementation but also increases the overall fidelity of the algorithm.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Grover-QAOA for 3-SAT: quadratic speedup, fair-sampling, and parameter clustering

Abstract The SAT problem is a prototypical NP-complete problem of fundamental importance in computational complexity theory with many applications in science and engineering; as such, it has long served as an essential benchmark for classical and quantum algorithms. This study shows numerical evidence for a quadratic speedup of the Grover Quantum Approximate Optimization Algorithm (G-QAOA) over random sampling for finding all solutions to 3-SAT (All-SAT) and Max-SAT problems. G-QAOA is less resource-intensive and more adaptable for these problems than Grover’s algorithm, and it surpasses conventional QAOA in its ability to sample all solutions. We show these benefits by classical simulations of many-round G-QAOA on thousands of random 3-SAT instances. We also observe G-QAOA advantages on the IonQ Aria quantum computer for small instances, finding that current hardware suffices to determine and sample all solutions. Interestingly, a single-angle-pair constraint that uses the same pair of angles at each G-QAOA round greatly reduces the classical computational overhead of optimizing the G-QAOA angles while preserving its quadratic speedup. We also find parameter clustering of the angles. The single-angle-pair protocol and parameter clustering significantly reduce obstacles to classical optimization of the G-QAOA angles.

Zhang, Zewen (ORCID:000000032258613X)↗