We study a parameterized version of the local Hamiltonian problem, called the weighted local Hamiltonian problem, where the relevant quantum states are superpositions of computational basis states of Hamming weight k . The Hamming weight constraint can have a physical interpretation as a constraint on the number of excitations allowed or the particle number in a system. We prove that this problem is in QW[1] , the first level of the quantum weft hierarchy, and that it is hard for QM[1] , the quantum analogue of M[1] . Our results show that this problem cannot be fixed parameter quantum tractable (FPQT) unless certain natural quantum analogue of the exponential time hypothesis (ETH) is false.

Cooperative AI and AI alignment research are increasingly important fields of study as machine learning models are becoming more prevalent in society. Applications such as self-driving cars, realistic AI in games, and human-AI teams, all require further advancement in cooperative and alignment research before more widespread applications can be achieved. However, research in these fields has typically lagged behind other machine learning applications due to the difficulty of creating models that are robust to and can adapt to novel human partners. We attempt to address this through the creation of a framework that uses Archetypal Analysis, a unique clustering algorithm that finds extremal ‘archetype’ points in a dataset and expresses each other point as a convex combination of these archetypes. This framework creates understandable archetypes of players which a reinforcement learning agent can use to adapt accordingly to unseen partners. We show that this framework not only results in performance comparable to other cooperative benchmark models but also achieves higher levels of perceived cooperativeness without the need for human involvement during the training process. As such, we demonstrate that the use of clustering techniques to better model different types of human behaviour and strategies can be an effective approach in improving the ability of AI models to adapt to and improve cooperation with novel partners.

Control of complex networks is one of the most challenging open problems within network science. One view says that we can only claim to fully understand a network if we have the ability to influence or control it and predict the results of the employed control mechanisms. The area of control and controllability has progressed notably in the past ten years with several frameworks proposed namely, structural, exact, and physical. With continuing advancement in the area, the need to develop effective and efficient control methods that provide robust control is increasingly critical. The ultimate responsibility for controlling the network lies with the set of driver nodes that, according to the classical definition of the control theory of complex systems, can steer the network from any given state to a desired final state. To be able to develop better control mechanisms, we need to understand the relationship between different network structures and the number of driver nodes needed to control a given structure. This will allow understanding of which networks might be easier to control and the resources needed to control them. In this paper, we present a systematic study that builds an understanding of how network profiles (random (R), small-world (SW), scale-free (SF)) influence the number of driver nodes needed for control. Additionally, we also consider real social networks and identify their driver nodes set to further expand the discussion. We mean to find a correlation between network structure measures and number of driver nodes. Our results show that there is in fact a strong relationship between these.

Given two graphs modelling related, but possibly distinct, networks, the alignment of the networks can help identify significant structures and substructures which may relate to the functional purpose of the network components. The Network Alignment Problem is the NP-hard computational formalisation of this goal and is a useful technique in a variety of data mining and knowledge discovery domains. In this paper we develop a memetic algorithm to solve the Network Alignment Problem and demonstrate the effectiveness of the approach on a series of biological networks against the existing state of the art alignment tools. We also demonstrate the use of network alignment as a clustering and classification tool on two mental health disorder diagnostic databases.

Recent data-driven research has produced metrics for quantifying a novice programmer's error profile, such as Jadud's error quotient. However, these metrics tend to be context dependent and contain free parameters. This paper reviews the caveats of such metrics and proposes a more general approach to developing a metric. The online implementation of the proposed metric is publicly available at http://online-analysis-demo.herokuapp.com/.

Trees are a fundamental structure in algorithmics. In this paper, we study the transformation of an arbitrary binary tree S with n vertices into a completely balanced tree T via rotations , a widely studied elementary tree operation. Combining concepts on rotation distance and data structures, we give a basic algorithm that performs the transformation in Θ( n ) time and Θ(1) space, making at most 2 n − 2 log 2n rotations and improving on known previous results. The algorithm is then improved, exploiting particular properties of S . Finally, we show tighter upper bounds and obtain a close lower bound on the rotation distance between a zig-zag tree and a completely balanced tree. We also find the exact rotation distance of a particular almost balanced tree to a completely balanced tree, and thus show that their distance is quite large despite the similarity of the two trees.