土, 22 1月 2022 21:44

Avoiding Barren Plateaus

During the current NISQ era of quantum computation the most common algorithms used to solve problems are based on a hybrid variational approach, where the quantum hardware is used to implement a variational wave function and measure observables, whereas the classical computer is used to store and update the variational parameters. Such algorithms are known as Variational Quantum Algorithms (VQAs) and are the most promising approach in reaching quantum advantage in the near future. However, despite proven advantages, variational algorithms are limited by the existence of barren plateaus (BPs) , which are regions of the optimization landscape where the gradients become vanishingly small. This makes the optimization exponentially hard as the gradients of the cost function are on average zero and deviations vanish exponentially in system size, which is furthermore exacerbated by finite estimation statistics in case of Hamiltonian averaging procedures.

So far, numerous approaches have been proposed to minimize this limitation. For instance, one can avoid BP at the initialization stage of variational algorithms, by performing pre-processing that finds a favorable initial configuration that can lead the system towards the desired optimization solution without the gradient becoming small. Also, studying the relation between BPs and entanglement can potentially lead to controlling entanglement to mitigate BPs. However, these approaches are impractical to implement on current quantum devices due to the difficulty in measuring entanglement. In an attempt to diagnose and avoid BPs, the authors in this paper propose the notion of weak barren plateaus (WBPs), which emerge when the entanglement of a local subsystem exceeds a certain threshold identified by the entanglement of a fully scrambled state. Utilizing WBPs, the authors propose a general algorithm to avoid barren plateaus that can be implemented on available NISQ devices, both at initialization and during the optimization.

The proposed algorithm estimates the expectation value of the cost function, its gradients, and the second Rényi entropy of small subsystems using classical shadow estimation during the optimization process. For the optimization procedure, gradient descent is used. The classical shadows protocol enables the tracking of the second Rényi entropy, which allows for an efficient diagnosis of the WBP both at the initialization step and during the optimization process of variational parameters. Upon encountering a WBP, as a certain subregion having a sufficiently large Rényi entropy, the algorithm restarts the optimization process with a decreased value of the update step. This process is controlled by a certain learning rate. The overall results show that the absence of WBPs is a sufficient condition for avoiding BPs.

The work further includes numerical simulations utilizing variational quantum eigensolvers (VQE) to test the proposed algorithm. For this, a WBP-free initial state is prepared using small qubit rotation angles. The algorithm is then implemented with different learning rates to compare the optimization performance. The results show that lower learning rates avoid WBPs during the optimization cycle, however if the learning rate is further decreased after an optimum value, then the algorithm converges slower and therefore to a larger (worse) energy due to the less than necessary training iterations. Hence, the learning rate should be sufficiently low enough to avoid BPs, but at the same time high enough such that it does not degrade the performance.

The results further indicate that entanglement also plays a crucial role in circumventing BPs and is important for achieving a good optimization performance. Moreover, observing the optimization performance according to the learning rate used, indicates that the system might get stuck in local minima characterized by large entanglement. The proposed way to avoid such areas is to define a parameter ‘alpha’ that suggests the presence of a WBP. It was found in the experimentation that setting the parameter ‘alpha’ to less than 1 can be beneficial for the optimization. This can help in avoiding low-quality local minima that are characterized by higher entanglement. However, this requires the entanglement structure of the target state to be previously known. One potential direction to further explore is whether an algorithm can be designed where the learning rate can be dynamically adjusted at every step of the optimization process and not only when a WBP is encountered. This may allow for efficiently maneuvering complicated optimization landscapes by staying clear of highly entangled local minima. Avoiding barren plateaus is a critical step in increasing the performance of any VQA, therefore it will be of interest to test the applicability of the techniques introduced here for quantum machine learning, quantum optimization, or variational time evolution.
土, 15 1月 2022 21:49

Decompositional QGNN

Quantum Machine Learning is a field that aims to solve Machine Learning problems with quantum algorithms and quantum computing. There exists a large variety of quantum algorithms used in solving such problems, with the most common being Quantum Neural Networks (QNNs). Varieties of QNNs include Quantum Convolutional Neural Network (QCNN), Quantum Generative Adversarial Network (QGAN), and Quantum Graph Neural Network (QGNN). As the names suggest, these algorithms are inspired from their classical counterparts. In this paper, the proposed algorithm is a hybrid quantum-classical algorithm for graph-structured data, which is called Decompositional Quantum Graph Neural Network (DQGNN), and is based on the classical GNN, which is one of the most popular learning tools, especially for dealing with non-Euclidean data. The main differentiator between the DQGNN and previous QGNN implementations is the decompositional aspect of this algorithm, that allows the computation of larger-sized graph-structured data with a fixed-sized quantum circuit with limited number of qubits, regardless of the size of the data. Algorithms based on GNNs have found applications in social network analysis, drug design, combinatorial optimization, and multi-agent learning.

GNNs function on the basis of the neighborhood aggregation strategy, which involves updating the representation of a graph node by recursively aggregating the representations of its neighbors. So far, a variety of GNNs has been realized such as the Relational Graph Convolutional Networks (R-GCN), Graph Isomorphism Networks (GIN), edGNN, Random Walk Graph Neural Networks (RW-GNN), and Factorizable Graph Convolutional Networks (Factor GCN). However, these approaches embed nodes represented as points in a Euclidean space leading to significant structural distortion and information loss during computation. On the other hand, DQGNN is a hybrid quantum-classical algorithm for graph-structured data, that focuses on effective and scalable learning.

