Arrow Research search

Author name cluster

Sanjiang Li

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

33 papers
2 author rows

Possible papers

33

AAAI Conference 2025 Conference Paper

On the Trainability and Classical Simulability of Learning Matrix Product States Variationally

  • Afrad Basheer
  • Yuan Feng
  • Christopher Ferrie
  • Sanjiang Li
  • Hakop Pashayan

We prove that using global observables to train the matrix product state ansatz results in the vanishing of all partial derivatives, also known as barren plateaus, while using local observables avoids this. This ansatz is widely used in quantum machine learning for learning weakly entangled state approximations. Additionally, we empirically demonstrate that in many cases, the objective function is an inner product of almost sparse operators, highlighting the potential for classically simulating such a learning problem with few quantum resources. All our results are experimentally validated across various scenarios.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

Ansatz-Agnostic Exponential Resource Saving in Variational Quantum Algorithms Using Shallow Shadows

  • Afrad Basheer
  • Yuan Feng
  • Christopher Ferrie
  • Sanjiang Li

Variational Quantum Algorithms (VQA) have been identified as a promising candidate for the demonstration of near-term quantum advantage in solving optimization tasks in chemical simulation, quantum information, and machine learning. The standard model of training requires a significant amount of quantum resources, which led researchers to use classical shadows to devise an alternative that consumes exponentially fewer quantum resources. However, the approach only works when the observables are local and the ansatz is the shallow Alternating Layered Ansatz (ALA), thus severely limiting its potential in solving problems such as quantum state preparation, where the ideal state might not be approximable with an ALA. In this work, we present a protocol based on shallow shadows that achieves similar levels of savings for almost any shallow ansatz studied in the literature, when combined with observables of low Frobenius norm. We show that two important applications in quantum information for which VQAs can be a powerful option, namely variational quantum state preparation and variational quantum circuit synthesis, are compatible with our protocol. We also experimentally demonstrate orders of magnitude improvement in comparison to the standard VQA model.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Alternating Layered Variational Quantum Circuits Can Be Classically Optimized Efficiently Using Classical Shadows

  • Afrad Basheer
  • Yuan Feng
  • Christopher Ferrie
  • Sanjiang Li

Variational quantum algorithms (VQAs) are the quantum analog of classical neural networks (NNs). A VQA consists of a parameterized quantum circuit (PQC) which is composed of multiple layers of ansatzes (simpler PQCs, which are an analogy of NN layers) that differ only in selections of parameters. Previous work has identified the alternating layered ansatz as potentially a new standard ansatz in near-term quantum computing. Indeed, shallow alternating layered VQAs are easy to implement and have been shown to be both trainable and expressive. In this work, we introduce a training algorithm with an exponential reduction in training cost of such VQAs. Moreover, our algorithm uses classical shadows of quantum input data, and can hence be run on a classical computer with rigorous performance guarantees. We demonstrate 2-3 orders of magnitude improvement in the training cost using our algorithm for the example problems of finding state preparation circuits and the quantum autoencoder.

PDF Details DOI

JAAMAS Journal 2018 Journal Article

A new distributed algorithm for efficient generalized arc-consistency propagation

  • Shufeng Kong
  • Jae Hee Lee
  • Sanjiang Li

Abstract Generalized arc-consistency propagation is predominantly used in constraint solvers to efficiently prune the search space when solving constraint satisfaction problems. Although many practical applications can be modelled as distributed constraint satisfaction problems, no distributed arc-consistency algorithms so far have considered the privacy of individual agents. In this paper, we propose a new distributed arc-consistency algorithm, called \(\mathsf {DisAC3. 1}\), which leaks less private information of agents than existing distributed arc-consistency algorithms. In particular, \(\mathsf {DisAC3. 1}\) uses a novel termination determination mechanism, which allows the agents to share domains, constraints and communication addresses only with relevant agents. We further extend \(\mathsf {DisAC3. 1}\) to \(\mathsf {DisGAC3. 1}\), which is the first distributed algorithm that enforces generalized arc-consistency on k -ary ( \(k\ge 2\) ) constraint satisfaction problems. Theoretical analyses show that our algorithms are efficient in both time and space. Experiments also demonstrate that \(\mathsf {DisAC3. 1}\) outperforms the state-of-the-art distributed arc-consistency algorithm and that \(\mathsf {DisGAC3. 1}\) ’s performance scales linearly in the number of agents.

