skip to main content

Title: Bounded Continuous-Time Satisfiability Solver
To tackle problems that can not be solved by current digital computers, many systems propose ideas from physics and neuroscience. The CTDS solver introduced by Ercsey-Ravasz and Toroczkai is one of such system. It solves the satisfiability problem by reducing it to a minimization of a time-varying target function. Although the possibility of an efficient electric circuit implementation of the solver has been shown, in terms of physical realizations, the solver has a problem of unbounded variations of the target function parameters. Here we propose a variant of the solver with bounded target function parameters. It includes several possible modifications of the solver in system parameter differences. We also show the basic characteristics of the solver, the upper and lower bounds of the target function parameters.
Authors:
; ; ;
Award ID(s):
1644368 1640081
Publication Date:
NSF-PAR ID:
10163758
Journal Name:
International Symposium on Nonlinear Theory and its Applications (NOLTA2019)
Page Range or eLocation-ID:
436--439
Sponsoring Org:
National Science Foundation
More Like this
  1. To tackle problems that can not be solved by current digital computers, many systems propose ideas from physics and neuroscience. The CTDS solver introduced by Ercsey-Ravasz and Toroczkai is one of such system. It solves the satisfiability problem by reducing it to a minimization of a time-varying target function. Although the possibility of an efficient electric circuit implementation of the solver has been shown, in terms of physical realizations, the solver has a problem of unbounded variations of the target function parameters. Here we propose a variant of the solver with bounded target function parameters. It includes several possible modificationsmore »of the solver in system parameter differences. We also show the basic characteristics of the solver, the upper and lower bounds of the target function parameters.« less
  2. Appeared in the proceedings of the 2021 IFAC Workshop on Time-Delay Systems This paper establishes a PIE (Partial Integral Equation)-based technique for the robust stability and H∞ performance analysis of linear systems with interval delays. The delays considered are time-invariant but uncertain, residing within a bounded interval excluding zero. We first propose a structured class of PIE systems with parametric uncertainty, then propose a Linear PI Inequality (LPI) for robust stability and H∞ performance of PIEs with polytopic uncertainty. Next, we consider the problem of robust stability and H∞ performance of multidelay systems with interval uncertainty in the delay parametersmore »and show this problem is equivalent to robust stability and performance of a given PIE with parametric uncertainty. The robust stability and H∞ performance of the uncertain time-delay system are then solved using the LPI solver in the MATLAB PIETOOLS toolbox. Numerical examples are given to prove the effectiveness and accuracy of the method. This paper adds to the expanding field of PIE approach and can be extended to linear partial differential equations.« less
  3. Problem definition: Inspired by new developments in dynamic spectrum access, we study the dynamic pricing of wireless Internet access when demand and capacity (bandwidth) are stochastic. Academic/practical relevance: The demand for wireless Internet access has increased enormously. However, the spectrum available to wireless service providers is limited. The industry has, thus, altered conventional license-based spectrum access policies through unlicensed spectrum operations. The additional spectrum obtained through these operations has stochastic capacity. Thus, the pricing of this service by the service provider has novel challenges. The problem considered in this paper is, therefore, of high practical relevance and new to themore »academic literature. Methodology: We study this pricing problem using a Markov decision process model in which customers are posted dynamic prices based on their bandwidth requirement and the available capacity. Results: We characterize the structure of the optimal pricing policy as a function of the system state and of the input parameters. Because it is impossible to solve this problem for practically large state spaces, we propose a heuristic dynamic pricing policy that performs very well, particularly when the ratio of capacity to demand rate is low. Managerial implications: We demonstrate the value of using a dynamic heuristic pricing policy compared with the myopic and optimal static policies. The previous literature has studied similar systems with fixed capacity and has characterized conditions under which myopic policies perform well. In contrast, our setting has dynamic (stochastic) capacity, and we find that identifying good state-dependent heuristic pricing policies is of greater importance. Our heuristic policy is computationally more tractable and easier to implement than the optimal dynamic and static pricing policies. It also provides a significant performance improvement relative to the myopic and optimal static policies when capacity is scarce, a condition that holds for the practical setting that motivated this research.« less
  4. This paper studies the distributed linearly separable computation problem, which is a generalization of many existing distributed computing problems such as distributed gradient coding and distributed linear transform. A master asks N distributed workers to compute a linearly separable function of K datasets, which is a set of Kc linear combinations of K equal-length messages (each message is a function of one dataset). We assign some datasets to each worker in an uncoded manner, who then computes the corresponding messages and returns some function of these messages, such that from the answers of any Nr out of N workers themore »master can recover the task function with high probability. In the literature, the specific case where Kc = 1 or where the computation cost is minimum has been considered. In this paper, we focus on the general case (i.e., general Kc and general computation cost) and aim to find the minimum communication cost. We first propose a novel converse bound on the communication cost under the constraint of the popular cyclic assignment (widely considered in the literature), which assigns the datasets to the workers in a cyclic way. Motivated by the observation that existing strategies for distributed computing fall short of achieving the converse bound, we propose a novel distributed computing scheme for some system parameters. The proposed computing scheme is optimal for any assignment when Kc is large and is optimal under the cyclic assignment when the numbers of workers and datasets are equal or Kc is small. In addition, it is order optimal within a factor of 2 under the cyclic assignment for the remaining cases.« less
  5. Variational Quantum Algorithms (VQA) are one of the most promising candidates for near-term quantum advantage. Traditionally, these algorithms are parameterized by rotational gate angles whose values are tuned over iterative execution on quantum machines. The iterative tuning of these gate angle parameters make VQAs more robust to a quantum machine’s noise profile. However, the effect of noise is still a significant detriment to VQA’s target estimations on real quantum machines — they are far from ideal. Thus, it is imperative to employ effective error mitigation strategies to improve the fidelity of these quantum algorithms on near-term machines.While existing error mitigationmore »techniques built from theory do provide substantial gains, the disconnect between theory and real machine execution characteristics limit the scope of these improvements. Thus, it is critical to optimize mitigation techniques to explicitly suit the target application as well as the noise characteristics of the target machine.We propose VAQEM, which dynamically tailors existing error mitigation techniques to the actual, dynamic noisy execution characteristics of VQAs on a target quantum machine. We do so by tuning specific features of these mitigation techniques similar to the traditional rotation angle parameters -by targeting improvements towards a specific objective function which represents the VQA problem at hand. In this paper, we target two types of error mitigation techniques which are suited to idle times in quantum circuits: single qubit gate scheduling and the insertion of dynamical decoupling sequences. We gain substantial improvements to VQA objective measurements — a mean of over 3x across a variety of VQA applications, run on IBM Quantum machines.More importantly, while we study two specific error mitigation techniques, the proposed variational approach is general and can be extended to many other error mitigation techniques whose specific configurations are hard to select a priori. Integrating more mitigation techniques into the VAQEM framework in the future can lead to further formidable gains, potentially realizing practically useful VQA benefits on today’s noisy quantum machines.« less