DQGNN utilizes tensor and unitary matrices to implement a quantum GNN by designing a quantum circuit and replacing the Euclidean weight matrices of the GNN with unitary matrices, i.e. quantum gates. Utilizing tensor products offers two advantages: i) enlarges the node representation space exponentially such that nodes with different features can be mapped to different representations, and ii) requires significantly fewer model parameters than related deep learning models. DQGNN consists of the following processing steps; 1) A classical computer is used to decompose graphs into subgraphs. 2) The circuit of the mapping method is trained with node features. After training, the node features of the subgraphs are mapped into quantum states by applying the circuit. 3) The quantum circuit is implemented on a quantum device to compute the representations of the different subgraphs sequentially. 4) Finally, a classical computer computes the entropies of the individual representations and combines them. All these steps are iterated for obtaining graph representations for classification.

Besides the proposed decompositional processing strategy, a trainable method is also proposed for mapping data from a Euclidean space to a Hilbert space, which can maintain distance relations and reduce information loss during the mapping.

DQGNN is evaluated experimentally on six graph classification benchmarks. The compared methods include graph kernels, deep learning methods, and quantum machine learning methods. DQGNN is also compared with recent baselines for graph classification: 1) Kernel-based methods: WL subtree kernel, and Subgraph Matching Kernel (CSM), 2) Representative GCNs, including Deep Graph CNN’s (DGCNN) and Relational Graph Convolutional Networks (R-GCN), 3) Representative GNNs, i.e., Graph Isomorphism Network (GIN), edGNN, and RW-GNN. A derivative-free optimization method, UOBYQA is utilized for training DQGNN. A quantum simulator is used to implement quantum machine learning models on a classical computer utilizing codes by Qiskit and Tensorflow Quantum.

The results demonstrate that DQGNN achieves the best results on 5 out of 6 benchmarks with accuracy close to GNNs, while requiring fewer parameters in comparison. As compared to the GNN model with the least parameters referenced as DGCNN, the authors find that DQGNN achieves similar performance with only 1.68% parameters of the classical counterpart. The performance is also compared with alternative quantum machine learning methods like QSVM (Quantum-enhanced Support Vector Machine) and QCNN (Quantum Convolutional Neural Networks) using the graphlet count vector as the inputs (Gra+QSVM, Gra+QCNN). Results show that Gra+QSVM, Gra+QCNN and Gra+QCNN with the proposed trainable mapping method (Gra+QCNN w/M) demonstrate no improvement on DQGNN. However, as compared to Gra+QCNN, Gra+QCNN w/M achieve higher accuracy, therefore highlighting the effectiveness of the proposed mapping method. For example, in the case of the PROTEINS dataset, the accuracy achieved by DQGNN is 9% higher than that of DQGNN without the mapping. This improvement can be resulted from less information loss in the former case.

DQGNN is a method that can be applied to any application that includes graph-structured data, and offers many advantages compared to other contemporary algorithms. The main advantage lies in the ability to divide the graph into sub-graphs and process each sub-graph one at a time with DQGNN, while using the same quantum circuit. Such methods can help with potential scalability issues that other algorithms might exhibit. Furthermore, it is speculated that the proposed mapping method can enhance the accuracy of alternative quantum machine learning methods, because of less information loss.

DQGNN provides a good insight into transitioning to larger-sized graph-structured data during the NISQ era (limited qubits); requiring fewer parameters but having similar performance to other contemporary quantum algorithms.
土, 08 1月 2022 21:52

Quantum Capsule Networks

Artificial Intelligence incorporates two important complementary approaches namely connectionism and symbolism. Connectionism aims to model intelligence as an emergent phenomenon by connecting a large number of neurons while symbolic AI is based on logic, deduction, and higher-level symbolic representations. Recent attempts focus on uniting these two approaches leading to the development of Capsule Networks (CapsNets).

The building block of capsule networks is a so-called ‘capsule’ which is a group of neurons represented by a vector to encode different features of an observable entity such as shape, color, texture, deformation, etc. The information is then transferred through capsule layers hierarchically i.e. the capsule in the higher-level layer is predicated upon its geometric relationship with the lower-level one. This routing mechanism used in CapsNets can preserve the geometric relationships amongst entities and hence have more intrinsic explainability than regular (classical) Neural Networks (NNs). Inspired by the advantages of classical CapsNets, the authors in this paper propose a quantum capsule network (QCapsNet) to explore a potential quantum advantage over the classical counterpart. In QCapsNets, interacting qubits are encapsulated into a capsule as the building block of the architecture.

QCapsNets consist of three crucial components; i) the preprocessing layers, ii) the capsule layers, and iii) the quantum dynamic routing process. Firstly, the model’s input is fed into the preprocessing layers to extract some preliminary features. These features are then encapsulated into several quantum states and then sent to the capsule layers. Inside each capsule, there are a group of interacting qubits building up a sub-quantum neural network (sub-QNN). To enable the feed-forward process between the two adjacent capsule layers, a quantum dynamic routing algorithm is proposed. This routing algorithm operates with a certain routing probability which is dynamically updated with the geometric relationship between capsule layers.