Details DOI

AAAI Conference 2018 Conference Paper

Multiagent Simple Temporal Problem: The Arc-Consistency Approach

  • Shufeng Kong
  • Jae Hee Lee
  • Sanjiang Li

The Simple Temporal Problem (STP) is a fundamental temporal reasoning problem and has recently been extended to the Multiagent Simple Temporal Problem (MaSTP). In this paper we present a novel approach that is based on enforcing arc-consistency (AC) on the input (multiagent) simple temporal network. We show that the AC-based approach is suf- ficient for solving both the STP and MaSTP and provide ef- ficient algorithms for them. As our AC-based approach does not impose new constraints between agents, it does not violate the privacy of the agents and is superior to the state-ofthe-art approach to MaSTP. Empirical evaluations on diverse benchmark datasets also show that our AC-based algorithms for STP and MaSTP are significantly more efficient than existing approaches.

PDF Details

IJCAI Conference 2018 Conference Paper

Reasoning about Betweenness and RCC8 Constraints in Qualitative Conceptual Spaces

  • Steven Schockaert
  • Sanjiang Li

Conceptual spaces are a knowledge representation framework in which concepts are represented geometrically, using convex regions. Motivated by the fact that exact conceptual spaces are usually difficult to obtain, we study the problem of spatial reasoning about qualitative abstractions of such representations. In particular, we consider the problem of deciding whether an RCC8 network extended with constraints about betweenness can be realized using bounded and convex regions in a high-dimensional Euclidean space. After showing that this decision problem is PSPACE-hard in general, we introduce an important fragment for which deciding realizability is NP-complete.

PDF Details

AAMAS Conference 2017 Conference Paper

A Deterministic Distributed Algorithm for Reasoning with Connected Row-Convex Constraints

  • Shufeng Kong
  • Jae Hee Lee
  • Sanjiang Li

The class of CRC constraints generalizes several tractable classes of constraints and is expressive enough to model problems in domains such as temporal reasoning, geometric reasoning, and scene labelling. This paper presents the first distributed deterministic algorithm for connected row-convex (CRC) constraints. Our distributed (partial) path consistency algorithm efficiently transforms a CRC constraint network into an equivalent constraint network, where all constraints are minimal (i. e. , they are the tightest constraints) and generating all solutions can be done in a backtrackfree manner. When compared with the state-of-the-art distributed algorithm for CRC constraints, which is a randomized one, our algorithm guarantees to generate a solution for satisfiable CRC constraint networks and it is applicable to solve large networks in real distributed systems. The experimental evaluations show that our algorithm outperforms the state-of-the-art algorithm in both practice and theory.

PDF

IJCAI Conference 2017 Conference Paper

On Redundant Topological Constraints (Extended Abstract)

  • Sanjiang Li
  • Zhiguo Long
  • Weiming Liu
  • Matt Duckham
  • Alan Both

Redundancy checking is an important task in AI subfields such as knowledge representation and constraint solving. This paper considers redundant topological constraints, defined in the region connection calculus RCC8. We say a constraint in a set C of RCC8 constraints is redundant if it is entailed by the rest of C. A prime subnetwork of C is a subset of C which contains no redundant constraints and has the same solution set as C. It is natural to ask how to compute such a prime subnetwork, and when it is unique. While this problem is in general intractable, we show that, if S is a subalgebra of RCC8 in which weak composition distributes over nonempty intersections, then C has a unique prime subnetwork, which can be obtained in cubic time by removing all redundant constraints simultaneously from C. As a by-product, we show that any path-consistent network over such a distributive subalgebra is minimal.

PDF Details

IJCAI Conference 2016 Conference Paper

Efficient Path Consistency Algorithm for Large Qualitative Constraint Networks

  • Zhiguo Long
  • Michael Sioutis
  • Sanjiang Li

We propose a new algorithm called DPC+ to enforce partial path consistency (PPC) on qualitative constraint networks. PPC restricts path consistency (PC) to a triangulation of the underlying constraint graph of a network. As PPC retains the sparseness of a constraint graph, it can make reasoning tasks such as consistency checking and minimal labelling of large qualitative constraint networks much easier to tackle than PC. For qualitative constraint networks defined over any distributive subalgebra of well-known spatio-temporal calculi, such as the Region Connection Calculus and the Interval Algebra, we show that DPC+ can achieve PPC very fast. Indeed, the algorithm enforces PPC on a qualitative constraint network by processing each triangle in a triangulation of its underlying constraint graph at most three times. Our experiments demonstrate significant improvements of DPC+ over the state-of-the-art PPC enforcing algorithm.

