OPUS Collection:

On the Quantum Time Complexity of Divide and Conquer

2025-06-30T00:00:00Z

Title: On the Quantum Time Complexity of Divide and Conquer Authors: Allcock, J; Bao, J; Belovs, A; Lee, T; Santha, M Abstract: In this work, we initiate a systematic study of the time complexity of quantum divide and conquer (QD&C) algorithms for classical problems, and propose a general framework for their analysis. We establish generic conditions under which search and minimization problems with classical divide and conquer algorithms are amenable to quantum speedup, and apply these theorems to various problems involving strings, integers, and geometric objects. These include Longest Distinct Substring, Klee’s Coverage, several optimization problems on stock transactions, and k-Increasing Subsequence. For most of these problems our quantum time upper bounds match the quantum query lower bounds, up to polylogarithmic factors. We give a structured framework for describing and classifying a wide variety of QD&C algorithms so that quantum speedups can be more easily identified and applied, and prove general statements on QD&C time complexity covering a range of cases, accounting for the time required for all operations. In particular, we explicitly account for memory access operations in the commonly used QRAM (read-only) and QRAG (read-write) models, which are assumed to take unit time in the query model, and which require careful analysis when involved in recursion. Our generic QD&C theorems have several nice features. 1. To apply them, it suffices to come up with a classical divide and conquer algorithm satisfying the conditions of the theorem. The quantization of the algorithm is then completely handled by the theorem. This can make it easier to find applications which admit a quantum speedup, and contrast with dynamic programming algorithms which can be difficult to quantize due to their highly sequential nature. 2. As these theorems give bounds on time complexity, they can be applied to a greater range of problems than those based on query complexity, e.g., where the best-known quantum algorithms require super-linear time. 3. It can handle minimization problems as well as boolean functions, which allows us to improve on the query complexity result of Childs et al. [13] for k-Increasing Subsequence by a logarithmic factor.

Scaling Up or Scaling Down? Rubrics, Peer Assessment and Feedback Literacy in a Large Postgraduate Cohort

2026-06-12T00:00:00Z

Title: Scaling Up or Scaling Down? Rubrics, Peer Assessment and Feedback Literacy in a Large Postgraduate Cohort Authors: Atif, A Abstract: This paper examines the use of rubrics to support peer assessment and feedback literacy in a large postgraduate cohort of over 210 students at an Australian university. Drawing on reflective practitioner inquiry, it explores how an analytic feedback rubric designed primarily as a feedback tool rather than a marking guide was deployed to scaffold peer assessment within a major group project. Three interrelated challenges are documented: inconsistent criterion application, surface-level compliance among a quarter of students, and affective barriers for culturally diverse learners. The paper reports on iterative adaptations, including co-developed rubric language and calibration activities, and reflects on their effectiveness. It argues that rubrics are necessary but insufficient for sustainable feedback at scale, and that their effectiveness depends on deliberate pedagogical scaffolding. The findings suggest that sustainable feedback at scale requires to be treated as dialogic tools rather than static artefacts.

Superconducting qubits in the millions: The potential and limitations of modularity

2026-04-01T00:00:00Z

Title: Superconducting qubits in the millions: The potential and limitations of modularity Authors: Anonymous, Abstract: The development of fault-tolerant quantum computers (FTQCs) is receiving increasing attention within the quantum computing community. Like conventional digital computers, FTQCs, which utilize error correction and millions of physical qubits, have the potential to address some of humanity’s grand challenges. However, accurate estimates of the tangible scale of future FTQCs, based on transparent assumptions, are uncommon. How many physical qubits are necessary to solve a practical problem intractable for classical hardware? What costs arise from distributing quantum computation across multiple machines? This paper presents an architectural model of a potential FTQC based on superconducting qubits, divided into discrete modules and interconnected via coherent links. We employ a resource-estimation framework and software tool to assess the physical resources required to execute specific quantum algorithms compiled into their graph-state form and arranged onto a modular superconducting hardware architecture. Our tool can predict the size, power consumption, and execution time of these algorithms based on explicit assumptions about the physical layout, thermal load, and modular connectivity of the system. We assess the resources needed for quantum computation examples that serve as building blocks of proposed applications, quantifying the architectural bottlenecks and trade-offs that remain to be addressed to deliver utility.

Purchase Intention in Augmented Reality vs. Web Shopping: A Multimodal Exploration

2026-02-05T00:00:00Z

Title: Purchase Intention in Augmented Reality vs. Web Shopping: A Multimodal Exploration Authors: Perez, A; Singh, A; Pontes, V Abstract: Augmented reality (AR) is gaining traction as a tool for immersive digital marketing, yet its influence on consumer decision-making remains underexplored, particularly when delivered through head-mounted displays (HMDs). This pilot study investigates how AR affects physiological engagement and purchase intention by comparing AR and web shopping experiences across galvanic skin response, heart rate variability, heart rate, and eye movement metrics, alongside perceived usefulness and enjoyment. Eighteen participants completed a shopping task in one of two conditions while physiological and self-report data were collected. Although some significant differences were observed in eye-tracking metrics, most physiological and self-reported outcomes did not reach statistical significance. Regression analyses revealed promising - but inconclusive - trends linking both physiological and attitudinal predictors to purchase intention, as seen through willingness-to-pay (WTP). These findings underscore the need for larger, better-powered studies but offer methodological insights into integrating multimodal data for intelligent AR systems and the Stimulus-Organism-Response (SOR) framework.