For benchmarking the performance of QCapsNets against classification accuracy, numerical experiments were performed on three proposed models of QCapsNets, each with different sub-QNNs i.e. i) parameterized quantum circuit (PQC), ii) deep quantum feed-forward neural network (DQFNN), and iii) post-selection deep quantum feedforward neural network (post-DQFNN). The QCapsNets is then applied to the classification of handwritten digit images in the MNIST dataset. The results demonstrate that the inaccuracy of all three QCapsNets is reduced to less than 2 × 10^(−2) as the number of parameters increases. Also, the proposed quantum dynamic routing algorithm is able to evaluate the distance measure of quantum states in parallel, and thus is suggested to achieve an exponential speedup over its classical counterpart, given the same number of parameters. No rigorous proof has been established with this regard though.

Furthermore, the work tests the efficiency of QCapsNets in making critical decisions. To achieve this, the QCapsNet is attached to a classical encoder (CNN) and a classical decoder (feed-forward network). The whole network is used to reconstruct the input image from the MNIST dataset. The results demonstrate that the potential to encode information in each capsule seems to grow close to exponentially, just as the Hilbert space grows exponentially with respect to the number of qubits, implying a potential for quantum advantage compared to classical CapsNets.

This work suggests QCapsNets as an efficient approach demonstrating state-of-the-art accuracy among quantum classifiers. It is claimed that by means of geometric relationships, QCapsNets can capture the essential features of the input data, and then encapsulate them into the output capsule of which one specific subspace could correspond to a human-understandable feature of the input data.

QCapsNets can act as guide towards explainable quantum artificial intelligence, with some potential directions to explore being consideration of other distance measures to quantify the geometric relationships between capsule states, and exploration of the robustness of QCapsNets against adversarial perturbations as compared to traditional quantum classifiers.
The majority of quantum computers at the moment operate in accordance to the gate-based model. The gate-based model includes a universal set of gates, with the most common one employing only single- and two-qubit gate operations. Such quantum devices face difficulties in controlling all relevant degrees of freedom as the system is scaled up, due to both current hardware limitations and software challenges. Despite taking advantage of techniques like error correcting codes and optimization protocols, associated gate errors pose significant limitations, mainly due to hardware imperfections. A typical example where such scaling limitations are evident is the simulation of the Fermi-Hubbard model using conventional quantum computers, which is a simulation that is only possible for small systems with a limited number of fermionic lattice sites. To overcome this, alternative approaches which are not based on the execution of the standard two-qubit gates can be exploited.

One such alternative that is proposed in this work is hybrid digital-analog quantum computing. Here, single-qubit gates as well as individual readouts of qubits are accessible similarly to the case of gate-based model. However, in the case considered in this paper, quantum entanglement is created using always-on native interaction of qubits.

The always-on interaction between qubits diminishes the fidelity of single-qubit gates, but creates the entanglement that would otherwise require two-qubit gates. Therefore, a certain trade-off between the two should be found. A proposition to overcome this limitation, is to have a switchable interaction between qubits that can be turned off during the execution of single-qubit gates. In this paper, the authors analyze a digital-analog approach based on the fermionic SWAP network and refocusing technique, to simulate the dynamics of fermionic systems, in particular the Fermi-Hubbard model.

Firstly, a two-qubit fermionic simulation gate is parameterized by the Hamiltonian constants. The key idea is based on changing the qubit numbering in the Jordan-Wigner transformation on the fly and combining it with the evolution operator, to create such a two-qubit gate. This gate is used to circumvent difficulties associated with the mismatch between the fermion statistics of the simulated system and Pauli statistics relevant for qubits. After establishing a fermionic SWAP network, refocusing techniques are implemented to disable the interaction between certain qubits. This refocusing operation is based on a partition of the total interaction time of the desired operators involved in the realization and can be represented by action or non-action of Pauli X operators between selected idling times.

Furthermore, the authors study the impact of the connectivity amongst the qubit network. In the case of full connectivity of qubits, the digital-analog quantum device is shown to be inefficient for the implementation of the fermionic SWAP network as the circuit depth scales as O(n2), where n is the number of qubits. For spinless fermions the optimal topology is found to be a 1-dimensional chain, and for spin-1/2 fermions the optimal topology is found to be a ladder. While searching for the optimal topology, the simulation of the single Trotter step of the evolution requires O(n) applications of multiqubit gates. In terms of the refocusing technique, it is shown that the circuit depth also increases by a factor of O(n).

The work also analyzes the errors occurring during the determination of interaction constants and shows that these errors leads to the weak quadratic growth of infidelity as a function of the deviation of the actual coupling constants from the assumed values. While this error has a positive impact on the digital-analog approach, the depolarizing noise on the other hand leads to the linear decrease of fidelity as a function of error probability. Hence, the depolarizing noise poses severe challenges in the implementation of the digital-analog simulation of fermionic systems.

Such a hybrid digital-analog scheme is an interesting attempt to perform quantum computation, while avoiding the two- and multi-qubit gates in general that suffer from low fidelities due to manufacturing issues in current hardware. Although this is presented as a viable model of computation, there are still many issues and trade-offs that need to be resolved. However, as pointed out in this work such a model of computation can have many benefits when specific problems are addressed, such as the simulation of fermionic systems of many dimensions since all qubits in the chip can be used uniformly in time.
日, 19 12月 2021 12:54

Quantum Semidefinite Programming

Semidefinite programs (SDPs) in the classical optimization literature are considered as a generalization of linear programs (LPs), in which the vector inequalities of linear programs are replaced by matrix inequalities. Many quantum information problems can be formulated as SDPs, including combinatorial optimization, control theory, and state discrimination. Typically, SDPs can be solved efficiently in time polynomial in the dimension of the input matrices, using classical algorithms; however with an increase in the involved matrices size, many first-order and second-order methods require multiple gradient evaluations at each iteration that subsequently leads to significant computational overhead.