PDF Details

KR Conference 2016 Conference Paper

Encoding Large RCC8 Scenarios Using Rectangular Pseudo-Solutions

  • Zhiguo Long
  • Steven Schockaert
  • Sanjiang Li

Most approaches in the field of qualitative spatial reasoning (QSR) use constraint networks to encode spatial scenarios. The size of these networks is quadratic in the number of variables, which has severely limited the real-world application of QSR. In this paper, we propose another representation of spatial scenarios, in which each variable is associated with one or more rectangles. Instead of requiring these rectangles to define a solution of the corresponding constraint network, we construct sequences of rectangles that define partial solutions to progressively weaker constraint networks. We present experimental results that illustrate the effectiveness of this strategy.

ECAI Conference 2016 Conference Paper

On Redundancy in Simple Temporal Networks

  • Jae Hee Lee 0001
  • Sanjiang Li
  • Zhiguo Long
  • Michael Sioutis

The Simple Temporal Problem (STP) has been widely used in various applications to schedule tasks. For dynamical systems, scheduling needs to be efficient and flexible to handle uncertainty and perturbation. To this end, modern approaches usually encode the temporal information as an STP instance. This representation contains redundant information, which can not only take a significant amount of storage space, but also make scheduling inefficient due to the non-concise representation. In this paper, we investigate the problem of simplifying an STP instance by removing redundant information. We show that such a simplification can result in a unique minimal representation without loss of temporal information, and present an efficient algorithm to achieve this task. Evaluation on a large benchmark dataset of STP exhibits a significant reduction in redundant information for the involved instances.

Details

AAAI Conference 2015 Conference Paper

Belief Revision with General Epistemic States

  • Hua Meng
  • Hui Kou
  • Sanjiang Li

In order to properly regulate iterated belief revision, Darwiche and Pearl (1997) model belief revision as revising epistemic states by propositions. An epistemic state in their sense consists of a belief set and a set of conditional beliefs. Although the denotation of an epistemic state can be indirectly captured by a total preorder on the set of worlds, it is unclear how to directly capture the structure in terms of the beliefs and conditional beliefs it contains. In this paper, we first provide an axiomatic characterisation for epistemic states by using nine rules about beliefs and conditional beliefs, and then argue that the last two rules are too strong and should be eliminated for characterising the belief state of an agent. We call a structure which satisfies the first seven rules a general epistemic state (GEP). To provide a semantical characterisation of GEPs, we introduce a mathematical structure called belief algebra, which is in essence a certain binary relation defined on the power set of worlds. We then establish a 1-1 correspondence between GEPs and belief algebras, and show that total preorders on worlds are special cases of belief algebras. Furthermore, using the notion of belief algebras, we extend the classical iterated belief revision rules of Darwiche and Pearl to our setting of general epistemic states.

PDF Details

IJCAI Conference 2015 Conference Paper

Efficiently Characterizing Non-Redundant Constraints in Large Real World Qualitative Spatial Networks

  • Michael Sioutis
  • Sanjiang Li
  • Jean-Francois Condotta

RCC8 is a constraint language that serves for qualitative spatial representation and reasoning by encoding the topological relations between spatial entities. We focus on efficiently characterizing nonredundant constraints in large real world RCC8 networks and obtaining their prime networks. For a RCC8 network N a constraint is redundant, if removing that constraint from N does not change the solution set of N. A prime network of N is a network which contains no redundant constraints, but has the same solution set as N. We make use of a particular partial consistency, namely, G-consistency, and obtain new complexity results for various cases of RCC8 networks, while we also show that given a maximal distributive subclass for RCC8 and a network N defined on that subclass, the prunning capacity of G-consistency and -consistency is identical on the common edges of G and the complete graph of N, when G is a triangulation of the constraint graph of N. Finally, we devise an algorithm based on G-consistency to compute the unique prime network of a RCC8 network, and show that it significantly progresses the stateof-the-art for practical reasoning with real RCC8 networks scaling up to millions of nodes.

PDF Details

