Optimizing parameterized quantum circuits promises efficient use of near-term quantum computers to achieve the potential quantum advantage. However, there is a notorious tradeoff between the expressibility and trainability of the parameter ansatz. We find that in combinatorial optimization problems, since the solutions are described by bit strings, one can trade the expressiveness of the ansatz for high trainability. To be specific, by focusing on the max-cut problem we introduce a simple yet efficient algorithm named Quantum Qubit Rotation Algorithm (QQRA). The quantum circuits are comprised with single-qubit rotation gates implementing on each qubit. The rotation angles of the gates can be trained free of barren plateaus. Thus, the approximate solution of the max-cut problem can be obtained with probability close to 1. To illustrate the effectiveness of QQRA, we compare it with the well known quantum approximate optimization algorithm and the classical Goemans-Williamson algorithm.
相關內容
We construct families of circles in the plane such that their tangency graphs have arbitrarily large girth and chromatic number. This provides a strong negative answer to Ringel's circle problem (1959). The proof relies on a (multidimensional) version of Gallai's theorem with polynomial constraints, which we derive from the Hales-Jewett theorem and which may be of independent interest.
How efficiently can we find an unknown graph using distance queries between its vertices? We assume that the unknown graph is connected, unweighted, and has bounded degree. The goal is to find every edge in the graph. This problem admits a reconstruction algorithm based on multi-phase Voronoi-cell decomposition and using $\tilde O(n^{3/2})$ distance queries. In our work, we analyze a simple reconstruction algorithm. We show that, on random $\Delta$-regular graphs, our algorithm uses $\tilde O(n)$ distance queries. As by-products, we can reconstruct those graphs using $O(\log^2 n)$ queries to an all-distances oracle or $\tilde O(n)$ queries to a betweenness oracle, and we bound the metric dimension of those graphs by $\log^2 n$. Our reconstruction algorithm has a very simple structure, and is highly parallelizable. On general graphs of bounded degree, our reconstruction algorithm has subquadratic query complexity.
The Quantum Reverse Shannon Theorem has been a milestone in quantum information theory. It states that asymptotically reliable simulation of a quantum channel assisted by unlimited shared entanglement is possible, if and only if, the classical communication cost is greater than or equal to the channel's entanglement-assisted capacity. In this letter, we are concerned with the performance of reliable reverse Shannon simulation of quantum channels. Our main result is an in-depth characterization of the reliability function, that is, the optimal rate under which the performance of channel simulation asymptotically approaches the perfect. In particular, we have determined the exact formula of the reliability function when the classical communication cost is not too high -- below a critical value. In the derivation, we have also obtained an achievability bound for the simulation of finite many copies of the channel, which is of realistic significance.
The great diversity of end-user tasks ranging from manufacturing environments to personal homes makes pre-programming robots for general purpose applications extremely challenging. In fact, teaching robots new actions from scratch that can be reused for previously unseen tasks remains a difficult challenge and is generally left up to robotics experts. In this work, we present iRoPro, an interactive Robot Programming framework that allows end-users with little to no technical background to teach a robot new reusable actions. We combine Programming by Demonstration and Automated Planning techniques to allow the user to construct the robot's knowledge base by teaching new actions by kinesthetic demonstration. The actions are generalised and reused with a task planner to solve previously unseen problems defined by the user. We implement iRoPro as an end-to-end system on a Baxter Research Robot to simultaneously teach low- and high-level actions by demonstration that the user can customise via a Graphical User Interface to adapt to their specific use case. To evaluate the feasibility of our approach, we first conducted pre-design experiments to better understand the user's adoption of involved concepts and the proposed robot programming process. We compare results with post-design experiments, where we conducted a user study to validate the usability of our approach with real end-users. Overall, we showed that users with different programming levels and educational backgrounds can easily learn and use iRoPro and its robot programming process.
In this work, we design a novel game-theoretical framework capable of capturing the defining aspects of quantum theory. We introduce an original model and an algorithmic procedure that enables to express measurement scenarios encountered in quantum mechanics as multiplayer games and to translate physical notions of causality, correlation, and contextuality to particular aspects of game theory. Furthermore, inspired by the established correspondence, we investigate the causal consistency of games in extensive form with imperfect information from the quantum perspective and we conclude that counterfactual dependencies should be distinguished from causation and correlation as a separate phenomenon of its own. Most significantly, we deduce that Nashian free choice game theory is non-contextual and hence is in contradiction with the Kochen-Specker theorem. Hence, we propose that quantum physics should be analysed with toolkits from non-Nashian game theory applied to our suggested model.
We consider a class of resource allocation problems given a set of unconditional constraints whose objective function satisfies Bellman's optimality principle. Such problems are ubiquitous in wireless communication, signal processing, and networking. These constrained combinatorial optimization problems are, in general, NP-Hard. This paper proposes two algorithms to solve this class of problems using a dynamic programming framework assisted by an information-theoretic measure. We demonstrate that the proposed algorithms ensure optimal solutions under carefully chosen conditions and use significantly reduced computational resources. We substantiate our claims by solving the power-constrained bit allocation problem in 5G massive Multiple-Input Multiple-Output receivers using the proposed approach.
In this paper a problem of numerical simulation of hydraulic fractures is considered. An efficient algorithm of solution, based on the universal scheme introduced earlier by the authors for the fractures propagating in elastic solids, is proposed. The algorithm utilizes a FEM based subroutine to compute deformation of the fractured material. Consequently, the computational scheme retains the relative simplicity of its original version and simultaneously enables one to deal with more advanced cases of the fractured material properties and configurations. In particular, the problems of poroelasticity, plasticity and spatially varying properties of the fractured material can be analyzed. The accuracy and efficiency of the proposed algorithm are verified against analytical benchmark solutions. The algorithm capabilities are demonstrated using the example of the hydraulic fracture propagating in complex geological settings.
In this paper we tackle the problem of dynamic portfolio optimization, i.e., determining the optimal trading trajectory for an investment portfolio of assets over a period of time, taking into account transaction costs and other possible constraints. This problem is central to quantitative finance. After a detailed introduction to the problem, we implement a number of quantum and quantum-inspired algorithms on different hardware platforms to solve its discrete formulation using real data from daily prices over 8 years of 52 assets, and do a detailed comparison of the obtained Sharpe ratios, profits and computing times. In particular, we implement classical solvers (Gekko, exhaustive), D-Wave Hybrid quantum annealing, two different approaches based on Variational Quantum Eigensolvers on IBM-Q (one of them brand-new and tailored to the problem), and for the first time in this context also a quantum-inspired optimizer based on Tensor Networks. In order to fit the data into each specific hardware platform, we also consider doing a preprocessing based on clustering of assets. From our comparison, we conclude that D-Wave Hybrid and Tensor Networks are able to handle the largest systems, where we do calculations up to 1272 fully-connected qubits for demonstrative purposes. Finally, we also discuss how to mathematically implement other possible real-life constraints, as well as several ideas to further improve the performance of the studied methods.
The existence of a universal learning architecture in human cognition is a widely spread conjecture supported by experimental findings from neuroscience. While no low-level implementation can be specified yet, an abstract outline of human perception and learning is believed to entail three basic properties: (a) hierarchical attention and processing, (b) memory-based knowledge representation, and (c) progressive learning and knowledge compaction. We approach the design of such a learning architecture from a system-theoretic viewpoint, developing a closed-loop system with three main components: (i) a multi-resolution analysis pre-processor, (ii) a group-invariant feature extractor, and (iii) a progressive knowledge-based learning module. Multi-resolution feedback loops are used for learning, i.e., for adapting the system parameters to online observations. To design (i) and (ii), we build upon the established theory of wavelet-based multi-resolution analysis and the properties of group convolution operators. Regarding (iii), we introduce a novel learning algorithm that constructs progressively growing knowledge representations in multiple resolutions. The proposed algorithm is an extension of the Online Deterministic Annealing (ODA) algorithm based on annealing optimization, solved using gradient-free stochastic approximation. ODA has inherent robustness and regularization properties and provides a means to progressively increase the complexity of the learning model i.e. the number of the neurons, as needed, through an intuitive bifurcation phenomenon. The proposed multi-resolution approach is hierarchical, progressive, knowledge-based, and interpretable. We illustrate the properties of the proposed architecture in the context of the state-of-the-art learning algorithms and deep learning methods.
Quantum hardware and quantum-inspired algorithms are becoming increasingly popular for combinatorial optimization. However, these algorithms may require careful hyperparameter tuning for each problem instance. We use a reinforcement learning agent in conjunction with a quantum-inspired algorithm to solve the Ising energy minimization problem, which is equivalent to the Maximum Cut problem. The agent controls the algorithm by tuning one of its parameters with the goal of improving recently seen solutions. We propose a new Rescaled Ranked Reward (R3) method that enables stable single-player version of self-play training that helps the agent to escape local optima. The training on any problem instance can be accelerated by applying transfer learning from an agent trained on randomly generated problems. Our approach allows sampling high-quality solutions to the Ising problem with high probability and outperforms both baseline heuristics and a black-box hyperparameter optimization approach.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191