So far, quantum algorithms have been proposed for solving SDPs with a proven quadratic speedup over their classical counterpart, however such quantum algorithms require a fault-tolerant quantum computer to realize the promised speedup. Since there are no fault-tolerant quantum computers available at the moment, the focus is currently on designing quantum algorithms for solving SDPs that can be implemented on NISQ devices. The authors in this work develop variational quantum algorithms for solving three different kinds of SDPs. The additional objective is to analyze the convergence rates of the algorithms corresponding to the standard formulation of an SDP.

The considered SDPs cases are i) General form (GF): when SDPs are not weakly constrained i.e. the dimension of the constraint variable is not much smaller than the dimension of the objective variable. ii) Standard Form (SF): when SDPs are weakly constrained i.e. the dimension of the constraint variable is much smaller than the dimension of the objective variable. Besides the form (general or standard), the authors further categorize the SDP cases for SF based on the constraints, namely the Equality Constrained Standard Form (ECSF) and Inequality Constrained Standard Form (ICSF).

Firstly, these constrained optimization problems are reduced to their unconstrained forms by employing a series of identities. Then, the final unconstrained form is expressed as a function of expectation values of the input Hermitian operators. These final unconstrained formulations are solved by implementing a gradient-based method using parameterized quantum circuits. These parameterized quantum circuits use the parameter shift rule to evaluate the partial derivatives of the objective function with respect to circuit parameters. Finally, variational quantum algorithms are designed to solve these unconstrained optimization problems. The proposed methods provide bounds on the optimal values, due to the reduction in the search space, as well as the non-convex nature of the objective function landscape in terms of ansatz parameters.

The convergence of the proposed algorithms is simulated for three cases based on the number of constraints (M) and the dimension of the input Hermitian operators (N), and the nature of the constraints: i) N=M, ii) N>M (Equality constraint), and iii) N>M (Inequality Constraint). The algorithms were simulated using the QASM simulator of the Qiskit Python package for three different shot settings, namely 10, 50, and 100 shots. The numerical simulations demonstrate that all three algorithms approximately converge to their respective optimal value, even in the case of few shots.

Overall, the work proposes variational quantum algorithms for different instances of SDPs and demonstrates numerical simulations of their convergence rates. The estimation of the gradient (of the objective function) of the proposed forms is done using parameterized circuits assuming that the estimators are unbiased and with small variance. These results are promising since they indicate that even with small amount of shots and some noise in the quantum system, the algorithm is capable of converging to the optimal solution of the optimization problem, and a potential next step would be to study the effect that a large variance in these estimators would have on the convergence rate of the algorithms. Nevertheless, one should keep in mind that this algorithm is focused on solving simple problems defined as semidefinite programs employing the advantages that variational quantum algorithms provide, in an effort to bridge the gap between existing classical implementations and future quantum fault-tolerant ones. This work focuses on the estimation of the gradient descent that can be challenging in the classical algorithms, and is in line with other quantum implementations that indicate the speedup, while maintaining good performance, compared to corresponding classical implementations.
火, 14 12月 2021 12:28

Shallow Circuits in Variational QML

Variational Quantum Machine Learning (VQML) models are based on variational principles where computation is done on a quantum computer with classical model parameters. These algorithms have shown efficient performance even in the presence of noise in hardware implementations, making them compatible with current Noisy Intermediate-Scale Quantum (NISQ) devices.

At the moment, there exist many useful approaches for implementing VQML algorithms, especially for solving machine learning tasks, however no clear ‘optimal’ approach to designing the circuit architectures has been identified. Some approaches use reinforcement learning or simulated annealing to design variational quantum circuits, however these techniques are sample-inefficient. Furthermore, such techniques are not applicable when access to real devices is scarce and can be expensive for a higher number of qubits. In addition, deep quantum circuits in principle have a higher capacity over shallower circuits given a fixed number of qubits, however there is no clarity on how to take advantage of such benefit. The authors in this work attempt to establish a set of core design principles for VQML, focusing specifically to classification tasks. The objective also includes investigating the effects of key architecture properties on machine learning model performance, noise apparent in the system (inducing a range of errors into the model), and the number of qubits used.

The work explores an ansatz based on fixed blocks from which circuits are sampled and evaluated. The following workflow was established to explore a large range of candidate circuits given a dataset and (classical) optimizer, 1) creating a number of candidate circuits by randomly sampling the available design space with trainable parameters such as number of qubits, the entanglement pattern, the number of blocks and the configuration of blocks, 2) compiling these circuits into an executable Qiskit circuit, 3) deriving a number of noise models to be applied to circuits, based on the two decoherence times and gate duration, 4) compiling the noise models into Qiskit executable noise model, and 5) training all permutations of circuit designs and noise models and evaluating their performance.

The design guidelines were established for VQML classifiers based on experiments with a large number (n = 6500) of circuits applied to five common datasets. All VQML models (circuits) were trained using the COBYLA optimizer for a maximum of 200 epochs. The overall results suggest four design guidelines: i) Circuits should be as shallow as possible since they are more robust to two-qubit-gate errors and generally have higher accuracy potential in both noisy and noise-free simulations ii) Circuits should be as wide as possible, iii) The number of features should be kept small, which can be done through dimensionality reduction techniques like PCA and, iv) The noise level should be small. It is also observed that measurement error is only a significant factor if “large”, i.e. > 10%.