KR Conference 2014 Short Paper

On Redundant Topological Constraints

  • Matt Duckham
  • Sanjiang Li
  • Weiming Liu
  • Zhiguo Long

The Region Connection Calculus (RCC) is a well-known calculus for representing part-whole and topological relations. It plays an important role in qualitative spatial reasoning, geographical information science, and ontology. The computational complexity of reasoning with RCC has been investigated in depth in the literature. Most of these works focus on the consistency of RCC constraint networks. In this paper, we consider the important problem of redundant RCC constraints. For a set Γ of RCC constraints, we say a constraint (xRy) in Γ is redundant if it can be entailed by the rest of Γ. A prime subnetwork of Γ is a subset of Γ which contains no redundant constraints but has the same solution set as Γ. It is natural to ask how to compute a prime subnetwork, and when it is unique. In this paper, we show that this problem is in general intractable, but becomes tractable if Γ is over a tractable subclass of RCC. If S is a tractable subclass in which weak composition distributes over non-empty intersections, then we can show that Γ has a unique prime network, which is obtained by removing all redundant constraints from Γ. As a byproduct, we identify a sufficient condition for a path-consistent network being minimal.

IJCAI Conference 2013 Conference Paper

Combining RCC5 Relations with Betweenness Information

  • Steven Schockaert
  • Sanjiang Li

RCC5 is an important and well-known calculus for representing and reasoning about mereological relations. Among many other applications, it is pivotal in the formalization of commonsense reasoning about natural categories. In particular, it allows for a qualitative representation of conceptual spaces in the sense of Gärdenfors. To further the role of RCC5 as a vehicle for conceptual reasoning, in this paper we combine RCC5 relations with information about betweenness of regions. The resulting calculus allows us to express, for instance, that some part (but not all) of region B is between regions A and C. We show how consistency can be decided in polynomial time for atomic networks, even when regions are required to be convex. From an application perspective, the ability to express betweenness information allows us to use RCC5 as a basis for interpolative reasoning, while the restriction to convex regions ensures that all consistent networks can be faithfully represented as a conceptual space.

PDF Details DOI

ECAI Conference 2012 Conference Paper

Convex Solutions of RCC8 Networks

  • Steven Schockaert
  • Sanjiang Li

RCC8 is one of the most widely used calculi for qualitative spatial reasoning. Although many applications have been explored where RCC8 relations refer to geographical or physical regions in two- or three-dimensional spaces, their use for conceptual reasoning is still at a rather preliminary stage. One of the core obstacles with using RCC8 to reason about conceptual spaces is that regions are required to be convex in this context. We investigate in this paper how the latter requirement impacts the realizability of RCC8 networks. Specifically, we show that consistent RCC8 networks over 2n + 1 variables are guaranteed to have a convex solution in Euclidean spaces of n dimensions and higher. We furthermore prove that our bound is optimal for 2- and 3-dimensional spaces, and that for any number of dimensions n ≥ 4, there exists a network of RCC8 relations over 3n variables which is consistent, but does not allow a convex solution in the n-dimensional Euclidean space.

Details

ECAI Conference 2012 Conference Paper

Here, There, but Not Everywhere: An Extended Framework for Qualitative Constraint Satisfaction

  • Weiming Liu 0001
  • Sanjiang Li

Dealing with spatial and temporal knowledge is an indispensable part of almost all aspects of human activities. The qualitative approach to spatial and temporal reasoning (QSTR) provides a promising framework for spatial and temporal knowledge representation and reasoning. QSTR typically represents spatial/temporal knowledge in terms of qualitative relations (e. g. , to the east of, after), and reasons with the knowledge by solving qualitative constraints. When formulating a qualitative constraint satisfaction problem (CSP), it is usually assumed that each variable could be "here, there and everywhere. " Practical applications e. g. urban planning, however, often require a variable taking values from a certain finite subset of the universe, i. e. require it to be 'here or there'. This paper extends the classic framework of qualitative constraint satisfaction by allowing variables taking values from finite domains. The computational complexity of this extended consistency problem is examined for five most important qualitative calculi, viz. Point Algebra, Interval Algebra, Cardinal Relation Algebra, RCC-5, and RCC-8. We show that the extended consistency problem remains in NP, but when only basic constraints are considered, the extended consistency problem for each calculus except Point Algebra is already NP-hard.

Details