Since the results demonstrate that overall low depth circuits exhibit a larger variance, it is crucial to explore improvement in results when the number of qubits is increased further. Also, the design space and constraints on the proposed model introduce limitations in leveraging the maximum number of qubits. It is an important future scope to explore tradeoffs in relaxing these constraints. For instance, by using features multiple times, wider circuits can be implemented, however, this could increase circuit depth and potentially variance. Further study of various circuit designs can also involve the influence of the barren plateau problem. Moreover, a larger variety of noise models and sources of noise, especially inspired from noise in hardware, should be further studied to develop more noise resilient circuits. Finally, as these results represent only 5 datasets, a potential next step would be to analyze classification problems with more classes or features via exploring larger numbers of datasets and models.
月, 13 12月 2021 12:41

Improving Quantum K-Means

Many quantum machine learning algorithms draw inspiration out of their classical analogues and attempt at solving the same problem with the help of quantum computing. Q-means is one such algorithm which is the quantum analogue of the classical K-means algorithm. K-Means is an unsupervised learning algorithm in machine learning, which groups the unlabeled dataset into different clusters, thus discovering the categories of groups in the unlabeled dataset. On the other hand, Q-means is implemented on the quantum states to obtain characteristic cluster quantum states, i.e. the quantum states that are in a superposition of all the quantum states in a particular cluster. This is done by evaluating a cost function based on the cluster quantum states through measuring the overlap or fidelity between the characteristic cluster quantum states, ensuring high separation between clusters and low cluster scatter about the centroids.

Early implementations of Q-means claim an exponential speedup over its classical counterpart, which sounds very promising since this is a NP-Hard problem for d-dimensional observations; however, this speedup is only possible for linearly separable clusters. Q-means performs cluster assignment based on Euclidean distances, which does not work for non-linearly separable clusters in the original space, which can be a significant limitation. Therefore, there is a need for feature mapping / kernel methods to efficiently separate the data in a high dimensional space, which is closely related to the Support Vector Machine (SVM) method of operation.

This paper proposes a hybrid quantum-classical algorithm that learns a suitable quantum feature map which separates non linearly separable unlabeled data using a variational quantum feature map and Q-means as a subroutine for unsupervised learning. The objective of the paper is the proposal of the new hybrid algorithm that includes Q-means. The objective of the algorithm is to maximally separate the clusters in the quantum feature Hilbert space.

The quantum circuit involves encoding unlabeled classical data using quantum gates that perform unitary operations on the initial quantum state based on quantum parameters and input data. To perform quantum feature encoding, 1) a variational circuit is used to learn the best possible quantum feature map that obtains meaningful clustering results. Since the quantum feature Hilbert space dimensions are exponential with respect to qubits used in the initial state, high dimensional feature spaces can be efficiently implemented. 2) Kernel estimation and cluster assignment is then performed by implementing the Q-means sub-routine. 3) Finally, measurement is done to compute the overlap between the characteristic cluster quantum states, that also acts as a measure of separation between the clusters. 4) The output of the complete quantum circuit is used to compute the value of the cost function that is based on the Hilbert-Schmidt distance between the density matrices of the characteristic cluster quantum states.

The simulations were implemented to compute overlap cost function using Pennylane’s QAOA embedding framework. Sk-learn is used to pre-process all the datasets before quantum embedding. Cluster datasets with labels were used as inputs for the quantum embedding circuit to train the quantum parameters. For the considered 3 datasets; blobs, concentric circles and moons, the algorithm took the least iterations to converge for the blobs as they are very well separated in the original space, whereas in the case of non-linearly separable datasets, the algorithm took a larger number of iterations to converge.

The overall method adapts a repetitive approach of performing unsupervised learning followed by adaptively training the feature map, which aims at learning the best representation of the data in the quantum feature Hilbert space. It is shown that one can explore more feature spaces that are better suited for the embedded dataset by explicitly implementing the kernel estimation. However, since there are no quantum simulators available to test Q-means to date, the work could not establish quantum advantage experimentally.
Quantum computing has been progressively applied in the field of quantum chemistry, especially applying modern computational approaches to navigate molecular potential energy surfaces. One such problem is calculation of forces, i.e. calculating the derivative of energies with respect to nuclear positions. These calculations are usually done by Molecular Dynamics (MD) simulations, and are used in multiple applications such as the description of heterogeneous processes on surfaces including catalysis, observation of phase transitions (e.g. nucleation processes for water), and in pharmaceutical research (observation of the interaction of drugs with their targets in the human body).

So far, quantum algorithms like force estimation via the Hellman-Feynman theorem and quantum gradient estimation have been implemented experimentally. However, these algorithms suffer from limited accuracy in a fault-tolerant or NISQ setting. There has been theoretical work that addresses the theoretical chemistry behind force estimation on a quantum device, presenting a detailed derivation in a Lagrangian formalism focusing on an ab initio exciton model, and stressed the importance of including full response. Also, the mathematical formulation of force estimation in NISQ on a significantly stronger footing has been provided, which combined this with gradient estimation for the optimization of variational quantum eigensolvers. The progress also includes small-scale experimental implementations.

In this work, the authors propose new quantum algorithms and resource estimates for computing molecular energy derivatives. The objective is to optimize and cost (value) methods for estimating forces and other first-order energy gradients for NISQ and fault-tolerant quantum computers. Firstly, the work estimates energy derivatives via the Hellman-Feynman theorem presenting a simple, calculable derivation of the force operator in second quantization for an atomic-centered basis orbital set, based on the orbital connection theory of Helgaker and Almlöf. Following that, the work derives the exact form of the force operator in a plane wave basis in first- and second-quantization. In order to estimate the error tolerance on a force vector, radial distribution function calculations were carried out for a system of 216 water molecules. The results demonstrate that for relevant molecular dynamics and geometry optimization, an RMS of the error in one force component should be below a certain threshold (0.6 mHa/Å).

Secondly, in order to estimate force vectors in molecular systems, the authors employ the state tomography method and optimization assuming that the preparation of an initial state satisfies the Hellman-Feynman theorem. The work shows calculations of the relevant bound on the cost of the number of measurements to estimate a constant 2-norm error, both analytically and numerically for hydrogen chains along with the estimation of the asymptotic costing for both. Since block-encoding is a required step in FTQC, the work proposed two methods - finite-difference algorithms for computing gradients as well as another method based on estimating expectation values of force operator to block-encode Hamiltonians and force operators in second quantization for factorized methods, and in first quantization for plane waves. The finite-difference algorithm is shown to provide asymptotically better scaling where the expected cost of state preparation is low, whereas in the case of high state preparation cost, the gradient operator approach provides better scaling. Moreover, the cost of simulating forces is similar to the cost of simulating Hamiltonians using sparse simulation methods, but for factorized methods, the cost is clearly asymptotically lower.

Practically speaking, the MD simulations require on the order of 106 − 109 unique force calculations estimating multiple hours of computing time for single-point energy calculations on fault-tolerant devices. An important result of this work is to show that such numbers are impractically large and prohibit immediate quantum advantage to be obtained with current generation hardware and methods.

Further research in force optimization can be done in improving the bounds on the variance obtained for NISQ systems. Moreover, it would be highly advantageous to perform a fully-quantum simulation as opposed to a semi-classical one, to avoid the costly gradient computation step. One approach could be simulating the differential equation governing the dynamics on the quantum computer itself, while retaining a classical description of the nuclear motion within the Born-Oppenheimer approximation, or by a fully-quantum simulation that treats the nuclei and electrons on a similar footing such as a first quantized simulation. Alternatively, taking a small number of measurements from a quantum device and fitting a semi-empirical model to the results can also be considered. This could be done using a semi-classical molecular mechanical model. Finally, one could consider reusing points from finite difference calculations, or sparsely sampling gradients to reduce these constant factor overheads. To conclude, it’ll be interesting to monitor progress in this field to properly predict when and where quantum computers could provide benefits in the computation of molecular forces and in-general energy gradients.
火, 16 11月 2021 12:25

Avoiding Barren Plateaus

In Quantum Machine Learning (QML), Variational Quantum Algorithms (VQAs) are a well-known class of algorithms that optimize parameters in a sequence of unitary operations, the product of which describes the time-evolution of the system and are compatible with current NISQ devices. The Variational Quantum Circuits (VQCs) included in the VQAs, typically rely on gradient based optimization to iteratively minimize a cost function evaluated by measuring output(s) of a quantum processor. A well-studied drawback of such methods is that they are limited by the existence of barren plateaus of the error surfaces i.e. exponentially vanishing gradients with increasingly large parameter regimes in sufficiently expressive parametrized quantum circuits (PQCs).

So far, previous works have investigated the dependence of barren plateaus on the locality of objective functions, circuit depth, spatial and temporal locality, and expressibility of the parametrization ansatze. In PQCs, the classical optimization process typically relies on gradient descent methods, which can lead to the gradient becoming extremely small, a phenomenon known as barren plateaus. However, the exact scaling behavior and emergence of barren plateaus in ansatz-agnostic VQAs is still unknown. In this paper, the authors propose a Fourier mode parametrization ansatz for quantum information processing, where one can control the Fourier coefficients of the system parameters of a Hamiltonian, i.e. the Fourier coefficients are trainable making the ansatz non-local in time.

Unlike discrete, gate-based quantum circuits, where the protocols of the gate implementations are sequential, the resulting protocols in the proposed method are parallel and continuous by construction, which ensures that the change in the resulting unitary transformations is smooth with respect to the Fourier coefficients. In order to reduce computational complexity, the amount of parameters, i.e. non-zero Fourier coefficients, is restricted by limiting the modes to low-end frequencies. The authors use measurement based quantum natural gradient (QNG) descent in a hybrid learning scheme in order to find solutions to a given objective function. Firstly, an input state is given to a quantum processing unit (QPU) along with a set of Fourier coefficients of the parameters of the QPU’s underlying Hamiltonian, as an initial guess. The input state is evolved with respect to the time-dependent system Hamiltonian. The generated output state is then measured to determine the value of the objective function as well as the Fubini-Study metric of the input state with respect to the Fourier coefficients. Furthermore, the quantum natural gradient update step is calculated to modify the Fourier coefficients in order to improve the value of the objective function. The steps of the algorithm are then iterated in order to yield a set of Fourier coefficients that generate the desired target transformation.

The proposed ansatz is compared to the optimal control ansatz of step-wise parameterizations for the considered objective functions, as well as minimizing the energy of given problem Hamiltonians. The results show that the Fourier based ansatz demonstrate higher fidelity and superior convergence in comparison, hence outperforming the step-wise protocols in speed and consistency. The effective implementation time is also observed to be comparable in both ansatze, indicating the absence of barren plateaus without increasing the effective protocol implementation times. The proposed ansatz also showed non-vanishing variances in the objective function gradients, further indicating the absence of barren plateaus.