KR Conference 2010 Conference Paper

A Layered Graph Representation for Complex Regions

  • Sanjiang Li

This paper proposes a layered graph model for representing the internal structure of complex plane regions, where each node represents the closure of a connected component of the interior or exterior of a complex region. The model provides a complete representation in the sense that the (global) nineintersections between the interiors, the boundaries, and the exteriors of two complex regions can be determined by the (local) RCC8 relations between associated simple regions. Figure 1: Two complex regions

AAAI Conference 2010 Conference Paper

Topological Relations between Convex Regions

  • Sanjiang Li
  • Weiming Liu

Topological relations between spatial objects are the most important kind of qualitative spatial information. Dozens of relation models have been proposed in the past two decades. These models usually make a small number of distinctions and therefore can only cope with spatial information at a fixed granularity of spatial knowledge. In this paper, we propose a topological relation model in which the topological relation between two convex plane regions can be uniquely represented as a circular string over the alphabet {u, v, x, y}. A linear algorithm is given to compute the topological relation between two convex polygons. The infinite relation calculus could be used in hierarchical spatial reasoning as well as in qualitative shape description.

PDF Details

IJCAI Conference 2009 Conference Paper

  • Weiming Liu
  • Sanjiang Li
  • Jochen Renz

Increasing the expressiveness of qualitative spatial calculi is an essential step towards meeting the requirements of applications. This can be achieved by combining existing calculi in a way that we can express spatial information using relations from both calculi. The great challenge is to develop reasoning algorithms that are correct and complete when reasoning over the combined information. Previous work has mainly studied cases where the interaction between the combined calculi was small, or where one of the two calculi was very simple. In this paper we tackle the important combination of topological and directional information for extended spatial objects. We combine some of the best known calculi in qualitative spatial reasoning (QSR), the RCC8 algebra for representing topological information, and the Rectangle Algebra (RA) and the Cardinal Direction Calculus (CDC) for directional information. Although CDC is more expressive than RA, reasoning with CDC is of the same order as reasoning with RA. We show that reasoning with basic RCC8 and basic RA relations is in P, but reasoning with basic RCC8 and basic CDC relations is NP-Complete.

PDF Details

ECAI Conference 2008 Conference Paper

Combining binary constraint networks in qualitative reasoning

  • Jason Jingshi Li
  • Tomasz Kowalski
  • Jochen Renz
  • Sanjiang Li

Constraint networks in qualitative spatial and temporal reasoning are always complete graphs. When one adds an extra element to a given network, previously unknown constraints are derived by intersections and compositions of other constraints, and this may introduce inconsistency to the overall network. Likewise, when combining two consistent networks that share a common part, the combined network may become inconsistent.

Details

AAAI Conference 2008 Conference Paper

Reasoning with Cardinal Directions: An Efficient Algorithm

  • Xiaotong Zhang
  • Sanjiang Li

Direction relations between extended spatial objects are important commonsense knowledge. Recently, Goyal and Egenhofer proposed a formal model, called Cardinal Direction Calculus (CDC), for representing direction relations between connected plane regions. CDC is perhaps the most expressive qualitative calculus for directional information, and has attracted increasing interest from areas such as artificial intelligence, geographical information science, and image retrieval. Given a network of CDC constraints, the consistency problem is deciding if the network is realizable by connected regions in the real plane. This paper provides a cubic algorithm for checking consistency of basic CDC constraint networks. As one byproduct, we also show that any consistent network of CDC constraints has a canonical realization in digital plane. The cubic algorithm can also been adapted to cope with disconnected regions, in which case the current best algorithm is of time complexity O(n5 ).

PDF Details

IJCAI Conference 2007 Conference Paper

  • Sanjiang Li

Current research on qualitative spatial representation and reasoning usually focuses on one single aspect of space. However, in real world applications, several aspects are often involved together. This paper extends the well-known RCC8 constraint language to deal with both topological and directional information, and then investigates the interaction between the two kinds of information. Given a topological (RCC8) constraint network and a directional constraint network, we ask when the joint network is satisfiable. We show that when the topological network is over one of the three maximal tractable subclasses of RCC8, the problem can be reduced into satisfiability problems in the RCC8 algebra and the rectangle algebra (RA). Therefore, reasoning techniques developed for RCC8 and RA can be used to solve the satisfiability problem of a joint network.

PDF Details