These results demonstrate the proposed ansatz is a promising candidate for overcoming barren plateaus in quantum algorithm optimization and also presents an alternative to parametrizations that are discrete or local in time. This approach can assist the on-going efforts of implementing quantum computing by providing a realistic and efficient access to optimal quantum algorithm protocols. A future scope along similar lines, will be to study the scaling behavior associated with the absence of barren plateaus.
木, 11 11月 2021 12:23

Quantum Kernel Bandwidth

Quantum Kernels have shown great promise in many quantum supervised machine learning methods where an appropriately defined kernel may provide speedups over classical ML methods. In quantum kernel methods, data points are mapped to quantum states using a quantum feature map, and the value of the kernel between two data points is given by some similarity measure (such as fidelity) of the corresponding quantum states. The advantage compared to classical kernels lies in processing the data using an exponentially sized Hilbert space and performing classically hard computations.

One major limitation to these methods is the exponentially decreasing fidelity of two random quantum states with the number of qubits, which leads to the exponential vanishing of kernel values that makes learning impossible, as such small differences can not be distinguished nor used for training. One can overcome this by controlling the inductive bias of the quantum kernel methods, by projecting the quantum state into a lower-dimensional subspace which can be done via hyperparameter tuning. One such hyperparameter is the kernel’s ‘bandwidth’. In this work, the authors identify quantum kernel bandwidth as a centrally important hyperparameter for quantum kernel methods.

The work considers the problem of supervised learning, specifically the task of classification. Given a training dataset, the goal is to learn a map from data points to labels that is in agreement with the true map with high probability on an unseen test set. The datapoint is encoded in a quantum state by a parameterized unitary. This unitary is referred to as a Hamiltonian evolution quantum feature map. A kernel matrix is then obtained by computing the quantum kernel for all pairs of data points. This value can be computed on a quantum computer by measuring the value of appropriate observable on the state. This kernel matrix is then used inside a Support Vector Machine (SVM) or other kernel methods.

The results demonstrate that varying the quantum kernel bandwidth, typically via the scaling factor and Trotter steps in the feature map, controls the expressiveness of the model. For the quantum feature maps considered, the bandwidth can be controlled by rescaling the data points. Numerical simulations were done with multiple quantum feature maps and datasets using up to 26 qubits. The results show that larger scaling factor leads to a narrow kernel for which the Support Vector Classifier can fit any labels, leading to overfitting. On the other hand, choosing too small values of scaling factor leads to a wide kernel making it insufficiently expressive, hence leading to underfitting. Optimizing the bandwidth can improve the performance of quantum kernel methods with qubit count. It was also observed that hardware limitations such as finite precision of controls and the variance introduced by sampling, do not limit the overall performance significantly.

The overall work discusses the potential of controlling the inductive bias of quantum kernels via projecting them into a lower-dimensional subspace using hyperparameter operations. Combining this projection with bandwidth optimization, leads to more precise modulation of the inductive bias of the model. Following the results of this work, it would be interesting to explore more elaborate feature maps with more tuned hyperparameters. Optimizing hyperparameters of quantum kernels may enable the tuning of inductive bias of the model in a classically feasible way and at the same time can bridge the gap between expensive fully trainable quantum embeddings and fixed feature maps.
金, 05 11月 2021 12:13

Quantum Combinatorial Relaxation

One of the main research interests in quantum computing is solving NP hard combinatorial problems. So far, methods like quantum adiabatic eigenstate evolution and the quantum approximate optimization algorithm (QAOA) have been proposed in order to harness quantum advantage. One limitation of the QAOA framework is that the cost function to be optimized on a quantum computer has a classical maximal eigenstate. This is in contrast to quantum many-body Hamiltonians or quantum chemistry, whose extremal eigenstates often are very entangled in the default or ‘natural’ basis.

The authors in this paper present algorithms which produce approximate solutions of combinatorial problems, searching for extremal eigenstates of local quantum Hamiltonians. These local quantum Hamiltonians are relaxations of the original combinatorial problems which means that for each element in the image of a combinatorial cost function, a quantum state with the same Hamiltonian expectation value can be constructed. A candidate ground state can then be obtained with variational eigensolvers, quantum phase estimation, approximation algorithms for quantum Hamiltonians, or quantum imaginary time evolution. This work uses the variational approach on prototypical NP-hard problems like the maximum cut (MaxCut) problem and weighted MaxCut.

Once a quantum relaxed Hamiltonian is prepared, its relaxed energy is rounded to an admissible value to the highest-energy state associated with the Hamiltonian. This highest-energy state is mapped to the ground state. For almost all graphs, its energy is strictly greater than the energy of the embedding of the optimal configuration of binary variables. To overcome this, candidate configuration was done using two rounding methods, magic state rounding and Pauli rounding. Magic state rounding takes a single-qubit density ρ and uniformly at random selects a measurement basis in which to measure a quantum state, while Pauli rounding is based on the direct estimation of the Pauli operators associated to each vertex.

The work also presents numerical simulations and hardware experiments benchmarking the relaxation methods proposed. To test the two rounding methods, numerical simulations were proposed on random MaxCut instances on 3-regular graphs of increasing size where Pauli rounding obtains better approximation ratios on average. The numerical experiments are conducted using a COBYLA optimizer, while the experiments on the superconducting processor were performed with an adaptive SPSA optimizer using 8192 measurements for each independent basis to estimate the relaxed Hamiltonian. In the case of the superconducting quantum processor the approximation ratio of 0.91 is obtained for 40-node graphs on unweighted 3-regular MaxCut and 0.96 on weighted planar MaxCut. The results establish connections between the energy of a relaxed quantum state and the average value of its rounded MaxCut approximation. Also, rounding from higher relaxed energy states leads to better combinatorial solutions.

A potential direction will be to explore classes of graphs that show large separations between the highest energy states of the relaxed spectrum and the optimal classical cut values. Also, for preparing ground state approximations for the relaxed problems, approximation algorithms for many-body quantum states can be used. Furthermore, other than embeddings based on 1-qubit quantum random access codes, other more sophisticated embeddings can be tested to get improved relaxations. Future scope can be in investigating rounding protocols for relaxed states which could take non-local qubit correlations into account.
金, 29 10月 2021 17:39

Quantum Portfolio Optimization

Quantum computing is currently being explored to target a wide variety of problems, with optimization-type problems being one of the primary applications. A specific type of optimization problem in finance, where it is believed that quantum computing could potentially have an advantage over classical computing, is portfolio optimization, due to its complex and time consuming nature in classical approaches. Portfolio optimization can be formulated in the language of quadratic program programming, which can in-turn be written in a feasible format for a quantum computer, with the cost function enforcing risk minimization for a targeted return.

Previous works have utilized the Harrow-Hassidim-Lloyd (HHL) algorithm for mean-variance portfolio optimization, which can be formulated as a linear quadratic-programming problem. However, multiple components of HHL are incompatible with the implementation on Noisy Intermediate Scale Quantum (NISQ) systems, which reflects the current state of quantum computers. For instance, eigenvalue inversion is an expensive subcircuit to run on such near-term devices, which suffer from prohibitively many errors over the course of the circuit execution.

The authors in this work introduce a classical/quantum hybrid HHL algorithm called NISQ-HHL, which is obtained by leveraging newly available hardware features and optimizing existing components of HHL. The objective is to execute and validate NISQ-HHL on real quantum hardware supporting mid-circuit measurement, qubit reset and reuse, and Quantum Conditional Logic (QCL). An enhanced formulation of the classical/quantum hybrid HHL algorithm is presented that integrates all the aforementioned features into the separate Quantum Phase Estimation (QPE) routine used for eigenvalue estimation. The end-to-end flow of NISQ-HHL consists of four steps:
i) The QCL-QPE procedure is used to construct a distribution over the estimates of the relevant eigenvalues with n-bit precision.
ii) Classical post-processing is performed on the resulting histogram to obtain the estimates of the relevant eigenvalues.
iii) The obtained n-bit estimates are used to determine rotation angles for the eigenvalue inversion circuit. The estimates are then mapped to a smaller number of bits (r) such that each rotation is conditioned on its corresponding r-bit estimate.
iv) A standard HHL procedure is executed using the circuit constructed in the above step for the eigenvalue inversion. In order to estimate the performance of NISQ-HHL on quantum hardware, in this work the Hamiltonian is simulated using classical algorithms instead of quantum algorithms and a circuit transpiler is used that decomposes it into basis gates relevant for e.g. superconducting-based NISQ hardware.

The first step of NISQ-HHL is to obtain estimates of the relevant eigenvalues using QCL-QPE. This variant of QPE uses mid-circuit measurement, qubit reset and reuse, and Quantum Conditional Logic (QCL). Implementing QCL-QPE has two advantages: i) It reduces the number of ancillas to just one for arbitrary bit precision and hence reduces the number of qubits required, which is important in the NISQ era where not that many logical qubits are available. ii) QCL-QPE replaces two-qubit gates with one-qubit gates controlled by classical bits, thereby reducing the requirement for qubit connectivity, SWAP gates or qubit transport. Also, an algorithm is proposed to optimize the scaling parameter γ for the Hamiltonian simulation required by QCL-QPE, that led to higher accuracy while resolving the eigenvalues. In comparison to the uniformly controlled rotation approach, the number of rotations in the NISQ-HHL implementation is smaller, and the circuit is therefore less deep.

In terms of an experimental implementation of the algorithm, the authors consider a portfolio-optimization problem with two S&P 500 assets. It is implemented on trapped-ion Honeywell System Model H1 after transpiling and optimizing the circuits from Qiskit to H1’s native gates using Cambridge Quantum’s pytket package. Experimental results show that QCL-QPE achieves high fidelity, between experimental and simulated measurement distributions, for three-bit precision. For four-bit estimations, QLC-QPE achieved a higher fidelity than the standard QPE. Also, the NISQ-HHL eigenvalue inversion circuit is shown to be more efficient than the uniformly controlled rotation gate method, mainly due to the reduced number of controlled rotations, and the circuit depth. Moreover, the work demonstrates that NISQ-HHL can scale to larger portfolios than those supported on current quantum hardware.

The total complexity of NISQ-HHL presented here is shown to be lower than the previously proposed methods for a low-qubit count, such as quantum arithmetic and uniformly controlled rotation gate, although the authors were unable to show asymptotic efficiency. Nevertheless, the presented methodology brings HHL implementation closer to current quantum hardware.
1 / 12

私たちにどんなお手伝いができるでしょうか?
以下のお問合せフォームからご連絡ください。

Invalid Input

Invalid Input

Invalid Input

Invalid Input

Invalid Input

Invalid Input

Copyright © Qu & Co
close